Karger Min Cut

karger_min_cut.c

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <ctype.h>

#define NROWS 200
#define NCOLS 100

int a[NROWS][NCOLS], v[NROWS], n, m;

struct edge {
    int x;
    int y;
}edges[NROWS*NCOLS];

void swap(struct edge *e1, struct edge *e2)
{
    struct edge tmp;
    tmp.x = e1->x;
    tmp.y = e1->y;
    e1->x = e2->x;
    e1->y = e2->y;
    e2->x = tmp.x;
    e2->y = tmp.y;
}

void prepare(const char *file)
{
    FILE *fp;
    int i, j;
    char buf[BUFSIZ];

    if ((fp = fopen(file, "r")) == NULL) {
        fprintf(stderr, "Could not open file %s\n", file);
        exit(1);
    }
    for (i = 0; i < NROWS; i++) {
        char *tmp;
        int num;
        if (fgets(buf, sizeof(buf) - 1, fp) == NULL)
            break;
        tmp = buf;
        j = 0;
        while (*tmp != '\0' && j < NCOLS) {
            while (isspace(*tmp))
                tmp++;
            num = 0;
            while (isdigit(*tmp)) {
                num = num * 10 - '0' + *tmp;
                tmp++;
            }
            a[i][j] = num;
            j++;
            while (isspace(*tmp))
                tmp++;
        }
    }
    n = i;
}

void graph(void)
{
    int i, j, current_v;
    for (i = 0; i < NROWS; i++)
        v[i] = 0;
    m = 0;
    for (i = 0; i < n; i++) {
        current_v = a[i][0];
        v[current_v] = 1;
        for (j = 1; a[i][j] > 0; j++) {
            if (v[a[i][j]] != 1) {
                edges[m].x = current_v;
                edges[m].y = a[i][j];
                m++;
            }
        }
    }
}

int get_edge(void)
{
    return rand() % m;
}

void merge(int a, int b)
{
    int i;
    v[b] = 0;
    for (i = 0; i < m; i++) {
        if (edges[i].x == b)
            edges[i].x = a;
        if (edges[i].y == b)
            edges[i].y = a;
    }
}

void clean(void)
{
    int i;
    for (i = 0; i < m; i++)
        if (edges[i].x == edges[i].y)
            swap(&edges[i], &edges[--m]);
}

int karger(void)
{
    int r;
    int tmp = n;
    while (tmp > 2) {
        r = get_edge();
        merge(edges[r].x, edges[r].y);
        clean();
        tmp--;
    }
    clean();
}

int karger_min_cut(const char *file)
{
    int i, min = 0;
    unsigned long iters = n * n * 8;
    for (i = 0; i < iters; i++) {
        srand(time(NULL));
        graph();
        karger();
        if (min == 0 || min > m)
            min = m;
    }
    return min;
}

int main(int argc, char **argv)
{
    int min, i, j;
    if (argc != 2) {
        fprintf(stderr, "usage: %s\n", argv[0]);
        exit(1);
    }
    prepare(argv[1]);

    min = karger_min_cut(argv[1]);
    printf("%d\n", min);

    /*graph();
    karger();
    printf("%d\n", m);*/

    exit(0);
}