Kargers Min cut algorithm

[hasslersteph]

Hi,

I have been coding in C++ since in a month and not completely familiar with the errors and bugs encountered (I am a mechanical engineer). I have tried to implement a algorithm to find the cuts in a graph. It works well sometimes and doesn't work that well on other times. Hence, I am not able to identify the exact problem. I obviously don't expect you to go through the code and find the mistake for me. I tried debugging in Codeblocks but could not identify the problem from the call stack etc. since a couple of days.

If someone could just run the code on their machine, and tell me which line is problematic, that would be really helpful. can then identify the mistake and fix it on my own. The link to the data file used is - https://drive.google.com/open?id=17j8tcC7dTQS51d5z5MOp_dVpliLdmqg7

Thanks a ton for your help in advance.

// Program for graphs and minimum cut

#include <iostream>
#include <fstream>
#include <vector>
#include <sstream>
#include <string>
#include <algorithm>
#include <cstdlib>



using namespace std;
typedef vector< vector<int> > gra;
typedef vector<int> gra1;
int merge(gra &a, int i, int j);
void printvector(gra a);
int nonzeronodes(gra &a);

int main()
{
    vector< vector<int> > graph;
    ifstream file("data.txt");


    string lineString;
    gra1 nodelist;

    for(int i=0;i<200;i++){
        nodelist.push_back(i);
        getline(file, lineString);
        stringstream line(lineString);
        int currentNode;
        line >> currentNode;
        int currentAdjacentNode;

        graph.push_back(vector<int>());
        while(line >> currentAdjacentNode){
            graph[i].push_back(currentAdjacentNode);
            //cout<<currentAdjacentNode<<endl;
        }
    }
    vector<vector<int> >::iterator it=graph.begin();
    printvector(graph);
    int nodes=5;
    int iteration=0;
    int node1=nonzeronodes(graph);int node1Neighbor=1;
    gra1 nodeslist;

    while(nodes>2){

        cout<<"NODE USED IS  "<<node1<<endl;
        nodes=merge(graph,node1,node1Neighbor);
        iteration+=1;
        cout<<"The number of iterations is  "<<iteration<<endl;
        node1=nonzeronodes(graph);

        //printvector(graph);
        cout<<"iteration ended"<<endl;

        cout<<endl;

    }
    //cout<<"Before second merge call"<<endl;
    printvector(graph);

    cout<<"the number of active nodes is = "<<nodes<<endl;

    return 0;

}


int merge(gra &a, int i, int j){

// i - node number....j- jth neighbour of i

gra::iterator aBegin=a.begin();// pointer to first vector
gra1::iterator iRow=(aBegin+(i-1))->begin(); //pointer to ith row
int neighbor=*(iRow+j-1);
//cout<<"The neighbor is  "<<neighbor<<endl;
// DELETE NEIGHBOR FROM I;
//(aBegin+(i-1))->erase(iRow+j-1);
int seen=0;
while(iRow!=(a.begin()+(i-1))->end()){
    seen+=1;
    if(*(iRow)==neighbor){
        (a.begin()+(i-1))->erase(iRow);
        iRow=((a.begin()+(i-1))->begin())+seen-1;
        seen-=1;
    }
    else{iRow+=1;;}
}

//cout<<"AFTER DELETING NEIGHBOR"<<endl;

//printvector(a);
gra1::iterator neighborRow=(aBegin+(neighbor-1))->begin(); //pointer to neighbor row
gra1::iterator neighborRowEnd=(aBegin+(neighbor-1))->end(); //pointer to neighbor row end


//PUSH BACK NEIGHBORS MEMBER INTO I
neighborRow=(aBegin+(neighbor-1))->begin(); //pointer to neighbor row
neighborRowEnd=(aBegin+(neighbor-1))->end(); //pointer to neighbor row end

for(neighborRow;neighborRow!=neighborRowEnd;neighborRow++){

    int pushback=*(neighborRow);
    (aBegin+i-1)->push_back(pushback);
}
//cout<<"After pushback"<<endl;
//printvector(a);


// REPLACE NEIGHBOR WITH 'I' IN EVERY MEMBER
neighborRow=(aBegin+(neighbor-1))->begin(); //pointer to neighbor row
neighborRowEnd=(aBegin+(neighbor-1))->end(); //pointer to neighbor row end

for(neighborRow;neighborRow!=neighborRowEnd;neighborRow++){

    int neighborMember=*(neighborRow);
    gra1::iterator neighborMemberRow=(aBegin+(neighborMember-1))->begin(); //pointer to neighbor row
    gra1::iterator neighborMemberRowEnd=(aBegin+(neighborMember-1))->end(); //pointer to neighbor row end

    for(neighborMemberRow;neighborMemberRow!=neighborMemberRowEnd;neighborMemberRow++){

    if(*(neighborMemberRow)==neighbor){*(neighborMemberRow)=i;}
}

}

//cout<<" REPLACE NEIGHBOR WITH 'I' IN EVERY MEMBER"<<endl;
//printvector(a);

// DELETING SELF LOOPS

iRow=(aBegin+(i-1))->begin();
aBegin=a.begin();
seen=0;
while(iRow!=(a.begin()+(i-1))->end()){

    if(*(iRow)==i){
        (a.begin()+(i-1))->erase(iRow);
        iRow=((a.begin()+(i-1))->begin())+seen-1;
        seen-=1;
    }
    else{iRow+=1;}
}

//DELETE THE JTH ROW AND REPLACE BY 0

vector<int> tempvec(1,0);
a.insert(aBegin+neighbor-1,tempvec);

a.erase(a.begin()+neighbor);

//cout<<" Rfinal replacement"<<endl;
//printvector(a);

//NODES ACTIVE
int nodesactive=0;
int firstNumber;
aBegin=a.begin();
gra1::iterator countNodes=(aBegin)->begin(); //pointer to ith row
for(aBegin;aBegin!=a.end();aBegin++){

    countNodes=aBegin->begin();
    firstNumber=*(countNodes);
    if(firstNumber!=0){nodesactive+=1;}
}
return nodesactive;
}


void printvector(gra a){
    gra::iterator nodes=a.begin();
    cout<<"The vector is"<<endl;
    int i=1;
    for(nodes;nodes!=a.end();nodes++){
        gra1::iterator rows;
        cout<<i<<" ";
        for(rows=nodes->begin();rows!=(nodes)->end();rows++){

            cout<<*(rows)<<" ";
        }
        cout<<endl;
        i+=1;
    }
    return;

}

int nonzeronodes(gra &a){
    int randomInteger;
gra1 lists;
gra::iterator aBegin=a.begin();
gra1:: iterator it=aBegin->begin();

for(int i=1;i<=200;i++){
    it=aBegin->begin();
    if(*(it)!=0){lists.push_back(i);
    //cout<<i<<endl;
    }
    aBegin++;
}
cout<<"the size is   "<<lists.size()<<endl;
int index=rand() % lists.size();
return lists[index];
}


  Put the code you need help with here.

[lastchance]

It fails in a debugger at line 201.

You don't check whether your iterator has reached the end of the vector array: are you sure there are always 200 elements, or have you been deleting some?

Line 199 is unusual in C++, as C++ arrays are usually zero-indexed.

Are you sure that you need all these iterators? Your code would be easier to read (for me, anyway, but I'm not a computer scientist) just using standard array-indexing notation - [i][j] etc. There is a size() function to supply vector dimensions.

BTW, I should turn warning messages up on your compiler: some of your for-loops have unnecessary first elements.

Your code is hard-coded for 200 entries ... which rather restricts the number of graphs it can deal with.

[hasslersteph]

Thanks a lot for your suggestion and information!

I figured out a couple of mistakes. The code works fine now

The loop on Line 199 starts from 1, as its not acting as a index to anything.

Regarding the iterators, it makes the code much much faster because you can manipulate the graph without making separate copies. The code is not easy to read, I should improve upon that.

Also, removing the hard coded part would have taken one loop of counting in the text file, I was just lazy to do it (Inspite on working on this for a couple of days)