Unhandled exception at 0x76d84b61 in Partition_2.exe: 0xC00000FD: Stack overflow

Question

I am running Tarjan Algorithm to find SCC in c++. Code is running perfectly for me when number of nodes are 80k. But When I ran the code with more than 80k graph nodes. It is giving me an error as stack overflow

Unhandled exception at 0x76d84b61 in Partition_2.exe: 0xC00000FD: Stack overflow.

I looked online for some suggestions, it says my functions passes maximum number of recursion. I have no idea what to do now?

Here is my code:

Tarjan::Tarjan(vector<LinkedList> &graph, vector<vector<LinkedList*>> &SCC)
{
    cout<<endl<<"Finding SCC in graph ....."<<endl;
    clock_t start, finish;
    start = clock();
    int num = 1;
    vector<LinkedList*> stack;

    for(size_t i = 0; i<graph.size(); i++)
    {   
        if(graph[i].index == 0)
        {
            strongConnect(&graph[i], num, stack, SCC);
        }
    }
    finish = clock();
    if(SCC.size()>0)
    {
        cout<<"Number of cycles found in graph are "<<SCC.size()<<endl;
        timeTracker=(finish-start);
        cout<<"Time taken to find cycles in graph is "<<timeTracker<<" ms "<<endl;
    }
    else
        cout<<"No cycles found in graph "<<endl<<endl;
}

void Tarjan::strongConnect(LinkedList* vertex, int &num, vector<LinkedList*> &stack, vector<vector<LinkedList*>> &cycles)
{
    vertex->index = num;
    vertex->lowlink = num;
    num++;
    vertex->inStack = true;
    stack.push_back(vertex);

    for(map<LinkedList*, string>::iterator it=vertex->childaddr.begin(); it!=vertex->childaddr.end(); it++)
    {   
        if(it->first->index == 0)
        {
            strongConnect(it->first, num, stack, cycles);
            vertex->lowlink = min(vertex->lowlink, it->first->lowlink);
        }
        else
        {   
            if(it->first->inStack)
            {   
                vertex->lowlink = min(vertex->lowlink, it->first->index);
            }
        }
    }


    if(vertex->lowlink == vertex -> index)
    {
        vector<LinkedList*> temp;
        LinkedList* x;
        do{ 
            x=stack[stack.size()-1];
            vector<LinkedList*>::iterator st = stack.end(); st--;
            stack.erase(st);
            x->inStack=false;
            temp.push_back(x);
            if(temp.size()>1)
                x->inClique = true;
        }while(vertex->node != x->node);

        if(temp.size()>1)
        {
            temp[0]->inClique=true;
            cycles.push_back(temp);
        }
    }
}




LinkedList.h
class LinkedList
{
    public:
    string node;
    map<LinkedList*, string> childaddr;
    bool inStack;               // to find ssc
    bool inClique;              // To distinguish if node belongs to any clique or not
    int index;              // to find ssc
    int lowlink;            // to find ssc
    bool visited;           
};

I had spent weeks on this to figure out the solution but no gain. Please help me here. Thanks.

"Stack overflow" is a message you typically get when your recursions become to deep. You might want to redesign your code to use loops instead of recursion. — Some programmer dude, Jun 19 '15 at 05:47
Is there any specific limit on running the recursion in c++ code. I am using the standard Tarjan algortihm and was expecting to run it more than millions graph nodes but it is failing at 80k, — user3022426, Jun 19 '15 at 05:51
Stack overflow... Dammit . I've read that somewhere recently. Where? Where? — user4581301, Jun 19 '15 at 05:58
The size of the stack is initially defined by the operating system you're running on (on Windows for example it's 1MB). So an easy approach would be to increase the stack size, but a better solution is to redesign the code. — Lukas Thomsen, Jun 19 '15 at 05:58
If you're using gcc this answer http://stackoverflow.com/questions/156510/increase-stack-size-on-windows-gcc should provide you some help. For msvc there are options for that as well. The stack size will always be a limit with this design though. — meneldal, Jun 19 '15 at 06:00
If you are on windows/Visual Studio, there is a discussed solution here. https://social.msdn.microsoft.com/Forums/en-US/2a5b32b6-683b-4729-92d3-45ed7a89ef3f/stack-overflow-and-how-to-increase-the-stack-size?forum=Vsexpressvc — Acha Bill, Jun 19 '15 at 06:00
I am using visual studio 2010. I tried to fix the size of stack but no use — user3022426, Jun 19 '15 at 06:05
issue resolved. Thanks a lot. I increase the size of stack from 1MB to 8MB by Properties - Configuration Properties - Linker - System - Stack Reserve Size — user3022426, Jun 19 '15 at 06:15

score 0 · Answer 1 · answered Jun 19 '15 at 07:09

For millions of nodes, or if your program needs compilation on a computer where you don't control the compiler options, consider replacing recursion with a std::stack data structure and a loop: http://www.codeproject.com/Articles/418776/How-to-replace-recursive-functions-using-stack-and (or this one is shorter, but not in C++ http://haacked.com/archive/2007/03/04/Replacing_Recursion_With_a_Stack.aspx/ )

Unhandled exception at 0x76d84b61 in Partition_2.exe: 0xC00000FD: Stack overflow

1 Answers1