First-chance and Unhandled Exception in my code.

[mythreya]

Hi folks,

I am trying to write a code to isolate Strongly Connected Components in a graph using Kosaraju's algorithm (Runs DFS on reversed graph first and on the forward graph next).

I am getting these two errors for a graph with 875714 vertices and 5105043 edges:


First-chance exception at 0x000d2d56 in SCC.exe: 0xC00000FD: Stack overflow.
Unhandled exception at 0x77da15de (ntdll.dll) in SCC.exe: 0xC00000FD: Stack overflow.
The thread 'Main Thread' (0x504) has exited with code -1073741510 (0xc000013a).
The program '[1292] SCC.exe: Native' has exited with code -1073741510 (0xc000013a).


I have a suspicion that there are some bad pointers in my code. Could one of you take a look my code and point out what I should do? By the way, the exception break happened in the function listed at the very bottom

Here's the main function:

#include <iostream>
#include <fstream>
#include <vector>
#include <time.h>
#include <stack>
#include <queue>
#include <deque>

using namespace std;

int t = 0;
int s = 0;
void DFS_loop(vector<stack <int>>&);
void DFS(vector<stack <int>>&,int,vector<bool>&);
vector<int> leader;
vector<int> finish_times;
void bubble_sort(int*);

int main()
{
	clock_t t1,t2, t3,t4,t5;
        t1=clock();
	//CREATING THE GRAPH
	ifstream file1,file2;
	file1.open("SCC.txt");
	file2.open("SCC.txt");
	int head, tail;
	vector<stack<int>> node_list_FORWARD, node_list_REVERSE;
	stack <int> temp;


        //CODE TO INPUT THE REVERSE GRAPH AND RUN DFS ON THE SAME
	node_list_REVERSE.assign(875714,temp);
	while(!file1.eof())
	{
		file1 >> tail >> head;
		node_list_REVERSE.at(head-1).push(tail-1);
	} 

	leader.assign(node_list_REVERSE.size(),-1);
	finish_times.assign(node_list_REVERSE.size(),-1);

	DFS_loop(node_list_REVERSE); 


	//CODE TO INPUT THE REORDERED FORWARD GRAPH 
	node_list_FORWARD.assign(875714,temp);
	while(!file2.eof())
	{
		file2 >> tail >> head;
		node_list_FORWARD.at(finish_times.at(tail-1)-1).push(finish_times.at(head-1)-1);
	}
	leader.assign(node_list_REVERSE.size(),-1);
	finish_times.assign(node_list_REVERSE.size(),-1);
	
	DFS_loop(node_list_FORWARD);


        //CODE TO FIND TOP 5 STRONGLY CONNECTED COMPONENTS 
	int topfive[] = {0,0,0,0,0};
	int current = leader.at(0);
	int count = 0;
	for(int i=0;i<leader.size();i++)
	{
		if (current == leader.at(i))
		{
			count+=1;
		}
		else
		{
			current = leader.at(i);
			
			if (count >= topfive[0])
			{
				topfive[0] = count;
				bubble_sort(&topfive[0]);
			}
			count = 1;
		}
	}
	if (count >= topfive[0])
	{
		topfive[0] = count;
		bubble_sort(&topfive[0]);
	}

	for (int i =0; i<4;i++)
		cout << topfive[i] << ",";
	cout<<topfive[4]<<endl;

        system ("pause");
	return 0;
}

This is the outer loop for recursion. I don't there there is a problem here.

void DFS_loop(vector<stack <int>>& list)
{
	vector<bool> explored (list.size(),false);
	for (int i=list.size()-1;i>=0;i--)
	{
		if (!explored.at(i))
		{
			cout << i << endl;
			s = i;
			DFS(list,i,explored);
		}
	}
}

This is the main DFS recursive function where I suspect a problem. This is where the breakpoint happened. Also, since it says Stack Overflow, there might be a bad recursion here.

void DFS(vector<stack <int>>& list, int pos, vector<bool>& explored)
{
	explored.at(pos) = true;
	leader.at(pos) = s;
	stack<int>& edges = list.at(pos);
	int eds = edges.size();
	if (eds>0)
	{
		for(int j=0;j<eds;j++)
		{
			if (!explored.at(edges.top()))
			{
				DFS(list,edges.top(),explored);
			}
			edges.pop();
		}
	}
	t += 1;
	finish_times.at(pos) = t;
}

This is an auxiliary bubble-sort (one pass only) to help find the 5 biggest connected components.

void bubble_sort(int* input)
{
	int swapper;
	for (int i=0;i<4;i++)
	{
		if (*(input+i) > *(input+i+1))
		{
			swapper = *(input+i);
			*(input+i) = *(input+i+1);
			*(input+i+1) = swapper;
		}
	}
}

[Dy7SLyTq]

i believe you are going out of memory. that is a guess however. dont quote me on it

[ne555]

Try to make DFS iterative.

> This is an auxiliary bubble-sort (one pass only) to help find the 5 biggest connected components.
¿ah?

[Dy7SLyTq]

http://en.wikipedia.org/wiki/Bubble_sort

its a sorting algorithim and hes using it to a) order the components then b) just take the 5 biggest off the top

[mythreya]

I know I might have confused some of you there:

Here's the section where I suspect the problem lies because it involves pretty deep recursion:

void DFS(vector<stack <int>>& list, int pos, vector<bool>& explored)
{
	explored.at(pos) = true;
	leader.at(pos) = s;
	stack<int>& edges = list.at(pos);
	int eds = edges.size();
	if (eds>0)
	{
		for(int j=0;j<eds;j++)
		{
			if (!explored.at(edges.top()))
			{
				DFS(list,edges.top(),explored);
			}
			edges.pop();
		}
	}
	t += 1;
	finish_times.at(pos) = t;
}

as for ne555's answer: how do you suggest that I make DFS iterative?

[ne555]

stack candidates;
candidates.push(pos);
while( not candidates.empty() ){
   top = candidates.top();
   candidates.pop();
   explored( top ) = true;

   if( goal(top) )
      return top;

   for( son : top->sons )
      if( not explored(son) )
         candidates.push(son);
}

@DTSCode: I know what bubble sort is, now look at the code that's posted

[mythreya]

@ne555: Nice, let me try it. Can you explain what this section of the code does? Sorry about my ignorance.

if( goal(top) )
      return top;

[ne555]

It would interrupt the process because the objective was reached.
By instance, if you reach the exit of the labyrinth there is no need to keep exploring.

If it doesn't make sense in your code, just kill it.

[Dy7SLyTq]

guys i dont want to interrupt a discussion that is beyond me, but what does explored( top ) = true; mean? i didnt think functions could be lvalues in that way

[mythreya]

What ne555 posted was a pseudocode.

In my case explored is a vector and I converted explored(top) = true to explored.at(top) = true

[Dy7SLyTq]

oh ok