Нерекурсивная реализация двухпроходного алгоритма Косараю, выполняемая навсегда для большого набора данных
Я закодировал это для задания, которое прошло его крайний срок.
Эта реализация прекрасно работает с различными меньшими тестовыми примерами и отображает размеры 5 самых сильных компонентов на графике, как и должно быть.
Но, кажется, выполняется вечно, когда я запускаю его на наборе данных о назначении около 875714 вершин. (Даже не выходит из первого прохода DFS через 60 минут)
Я использовал нерекурсивную реализацию стека подпрограммы DFS, так как услышал, что большое количество вершин вызывает проблемы переполнения стека рекурсии.
Было бы очень полезно, если бы кто-то мог указать, что в этом коде заставляет его вести себя таким образом с большим набором данных.
Входной файл состоит из списка ребер в графе. один край / линия.
(например):
1 2
2 3
3 1
3 4
5 4
Ссылка на скачивание zip-файла тестового набора Large graph
Ссылка на мой программный файл
Код следует:
// Макроопределения и глобальные переменные
#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
}
// Двухпроходный алгоритм Косараю
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();
}
1 ответ
Есть несколько улучшений, которые вы можете применить:
1- cin не так быстро scanf для больших входов: поскольку ваш входной файл огромен, лучше использовать scanf читать ваши данные.
2. Не стоит передавать большие данные в функции по значению: в вашем коде есть два огромных графика, которые вы передаете их функциям по значению. Это занимает много времени, потому что каждый раз, когда вы делаете копию данных.
3- Нет необходимости использовать iterator для прохождения vector: Потому что вы используете vector и у вас есть произвольный доступ к нему через [] Оператору нет необходимости использовать iterator для доступа к данным.
4- Ваша DFS неэффективна: это самая важная из них. Каждый раз, когда программа переходит в начало while и проверьте список смежности элемента в верхней части stack Вы начинаете с начала и проверяете элементы. Это делает алгоритм очень неэффективным, потому что вы проверяете некоторые вещи снова и снова. Вы можете просто сохранить, сколько дочерних элементов вы проверили, и когда вы вернетесь к этому элементу, вы начнете со следующего элемента вместо того, чтобы начинать со старта.
#include<iostream>
#include<vector>
#include<stack>
#include<algorithm>
#include<fstream>
#include<string>
#include<sstream>
using namespace std;
typedef vector<int> vi;
typedef vector<vi> vvi;
#define N 875714
#define sz(a) int((a).size())
#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;
vi childsVisited(N);
void DFS(vvi &g, int s, int flag)
{
stack<int> stk;
stk.push(s);
v[s] = 1;
int jumpOut, count;
if(flag == 2)
count = 1;
int counter = 0;
while(!stk.empty())
{
jumpOut = 0;
int cur = stk.top();
for ( ;childsVisited[cur] < g[cur].size(); ++childsVisited[cur] )
//for ( int i=0; i< g[cur].size(); ++i )
//for(; i != g[stk.top()].end(); i++)
{
int i = childsVisited[cur];
int next = g[cur][i];
if(v[next] != 1)
{
stk.push(next);
v[next] = 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
}
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);
fill(all(childsVisited), 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()
{
freopen("input.txt","r",stdin);
vvi g(N), gr(N);
//ifstream file("/home/tauseef/Desktop/DAA/SCC.txt");
int first, second;
//string line;
unsigned long int cnt = 0;
//while(getline(file,line,'\n')) //Reading from file
//{
//stringstream ss(line);
//ss >> first;
//ss >> second;
//if(first == second) //Eliminating self loops
//continue;
for ( int i = 0; i < 5105043; ++i ){
int first, second;
scanf("%d %d",&first,&second);
g[first-1].push_back(second-1); //Creating G & Grev
gr[second-1].push_back(first-1);
}
//cnt++;
//}
cout<<"\nfile read successfully\n";
kosaraju(g, gr);
cout<<"\nFinishing order is: ";
sort(size.rbegin(), size.rend()); //Sorting the SCC sizes in descending order
cout<<"\nThe largest 5 SCCs are: ";
}