mercredi 21 octobre 2020

How can I make a graph of about 500, 1K, 2K nodes in c++?

I'm trying to do some analysis on the time complexity of Kosaraju and Tarjan algorithm to find strongly connected components in a directed graph but the process of making up the graph is taking too much time. I tried making this 21 nodes graph but this too took me too long, i don't think continuing this way till 1k nodes is a good strategy.

class Graph 
{ 
public:
int vertex; 
vector<int> *adjcent_list;
Graph(int vertex){
  (*this).vertex=vertex;
  adjcent_list = new vector<int>[vertex]; 
}
void add_edge(int a, int b) 
{ 
adjcent_list[a].push_back(b); 
} 
};


int main() 
{ 
Graph g(22); 
g.add_edge(0, 1); 
g.add_edge(1, 2); 
g.add_edge(1, 3); 
g.add_edge(3, 4); 
g.add_edge(4, 0); 
g.add_edge(4, 5); 
g.add_edge(4, 6); 
g.add_edge(5, 6); 
g.add_edge(6, 5); 
g.add_edge(6, 7);
g.add_edge(7, 5); 
g.add_edge(7, 8); 

g.add_edge(8, 9); 
g.add_edge(9, 11); 
g.add_edge(9, 13); 
g.add_edge(11, 12); 
g.add_edge(12, 13);

g.add_edge(12, 9); 
g.add_edge(12, 8); 
g.add_edge(8, 10); 
g.add_edge(10, 13); 
g.add_edge(13, 14); 
g.add_edge(14, 15); 
g.add_edge(15, 16); 
g.add_edge(16, 17); 
g.add_edge(17, 18);
g.add_edge(18, 19); 
g.add_edge(19, 20); 
g.add_edge(20, 21); 
g.add_edge(19, 16); 
g.add_edge(20, 15);
    g.add_edge(16,19);
return 0;
}

Please help

Aucun commentaire:

Enregistrer un commentaire