PQ-3

#include <stdio.h>
#include <stdlib.h>//strtol,srand,rand
#include <time.h>//time
#include <assert.h>//assert
#include <limits.h>//INT_MAX

#include <vector>

#define MAX_VERTEX 41
#define MAX_LINE 30


std::vector< std::vector<int> > V(MAX_VERTEX);
std::vector< std::vector<int> > BV(MAX_VERTEX);//Backup;
int sum_of_vertices;
const char dataFile[] = "kargerAdj.txt";//"./"hw3/test2b2.txt";//"./"hw3/n8m14_2.txt";//"./"hw3/adjList08m1.txt";//"kargerAdj.txt";
//From https://github.com/franciscopassos/coursera-algo-class-2012-hw_unittests
//[TEST_CASES][]
const int Ctest_cases = 34;
const char testCases[][MAX_LINE] = {"hw3/adjList01m1.txt|1",
"hw3/adjList02m2.txt|2",
"hw3/adjList03m1.txt|1",
"hw3/adjList04m1.txt|1",
"hw3/adjList05m2.txt|2",
"hw3/adjList06m3.txt|3",
"hw3/adjList07m1.txt|1",
"hw3/adjList08m1.txt|1",
"hw3/adjList09m1.txt|1",
"hw3/adjList10m2.txt|2",
"hw3/n3m3_2.txt|2",
"hw3/n3m5_2.txt|2",
"hw3/n4m5_2.txt|2",
"hw3/n4m6_3.txt|3",
"hw3/n5m5_2.txt|2",
"hw3/n8m14_2.txt|2",
"hw3/test0_m3.txt|3",
"hw3/test0_m5.txt|5",
"hw3/test1.2.txt|2",
"hw3/test1bm3.txt|3",
"hw3/test1_m5.txt|5",
"hw3/test1_m6.txt|6",
"hw3/test2.4.txt|4",
"hw3/test2b2.txt|2",
"hw3/test2_m5.txt|5",
"hw3/test2_m7.txt|7",
"hw3/test3.1.txt|1",
"hw3/test3_m3.txt|3",
"hw3/test4.3.txt|3",
"hw3/test4_m5.txt|5",
"hw3/test5_m4.txt|4",
"hw3/test6_m4.txt|4",
"hw3/test7_m4.txt|4",
"hw3/test8_m3.txt|3",
"hw3/test9_m4.txt|4"};

void print_graph_data() {
    for (unsigned i=0; i<V.size() ; i++)
        for (unsigned j=0; j<V[i].size() ; j++)
            printf("Vertex: %d; Adjacent vertex: %d\n", i, V[i][j]);
    puts("");
}

void read_data(const char dataFile[]) {
    sum_of_vertices = 0;//Set initial value to global variable
    FILE * pFile = fopen(dataFile, "r");
    if ( pFile == NULL ) perror("Error opening file");
    else
    {
        //http://stackoverflow.com/questions/2287121/how-to-read-integers-from-a-file-line-by-line-in-c
        //http://webstaff.itn.liu.se/~kenbj/tng033/www.cppreference.com/index.html
        //http://www.gnu.org/software/libc/manual/html_node/Parsing-of-Integers.html
        //http://www.gnu.org/software/libc/manual/html_node/Creating-a-Pipe.html#Creating-a-Pipe
        //http://stackoverflow.com/questions/2287121/how-to-read-integers-from-a-file-line-by-line-in-c
        //http://tldp.org/LDP/lpg/node11.html
        char line[1024], *p, *e = NULL;
        int number;
        while ( fgets(line, sizeof(line), pFile) ) {
            int vertex = -1;

            //maybe TODO: create pipe and scan with fscanf
            for (p = line;
                (number = strtol(p, &e, 10)) > -1 && p != e;/* scan and check do "e" moved to new place*/ // "> -1" is for nothing...
                p = e /*last place where we were*/) {
                if(vertex == -1) {
                    vertex = number;
                    ++sum_of_vertices;
                } else {
                    //printf("%d %d\n", vertex, number);
                    //assert(number );
                    V[vertex].push_back(number);
                    assert(vertex != number);//Because in my implementation of algorithm it is not checked before first iteration
                }
                //printf("%d ", number);
            }
            //puts("");
        }
        fclose (pFile);
    }
    //print_graph_data();//If needs to print graph
}

int pick_vertex() {
    int picked_vertex;// = -1;
    do {
        picked_vertex = rand() % V.size();
    } while ( V[picked_vertex].empty() );
    return picked_vertex;
}
int pick_vertex_neighbour(int vertex_id) {
    int picked_vertex_neighbour;
    do {
        picked_vertex_neighbour = rand() % V[vertex_id].size();
        //printf("b");
    } while ( vertex_id == V[vertex_id][picked_vertex_neighbour] );
    return V[vertex_id][picked_vertex_neighbour];
}

int minimum_cut() {
    std::vector<int>::iterator it;
    while (sum_of_vertices > 2) {
        //pick a remaining edge (u,v) uniformly at random
        int vertex_id = pick_vertex();//u
        assert( !V[vertex_id].empty() );
        //printf("u%2d", vertex_id);
        int vertex_neighbour_val = pick_vertex_neighbour(vertex_id);//v
        //printf(" v%2d", vertex_neighbour_val);


        //Line below don't change anything to results...
        //if(1 == rand() % 2) swap(vertex_neighbour_val, vertex_id);

        //less vertices is result of merge process
        --sum_of_vertices;

        //merge (or "contract") u and v into a single vertex
        //merge to vertex_neighbour_val. Maybe would be better to merge into vertex_id?
        while( !V[vertex_id].empty() ) {
            //int last_element_val = V[vertex_id].back(); // Get value
            //if( last_element_val != vertex_neighbour_val && last_element_val != vertex_id)
            //  V[vertex_neighbour_val].push_back( last_element_val );
            //printf(" %d", last_element_val);
            V[vertex_neighbour_val].push_back( V[vertex_id].back() );
            V[vertex_id].pop_back(); // Remove
            //printf("d");
        }
        assert( V[vertex_id].empty() );

        //Change secondary vertex edges "indexes" to merged primary vertex index
        //Could be even more straight forward (less cost) if I make not through all verteces, but through all vertex edges in above cycle
        for (unsigned int i=0; i < V.size(); i++ )
            for (unsigned int j=0; j < V[i].size(); j++ )
                if(V[i][j] == vertex_id)
                    V[i][j] = vertex_neighbour_val;

        //remove self-loops
        for ( it=V[vertex_neighbour_val].begin() ; it < V[vertex_neighbour_val].end();  )
            if(*it == vertex_neighbour_val)
                //printf(" d%d", *it);
                    it = V[vertex_neighbour_val].erase(it);
            else it++;
        //puts("");
    }

    //return cut represented by final 2 vertices.
    unsigned int min = INT_MAX;
    for (unsigned i=0; i<V.size() ; i++)
            if( !V[i].empty() ) {
                //return V[i].size();
                //printf("%d %d\n", i, V[i].size());
                if(V[i].size() < min)
                    min = V[i].size();
            }

    return (int)min;
}

void test_cases(const char testcases[][MAX_LINE]) {
    char data_file[1024];
    int correct_answer;
    for(int i=0; i<Ctest_cases; i++) {
        sscanf(testCases[i], "%[^|]|%d", data_file, &correct_answer);
        printf("File: %s", data_file);

        int min = INT_MAX;
        read_data(data_file);
        int Bsum_of_vertices = sum_of_vertices;
        BV = V;
        for(int i=0; i<10000; i++) {

            //Copy of backup input
            V.clear();
            V.resize(MAX_VERTEX);
            V = BV;
            sum_of_vertices = Bsum_of_vertices;

            int curr = minimum_cut();
            if(curr < min)
                min = curr;
        }
        //assert(min == correct_answer);
        if(min != correct_answer)
            printf("\tcorrect: %d; current: %d;", correct_answer, min);
        else
            printf("\tOK");
        puts("");
    }
}

int main() {
    int min = INT_MAX;
    read_data(dataFile);
    int Bsum_of_vertices = sum_of_vertices;
    BV = V;
    int correct_count=0;//Correct answer counter
    srand ( time(NULL) );
    for(int i=0; i<10000; i++) {

        //Copy backup of input
        V.clear();
        V.resize(MAX_VERTEX);
        V = BV;
        sum_of_vertices = Bsum_of_vertices;

        int curr = minimum_cut();
        if(curr < min)
            min = curr;
        if(curr == 3) ++correct_count;
    }
    printf("PQ-3 min: %d.\n",  min);
    printf("Correct times: %d.\n",  correct_count);

    test_cases(testCases);

    return 0;
}