generator.c 6.88 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);
37 38

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

45 46
    process_signal();

47
    /// Create a regex to check the input against
Ivaylo Ivanov's avatar
Ivaylo Ivanov committed
48 49 50 51 52 53
    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);
    }

54 55
    int num_edges = argc - 1;
    edge_t edges[num_edges]; ///< Array to hold all edges
56 57 58 59

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

60 61
    int num_nodes = 0;
    for(int i=1; i <= num_edges; i++) {
62
        /// Check the input and terminate if incorrect
Ivaylo Ivanov's avatar
Ivaylo Ivanov committed
63 64 65 66
        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);
67 68 69 70 71 72 73
        } 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
74
            edges[i-1].chosen = false;
75 76 77 78 79

            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
80 81
        }
    }
82 83
    num_nodes++; ///< Our first node is labeled 0, so we need to add 1 more

Ivaylo Ivanov's avatar
Ivaylo Ivanov committed
84
    /// Declare array for unique nodes
85 86 87 88 89 90 91
    int unique_nodes[num_nodes];

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

92
    /// Allocate resources for circular buffer
93
    int wr_pos = 0;
94
    buffer_shmfd = create_shmfd(BUFF_SHM_NAME);
95 96
    circ_buffer = (buffer_t *)open_shm(buffer_shmfd, sizeof(buffer_t));

97 98 99 100
    /// 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);
101

Ivaylo Ivanov's avatar
Ivaylo Ivanov committed
102 103
    /// Declaring buffer arrays and variables
    int current_best = num_edges - 1; ///< Set a basic best solution
Ivaylo Ivanov's avatar
Ivaylo Ivanov committed
104
    int new_best = 0;
105
    int buf_nodes[num_nodes];
Ivaylo Ivanov's avatar
Ivaylo Ivanov committed
106
    edge_t buf_edges[num_edges];
107

Ivaylo Ivanov's avatar
Ivaylo Ivanov committed
108
    while(terminate != true && circ_buffer -> finished != true) { ///< Loop until told to stop or until an acyclic solution is discovered
109 110 111 112
        /// 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
113 114 115
        /// Reset the chosen status of the edges
        memcpy(buf_edges, edges, sizeof(edges));

Ivaylo Ivanov's avatar
Ivaylo Ivanov committed
116
        new_best = 0; ///< Reset the new_best counter
Ivaylo Ivanov's avatar
Ivaylo Ivanov committed
117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132
        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
133
        if(new_best < current_best && new_best <= SET_MAX_SIZE && current_best < circ_buffer -> best_arc_len) {
Ivaylo Ivanov's avatar
Ivaylo Ivanov committed
134
            current_best = new_best;
Ivaylo Ivanov's avatar
Ivaylo Ivanov committed
135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161

            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++;
                    res.edges[--new_best] = edges[i]; ///< We begin counting from 0
                }
            }
            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
162
        }
163
    }
164
    exit(EXIT_SUCCESS);
165
}
166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195

/**
 * @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) {

    srand(time(NULL)); ///< Set a random seed

    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
    }
}