search

iHeartGraph / iSpan

Parallel and distributed computation for the strongly connected component (SCC).
GNU General Public License v3.0
14 stars 10 forks source link

Wrong number of SCC on some input #3

Open Akatsukis opened 2 years ago

Akatsukis commented 2 years ago

Hi there,

I found that the application didn't report the correct number of SCCs in some cases. Here is one example: 0 2 1 0 2 3 3 1 3 2

One can follow the path 0->2->3->1->0, so the number of SCCs should be 1. The algorithm reported 2 instead.

I'm wondering if I ran the algorithm incorrectly or there is a glitch in the code.

yuede commented 2 years ago

Sorry for the late replying.

Yes, this example graph should have 1 SCC. Could you send me the exact graph file you tested?

Thanks, Yuede

Akatsukis commented 2 years ago

Hi Yuede,

Thanks for the reply! We tested it on LiveJournal. It reported 971233 SCCs while there are 971232 SCCs in the graph.

It also got stuck in infinite loops on some other graph instances. I will send you a CSR format of the graph later.

yuede commented 2 years ago

I think the extra one SCC is caused by an error in counting the SCCs at https://github.com/iHeartGraph/iSpan/blob/af53c7937b64f7acc06bce3f9fc7440d59fc1d4b/src/load_print.cpp#L35 You can change "vert_count+1" to "vert_count" and should get the correct result.

For the infinite loops, please send me the CSR file and I can take a look later.

Please let me know if you find any other issues. Good luck!

Best, Yuede

Akatsukis commented 2 years ago

I also realized this problem and tried to fix it. After I changed that line it reported wrong numbers on other graphs (e.g., CHEM_2.adj).

It got stuck in infinite loop in GeoLifeNoScale_2.adj.

The two graphs are organized in Problem Based Benchmark Suite format. Basically, the first line is a string of the graph description. The next two lines are n and m, the number of nodes and edges, respectively. The next n lines are offsets of the vertices. The next m lines are the edges. The vertex ids are 0-indexed.

Let me know if you have any problems running them.

yuede commented 2 years ago

Thank you for sharing the graphs.

It would be better if you could share the exact graph files and commands of how you run iSpan. The exact graph files should be the binary version of CSR, as shown here https://github.com/iHeartGraph/iSpan/tree/master/graph_converter

I should be able to dig in over this weekend if you could send me them before that.

Thanks, Yuede