karger Minimum Cut algo crashes for big input

Question

I try to implement the karger Minimum Cut algorithm (Karger wiki page)

So far, I have tried my algorithm on small examples (input of size 10) and it seems to work. But when I try to have a bigger input, let's say 200. It just crashes.

To store the minimum cut data, I create a 2D array: GraphCut[SIZE_ARRAY][SIZE_ARRAY_2] SIZE_ARRAY = 200 in this case, but I can't find a good length for SIZE_ARRAY_2.

Issue is, SIZE_ARRAY_2 has to be big as I modify the initial array to merge the different vertices.

If I declare SIZE_ARRAY_2 = 200, the size won't be enough, but if i put SIZE_ARRAY_2 = 1000, the program just crashes.

The thing is, I have to execute the algorithm 100000 times.

Here is parts of the code:

#define ARRAY_SIZE 200
#define ARRAY_SIZE_2 200

int main()
{
    int minCut,minMinCut;

    for (int k = 0; k < ARRAY_SIZE * ARRAY_SIZE * 4;k++) {
        minCut = kargerMinCut(k);
        if (k == 0)
            minMinCut = minCut;
        else if (minMinCut > minCut)
            minMinCut = minCut;
    }
    printf("\n minMinCut = %d\n", minMinCut);

    return 0;
}

int kargerMinCut(int k) {
// 1st dimension: each different node
// 2nd dimension: vertices
    long graphCut[ARRAY_SIZE + 1][ARRAY_SIZE_2] = {0};
    populateIntegerArray(graphCut); // import data from a file

    int nodeToMain[ARRAY_SIZE + 1];
    int sizeOfMainNode, indexToMerge,initialRand,i,j,m,nodeToMerge,nodeRemaining = ARRAY_SIZE;
    for (m = 0;m<ARRAY_SIZE + 1;m++) // initialization of nodeToMain
        nodeToMain[m] = m;

    while (nodeRemaining > 2) {
i = 0;
        j = 0;
        srand(time(NULL) + nodeRemaining);// initialise rand
        initialRand = nodeToMain[rand()%(ARRAY_SIZE) + 1]; // pick a random initial node, but not a merged one
        sizeOfMainNode = sizeOfArray(graphCut[initialRand]); // size of the initial node

        srand(time(NULL) + k); // initialise rand
        indexToMerge = rand()%sizeOfMainNode;// pick another random node in the linked nodes (its index to be precise)
        nodeToMerge = nodeToMain[graphCut[initialRand][indexToMerge]];

        for (m = 0;m<ARRAY_SIZE + 1;m++)  // update the nodeToMain array, initialRand is now the main node for nodeToMerge
            if (nodeToMain[m] == nodeToMerge)
                nodeToMain[m] = initialRand;

        // remove the nodeToMerge numbers from the graphCut[initialRand] (as they are going to be merged)
        while(graphCut[initialRand][j] > 0 && j < sizeOfMainNode) {
            if (initialRand == nodeToMain[graphCut[initialRand][j]]) {
                // if this is the last element, do nothing
                while(nodeToMain[graphCut[initialRand][sizeOfMainNode - 1]] == initialRand && j < sizeOfMainNode - 1) {
                    graphCut[initialRand][sizeOfMainNode - 1] = 0;
                    sizeOfMainNode--;
                }
                graphCut[initialRand][j] = nodeToMain[graphCut[initialRand][sizeOfMainNode - 1]];
                graphCut[initialRand][sizeOfMainNode - 1] = 0;
                sizeOfMainNode--;
            }
            j++;
        }

        i = 0;
        while (graphCut[nodeToMerge][i] > 0 && sizeOfMainNode < ARRAY_SIZE_2 && i < ARRAY_SIZE_2) { // add each vextex of the nodeTomerge to the merged nodes
            if (nodeToMain[graphCut[nodeToMerge][i]] != initialRand) {
                graphCut[initialRand][sizeOfMainNode] = nodeToMain[graphCut[nodeToMerge][i]];
                sizeOfMainNode++;
            }
            i++;
        }

        nodeRemaining--;
    }

    return sizeOfArray(graphCut[nodeToMain[1]]);
}

I'm sure that the code is not really clean, maybe even really bad (beginner in C). So i Welcome any other advice.

The errors I get with the debugger seems really random. Error is:

Impossible to divide by 0

it stops in time64.c at line 62

tim = (__time64_t)((nt_time.ft_scalar - EPOCH_BIAS) / 10000000i64);

Answer 1

The change in array size is probably causing a stack overflow. A common default size for the stack is 1MB (1048576 bytes). If you have:

long graphCut[200][1000];

and 4 == sizeof(long) the graphCut array is taking up 200 * 1000 * 4 = 800000 bytes, which leaves 248576 bytes which may not be enough for the stack variables in populateIntegerArray() function (I don't see that function). If 8 == sizeof(long) then the array would require 1600000 bytes, which is greater than 1MB.

If an array of that size is required then allocate (all or part) on the heap instead of the stack. For example:

long* graphCut[ARRAY_SIZE_1];
int i;
for (i = 0; i < sizeof(graphCut)/sizeof(graphCut[0]); i++)
{
    graphCut[i] = malloc(ARRAY_SIZE_2 * sizeof(graphCut[0][0]));
    memset(graphCut[i], 0, ARRAY_SIZE_2 * sizeof(graphCut[0][0]));
}

for (i = 0; i < sizeof(graphCut)/sizeof(graphCut[0]); i++)
{
    free(graphCut[i]);
}

Answer 2

Some possible problems are integer or stack overflow (so you're on the right site) and memory initialization.

This implementation should allocate graphCut on the heap, and zero it every time kargerMin gets called, thus addressing those problems.

int minCut, minMinCut;
    // There is a small possibility that ARRAY_SIZE*ARRAY_SIZE*4 exceeds int boundary if 16-bit
    long k;
    long **buffer;
// Allocate graphCut on the heap
buffer = malloc((ARRAY_SIZE + 1)*sizeof(long *));
for (k = 0; k < ARRAY_SIZE + 1; k++)
    buffer[k] = malloc(ARRAY_SIZE_2*sizeof(long));

for (k = 0; k < ARRAY_SIZE * ARRAY_SIZE * 4;k++) {
    minCut = kargerMinCut(k, buffer);
    if (k == 0)
        minMinCut = minCut;
    else if (minMinCut > minCut)
        minMinCut = minCut;
}
printf("\n minMinCut = %d\n", minMinCut);

// Here we free the buffer. We could do it in any order, but
// as it costs nothing here to do so, we free it in reverse-
// allocation-order to avoid any possible memory fragmentation
// - which is moot anyway, if this is a main() and we're exiting
// the program. In other instances it could be relevant.
for (k = 0; k < ARRAY_SIZE + 1; k++)
{
    free(buffer[ARRAY_SIZE-k]); buffer[ARRAY_SIZE-k] = NULL;
}
free(buffer); buffer = NULL;
// The NULLing of the just-freed variables has no purpose except
// to GUARANTEE that any illegal use of them, dangling pointers,
// leftover copies etc. will immediately trigger a core dump and
// be discovered, instead of lurking undetected.

return 0;
}

int kargerMinCut(long k, long **graphCut) {
    // 1st dimension: each different node
    // 2nd dimension: vertices

    // Zero graphCut. If populateIntegerArray rewrites
    // the whole of graphCut, these four lines are redundant.
    int     i, j;
    for (i = 0; i < ARRAY_SIZE + 1; i++)
            for (j = 0; j < ARRAY_SIZE_2; j++)
                    graphCut[i][j] = 0;
    // otherwise, they make sure that no old value of graphCut
    // or uninitialised value is going to linger and potentially
    // corrupt calculations later on.
    populateIntegerArray(graphCut); // import data from a file

Answer 3

I have implemented the Karger algorithm in C++. My code below works on large files but I have not optimized enough...it still runs fast though..but could be faster..Try this solution.

#include "stdafx.h"
#include <iostream>
#include <stdio.h>
#include <string>
#include <map>
#include <list>
#include <fstream>
#include <sstream>
#include <set>
#include <stdlib.h>
#include <time.h>

int pick_edge(std::map <int, std::list<int>> g2, set<int> myset, int &u, int &v)
{
    std::map <int, std::list<int>>::iterator it;
    std::list<int> eachRow;

    int rand_vertex;
    int rand_edge;

    srand (time(NULL));

    rand_vertex = (rand() + 1) % myset.size() ;
    if (rand_vertex == 0)
        rand_vertex = 1;
    u = get_value_at_i(myset, rand_vertex);

    for (it = g2.begin(); it != g2.end(); ++it) {
        if (it->first == u) {
            eachRow = it->second;
            rand_edge = (rand() + 1) % eachRow.size();
            if (rand_edge == 0)
                rand_edge = 1;
            v = get_edge_at_j(eachRow, rand_edge);
            break;
        }
    }
    return 0;
}




map <int, std::list<int>> merge_uv(map <int, std::list<int>>  g2, int u, int v)
{
    std::map <int, std::list<int>>::iterator it_g;
    std::map <int, std::list<int>>::iterator it_u;
    std::map <int, std::list<int>>::iterator it_v;
    std::list<int>::iterator iter_l;

    std::list<int> eachRow, uRow, vRow;
    std::list<int> newRow;
    int vertex;
    int j = 0;

    map <int, std::list<int>> new_Graph_G;
    vRow.clear();
    uRow.clear();
    eachRow.clear();
    newRow.clear();

    for (it_g = g2.begin(); it_g != g2.end(); ++it_g) {
        vertex = it_g->first;
        eachRow = it_g->second;

        if (vertex == u) {
            uRow = it_g->second;

            it_u = it_g;
            j++;
            continue;
        }
        if (vertex == v) {
            vRow = it_g->second;
            it_v = it_g;
            j++;
            continue;
        }
    }
    if (j == 2) {
        uRow.sort();
        vRow.sort();
        //      uRow.merge(vRow);
        for (std::list<int>::iterator ite = vRow.begin(); ite != vRow.end();  ++ite) {
            if (*ite != u) {
                uRow.push_back(*ite);
            }
        }
        g2.erase(v);
        g2[u] = uRow;
    }

    for (it_g = g2.begin(); it_g != g2.end(); ++it_g) {
        eachRow = it_g->second;
        for (std::list<int>::iterator ite = eachRow.begin(); ite != eachRow.end();  ++ite) {
            if (*ite == v && *ite != it_g->first) {
                newRow.push_back(u);
            } else if (*ite == it_g->first) {
                continue;
            }   else {
                newRow.push_back(*ite);
            }
        }
        new_Graph_G[it_g->first] = newRow;
        newRow.clear();
    }

    for (it_g = g2.begin(); it_g != g2.end(); ++it_g) {
        eachRow = it_g->second;
        if (it_g->first == u) {
            for (std::list<int>::iterator ite = eachRow.begin(); ite != eachRow.end();  ++ite) {
                if (*ite != u && *ite != v) {
                    newRow.push_back(*ite);
                }
            }
            new_Graph_G[it_g->first] = newRow;
            break;
        }
    }

    return new_Graph_G;
}

int get_min_cut(std::map <int, std::list<int>> g1)
{
    int v;
    std::list<int> eachRow;
    std::map <int, std::list<int>>::iterator it_g;
    int min_cut = 0;

    for (it_g = g1.begin(); it_g != g1.end(); ++it_g) {
        eachRow = it_g->second;
        v = it_g->first;
        for (std::list<int>::iterator ite = eachRow.begin(); ite != eachRow.end();  ++ite) {
            if (*ite != v) {
                min_cut++;
            }
        }
        break;
    }

    return min_cut;
}


int EdgeContractionAlgorithm()
{
    std::map <int, std::list<int>>::iterator it;
    int min_cut = 0;
    int vertex = 1;
    std::list<int> eachRow;
    std::set<int> myset;
    std::set<int>::iterator itSet;
    std::map <int, std::list<int>> g2;

    int edge;
    int n_vertices;
    int cnt = 0;
    int u, v;

    n_vertices = Cal_nVertices(myset, Graph_G);
    g2 = Graph_G;

    // Contraction algorithm.
    while (n_vertices > 2) {
        edge = pick_edge(g2, myset, u, v);
        g2 = merge_uv(Graph_G, u, v);

        n_vertices = g2.size();
        myset.erase (myset.find(v));
        Graph_G = g2;
    }

    print_graph(g2);

    min_cut = get_min_cut(g2);
    return (min_cut);
}