generator.c 7.13 KB
Newer Older
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29
/**
 * @file generator.c
 * @author Ivaylo Ivanov 11777707
 * @date 11.01.2018
 *
 * @brief Generator program module.
 *
 * The generator program takes a graph as input. The program repeatedly generates a random solution
 * to the problem as described on the first page and writes its result to the circular buffer. It repeats this
 * procedure until it is notified by the supervisor to terminate.
 * The generator program takes as arguments the set of edges of the graph.
 * Each positional argument is one edge; at least one edge must be given. An edge is specified by a string,
 * with the indices of the two nodes it connects separated by a -. Since the graph is directed, the edge starts
 * at the first node and leads to the second node. Note that the number of nodes of the graph is implicitly
 * provided through the indices in the edges. In the example above the generator program is called with
 * the graph shown on the first page.
 * The generator uses the algorithm described on the first page to generate random feedback arc sets for the
 * given graph. It writes these feedback arc sets to the circular buffer, one at a time; therefore a feedback
 * arc set is a single element of the circular buffer. The generator may produce debug output, describing
 * the feedback arc sets which it writes to the circular buffer.
 *
 *   SYNOPSIS
 *   generator EDGE1 EDGE2 ...
 *
 *   EXAMPLE
 *   generator 0-1 1-2 1-3 1-4 2-4 3-6 4-3 4-5 6-0
 *
 **/
#include "shared/shm.c"
30 31
#include "shared/sem.c"
#include "shared/structs.c"
Ivaylo Ivanov's avatar
Ivaylo Ivanov committed
32
#include <regex.h>
33 34 35 36
#include <time.h>

void swap(int *a, int *b);
void shuffle(int arr[], size_t size);
Ivaylo Ivanov's avatar
Ivaylo Ivanov committed
37
static unsigned int base_seed = 0;
38 39

int main(int argc, char *argv[]) {
Ivaylo Ivanov's avatar
Ivaylo Ivanov committed
40 41 42
    if(argc < 2) {
        fprintf(stderr, "ERROR: Command takes at least one argument.\n");
        puts("Usage: \ngenerator EDGE1 EDGE2 ...");
43 44 45
        exit(EXIT_FAILURE);
    }

46 47 48 49 50
    if(atexit(clean_up) != 0) {
        fprintf(stderr, "ERROR: Cannot set exit function\n");
        exit(EXIT_FAILURE);
    }

51 52
    process_signal();

53
    /// Create a regex to check the input against
Ivaylo Ivanov's avatar
Ivaylo Ivanov committed
54 55 56 57 58 59
    regex_t regex;
    if(regcomp(&regex, "^[0-9]*-[0-9]*$", REG_EXTENDED|REG_NOSUB)) {
        fprintf(stderr, "ERROR: Could not compile regex\n");
        exit(EXIT_FAILURE);
    }

60 61
    int num_edges = argc - 1;
    edge_t edges[num_edges]; ///< Array to hold all edges
62 63 64 65

    char edge[128]; ///< Variable to hold a single edge later on
    edge[127] = 0;

66 67
    int num_nodes = 0;
    for(int i=1; i <= num_edges; i++) {
68
        /// Check the input and terminate if incorrect
Ivaylo Ivanov's avatar
Ivaylo Ivanov committed
69 70 71 72
        if(regexec(&regex, argv[i], 0, NULL, 0) == REG_NOMATCH) {
            fprintf(stderr, "ERROR: Incorrect input found\n");
            puts("Usage: \ngenerator EDGE1 EDGE2 ...");
            exit(EXIT_FAILURE);
73 74 75 76 77 78 79
        } else {
            /// If input is correct, split and add to the edges array
            strcpy(edge, argv[i]);
            char *u = strtok(edge, "-");
            char *v = strtok(NULL, "");
            edges[i-1].u = strtol(u, NULL, 10);
            edges[i-1].v = strtol(v, NULL, 10);
Ivaylo Ivanov's avatar
Ivaylo Ivanov committed
80
            edges[i-1].chosen = false;
81 82 83 84 85

            if(num_nodes < edges[i-1].u)
                num_nodes = edges[i-1].u;
            if(num_nodes < edges[i-1].v)
                num_nodes = edges[i-1].u;
Ivaylo Ivanov's avatar
Ivaylo Ivanov committed
86 87
        }
    }
88 89
    num_nodes++; ///< Our first node is labeled 0, so we need to add 1 more

Ivaylo Ivanov's avatar
Ivaylo Ivanov committed
90
    /// Declare array for unique nodes
91 92 93 94 95 96 97
    int unique_nodes[num_nodes];

    /// Filling the node array with the nodes
    for(int i=0; i < num_nodes; i++) {
        unique_nodes[i] = i;
    }

98
    /// Allocate resources for circular buffer
99
    int wr_pos = 0;
100
    buffer_shmfd = create_shmfd(BUFF_SHM_NAME);
101 102
    circ_buffer = (buffer_t *)open_shm(buffer_shmfd, sizeof(buffer_t));

103 104 105 106
    /// Open semaphores
    free_sem = open_sem(FREE_SEM_NAME, BUFF_SIZE, 1);
    use_sem = open_sem(USE_SEM_NAME, 0, 1);
    mutex = open_sem(MUTEX_NAME, 1, 1);
107

Ivaylo Ivanov's avatar
Ivaylo Ivanov committed
108 109
    /// Declaring buffer arrays and variables
    int current_best = num_edges - 1; ///< Set a basic best solution
Ivaylo Ivanov's avatar
Ivaylo Ivanov committed
110
    int new_best = 0;
111
    int buf_nodes[num_nodes];
Ivaylo Ivanov's avatar
Ivaylo Ivanov committed
112
    edge_t buf_edges[num_edges];
113

Ivaylo Ivanov's avatar
Ivaylo Ivanov committed
114
    while(terminate != true && circ_buffer -> finished != true) { ///< Loop until told to stop or until an acyclic solution is discovered
115 116 117 118
        /// Copy the original into a buffer array and shuffle it
        memcpy(buf_nodes, unique_nodes, sizeof(unique_nodes));
        shuffle(buf_nodes, num_nodes);

Ivaylo Ivanov's avatar
Ivaylo Ivanov committed
119 120 121
        /// Reset the chosen status of the edges
        memcpy(buf_edges, edges, sizeof(edges));

Ivaylo Ivanov's avatar
Ivaylo Ivanov committed
122
        new_best = 0; ///< Reset the new_best counter
Ivaylo Ivanov's avatar
Ivaylo Ivanov committed
123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138
        for(int i=0; i < num_edges; i++) {
            if(new_best >= SET_MAX_SIZE || new_best >= num_edges)
                break; ///< Skip if the solution is faulty

            for(int j=0; j < num_nodes; j++) {
                if(buf_nodes[j] == edges[i].u)
                    break; ///< The first node comes before the second, break
                else if(buf_nodes[j] == buf_edges[i].v) {
                    buf_edges[i].chosen = true; ///< Found a correct edge, mark it as chosen
                    new_best++;
                    break;
                }
            }
        }

        /// Construct the new feedback arc set
Ivaylo Ivanov's avatar
Ivaylo Ivanov committed
139
        if(new_best < current_best && new_best <= SET_MAX_SIZE && current_best < circ_buffer -> best_arc_len) {
Ivaylo Ivanov's avatar
Ivaylo Ivanov committed
140
            current_best = new_best;
Ivaylo Ivanov's avatar
Ivaylo Ivanov committed
141 142 143 144 145 146

            fb_arc_set_t res;
            memset(&res, 0, sizeof(struct fb_arc_set)); /// Removes faulty data from the buffer later
            for(int i=0; i < num_edges; i++) {
                if(buf_edges[i].chosen == true) {
                    res.edge_num++;
147
                    res.edges[--new_best] = buf_edges[i]; ///< We begin counting from 0
Ivaylo Ivanov's avatar
Ivaylo Ivanov committed
148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167
                }
            }
            res.valid = true;

            wait_sem(mutex); ///< Say that it's our turn to write
            wait_sem(free_sem); ///< Lock the free space semaphore

            /// Find a free space to write to
            while(circ_buffer->sets[wr_pos].valid == true) {
                wr_pos = (wr_pos + 1) % BUFF_SIZE;
            }
            circ_buffer->sets[wr_pos] = res;

            post_sem(use_sem);
            wr_pos = (wr_pos + 1) % BUFF_SIZE;
            post_sem(mutex);

            if(current_best == 0) {
                signal_handler(15);
            }
Ivaylo Ivanov's avatar
Ivaylo Ivanov committed
168
        }
169
    }
170
    exit(EXIT_SUCCESS);
171
}
172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192

/**
 * @brief Function that swaps a two variables
 * @details The function takes pointers to two variables and swaps their values with a buffer variable
 * @param *a, *b
 * @return none
 **/
void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

/**
 * @brief Function that shuffles a given array
 * @details The function takes an array and shuffles it randomly using the Fisher-Yates algorithm:
 *          https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle
 * @param arr, size
 * @return res
 **/
void shuffle(int arr[], size_t size) {
Ivaylo Ivanov's avatar
Ivaylo Ivanov committed
193 194
    base_seed = (base_seed + 1) % (__UINT64_MAX__); ///< Extreme values for the randomizer
    srand(base_seed); ///< Set a random seed
195 196 197 198 199 200 201

    int j = 0; ///< Index that will be randomized later on
    for(int i = size - 1; i > 0; i--) {
        j = rand()%(i+1); ///< Pick a random index
        swap(&arr[i], &arr[j]); ///< Swap the values
    }
}