Karger's Random Contraction Algorithm for Min Graph Cuts

RandomContraction.cpp

#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <sstream>
#include <random>
#include <assert.h>
#include <algorithm>
#include <time.h>
using namespace std;

// read from file with adjacency list representation of undirected graph
void getFromtxt(char *name, vector<vector<int> >&graph)
{
    ifstream input;
    input.open(name);//read from a txt file
    if(input.is_open())
    {
        int num=0;
        std::string line;
        graph.push_back(vector<int>());// graph index begin with 1 not 0
        while (std::getline(input, line))
        {
            std::istringstream streamline(line);
            graph.push_back(vector<int>());
            while(streamline>>num)
                graph.back().push_back(num);
        }
    }
}

class  RandomContraction
{
	// graph vertex index begin with 1 ,let zero index empty .
public:
    RandomContraction(vector<vector<int> >&graph)
    {
        this->graph=graph;
    }
    int minCut(int seed=1)
    {
        while(graph.size()>3)
            edgeContraction(seed);

        return graph[1].size()-1;
    }
    void edgeContraction (int seed)
    {
	time_t seconds;
	time(&seconds);
	srand((unsigned int) seconds*seed-graph.size());
    //choose a random edge
    int node=1+rand()%(graph.size()-1);
    int edge=1+rand()%(graph[node].size()-1);

    //node to be merged
    int _node=graph.at(node).at(edge);
		
	while(_node==node)
	{
		edge=1+rand()%(graph[node].size()-1);
		_node=graph.at(node).at(edge);
		
	}

    //do merge ,replace _node with node
    for(int i=0;i<graph.size();++i)
        for(int j=0;j<graph.at(i).size();++j)
        {
    		if(graph.at(i).at(j)>=_node)
    		{
    			if(graph[i][j]==_node)
    				graph[i][j]=_node>node?node:(node-1);//correct the index ,if node>_node ,node will decrease one.
    			else if(graph[i][j]>_node)
    				--graph[i][j];
    		}
        }
    //add _node's edge to node and remove _node
    for(int i=1;i<graph[_node].size();++i)
        graph.at(node).push_back(graph[_node].at(i));

	//clear self cycle
	vector<int>::iterator i=std::remove(graph[node].begin()+1, graph[node].end(), _node>node?node:(node-1));
	graph[node].erase( i,graph[node].end());
	//remove merged _node
	graph.erase(graph.begin()+_node);
    }

private:
    vector<vector<int> > graph;

};

int main(int argv,char **argc)
{
    vector<vector<int> > graph;
    getFromtxt("kargerMinCut.txt",graph);
    //for(int i=0;i<graph.size();++i)
    //{
    //    for(int j=0;j<graph[i].size();++j)
    //        cout<<graph[i][j]<<" ";
    //    cout<<endl;
    //}
    int minum=200;
	for(int i=200;i>0;i--)
	{
	    RandomContraction con(graph);
		int cut=con.minCut(i);
		cout<<endl<<cut;
		minum=min(minum,cut); 
	}
	cout<<"minum:"<<minum<<endl;
	system("pause");
	return 0;
}

Download the text file here. (Right click and save link as)
The file contains the adjacency list representation of a simple undirected graph. There are 200 vertices labeled 1 to 200. The first column in the file represents the vertex label, and the particular row (other entries except the first column) tells all the vertices that the vertex is adjacent to. So for example, the 6th row looks like : "6 155 56 52 120 ......". This just means that the vertex with label 6 is adjacent to (i.e., shares an edge with) the vertices with labels 155,56,52,120,......,etc

Your task is to code up and run the randomized contraction algorithm for the min cut problem and use it on the above graph to compute the min cut. (HINT: Note that you'll have to figure out an implementation of edge contractions. Initially, you might want to do this naively, creating a new graph from the old every time there's an edge contraction. But you should also think about more efficient implementations.) (WARNING: As per the video lectures, please make sure to run the algorithm many times with different random seeds, and remember the smallest cut that you ever find.) Write your numeric answer in the space provided. So e.g., if your answer is 5, just type 5 in the space provided.