非递归Kosaraju的两遍算法实现永远在大数据集上执行(Non recursive Kosaraju's two pass algorithm implementation taking forever to execute on a large data set)

 
 
 我把它编码为一个已经超过截止日期的作业。 
 
 
 对于各种较小的测试用例，此实现完全正常，并在图中显示5个最大的强连接组件的大小。 
 
 
 但是当我在大约875714个顶点的赋值数据集上运行它时，似乎永远执行。 （60分钟后甚至没有出现在第一次DFS通行证中） 
 
 
 我已经使用了DFS例程的非递归堆栈实现，因为我听说大量的顶点导致了递归堆栈溢出问题。 
 
 
 如果有人能够指出，这个代码中的内容使得它使用大型数据集以这种方式运行将会非常有用。 
 
 
 输入文件由图表中的边列表组成。 一条边/线。 
 
 
 （例如）： 
 
 1 2 
 
 2 3 
 
 3 1 
 
 3 4 
 
 5 4 
 
 下载大图测试用例zip文件的链接 
 
 链接到我的程序文件 
 
 代码如下： 
 
 //宏定义和全局变量 
 
#define N 875714
#define all(a) (a).begin(), (a).end()
#define tr(c,i) for(typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)

vi v(N), ft, size;
 
 //非递归DFS算法 
 
void DFS(vvi g, int s, int flag)
{
stack<int> stk;
stk.push(s);
v[s] = 1;

int jumpOut, count;
vi::iterator i;

if(flag == 2)
     count = 1;

while(!stk.empty())
{
i = g[stk.top()].begin();
jumpOut = 0;

for(; i != g[stk.top()].end(); i++)
{
    if(v[*i] != 1)
    {
        stk.push(*i);
        v[*i] = 1;

        if(flag == 2) //Count the SCC size
            count++;

        jumpOut = 1; //Jump to the while loop's beginning
        break;
    }
 }

 if(flag == 1 && jumpOut == 0) //Record the finishing time order of vertices
    ft.push_back(stk.top());

 if(jumpOut == 0)
      stk.pop();
}

if(flag == 2)
    size.push_back(count); //Store the SCC size
}
 
 // 2通过Kosaraju算法 
 
void kosaraju(vvi g, vvi gr)
{
cout<<"\nInside pass 1\n";

for(int i = N - 1; i >= 0; i--)
    if(v[i] != 1)
        DFS(gr, i, 1);

cout<<"\nPass 1 completed\n";

fill(all(v), 0);

cout<<"\nInside pass 2\n";

for(int i = N - 1; i >= 0; i--)
    if(v[ ft[i] ] != 1)
        DFS(g, ft[i], 2);

cout<<"\nPass 2 completed\n";
}
 
 。 
 
int main()
{
vvi g(N), gr(N);
ifstream file("/home/tauseef/Desktop/DAA/SCC.txt");
int first, second;
string line;

while(getline(file,line,'\n')) //Reading from file
{
    stringstream ss(line);
    ss >> first;
    ss >> second;
    if(first == second) //Eliminating self loops
        continue;

    g[first-1].push_back(second-1); //Creating G & Grev
    gr[second-1].push_back(first-1);
}

cout<<"\nfile read successfully\n";

kosaraju(g, gr);

cout<<"\nFinishing order is: ";
tr(ft, j)
    cout<<*j+1<<" ";
cout<<"\n";

sort(size.rbegin(), size.rend()); //Sorting the SCC sizes in descending order

cout<<"\nThe largest 5 SCCs are: ";
tr(size, j)
    cout<<*j<<" ";
cout<<"\n";

file.close();
}

 
 
I coded this for an assignment which has passed its deadline.
 
 
This implementation works completely fine with various smaller test cases and displays the sizes of the 5 largest Strongly Connected Components in the graph as it should.
 
 
But seems to execute forever when i run it on the assignment data set of about 875714 vertices. (Doesn't even come out of the first DFS pass after 60mins)
 
 
I've used the non recursive stack implementation of the DFS routine as i heard that the large number of vertices was causing recursion stack overflow problems.
 
 
It would be really helpful if anyone could point out, what in this code is making it behave this way with the large dataset.
 
 
The input file consists of list of edges in the graph. one edge/line.
 
 
(eg):
 
1 2
 
2 3
 
3 1
 
3 4
 
5 4
 
Download link for the Large graph test case zip file 
 
Link to my program file
 
Code follows:
 
//Macro definitions and Global variables
 
#define N 875714
#define all(a) (a).begin(), (a).end()
#define tr(c,i) for(typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)

vi v(N), ft, size;
 
//Non recursive DFS algorithm
 
void DFS(vvi g, int s, int flag)
{
stack<int> stk;
stk.push(s);
v[s] = 1;

int jumpOut, count;
vi::iterator i;

if(flag == 2)
     count = 1;

while(!stk.empty())
{
i = g[stk.top()].begin();
jumpOut = 0;

for(; i != g[stk.top()].end(); i++)
{
    if(v[*i] != 1)
    {
        stk.push(*i);
        v[*i] = 1;

        if(flag == 2) //Count the SCC size
            count++;

        jumpOut = 1; //Jump to the while loop's beginning
        break;
    }
 }

 if(flag == 1 && jumpOut == 0) //Record the finishing time order of vertices
    ft.push_back(stk.top());

 if(jumpOut == 0)
      stk.pop();
}

if(flag == 2)
    size.push_back(count); //Store the SCC size
}
 
// The 2 pass Kosaraju algorithm
 
void kosaraju(vvi g, vvi gr)
{
cout<<"\nInside pass 1\n";

for(int i = N - 1; i >= 0; i--)
    if(v[i] != 1)
        DFS(gr, i, 1);

cout<<"\nPass 1 completed\n";

fill(all(v), 0);

cout<<"\nInside pass 2\n";

for(int i = N - 1; i >= 0; i--)
    if(v[ ft[i] ] != 1)
        DFS(g, ft[i], 2);

cout<<"\nPass 2 completed\n";
}
 
.
 
int main()
{
vvi g(N), gr(N);
ifstream file("/home/tauseef/Desktop/DAA/SCC.txt");
int first, second;
string line;

while(getline(file,line,'\n')) //Reading from file
{
    stringstream ss(line);
    ss >> first;
    ss >> second;
    if(first == second) //Eliminating self loops
        continue;

    g[first-1].push_back(second-1); //Creating G & Grev
    gr[second-1].push_back(first-1);
}

cout<<"\nfile read successfully\n";

kosaraju(g, gr);

cout<<"\nFinishing order is: ";
tr(ft, j)
    cout<<*j+1<<" ";
cout<<"\n";

sort(size.rbegin(), size.rend()); //Sorting the SCC sizes in descending order

cout<<"\nThe largest 5 SCCs are: ";
tr(size, j)
    cout<<*j<<" ";
cout<<"\n";

file.close();
}

原文：https://stackoverflow.com/questions/34257157