Wrong number of SCC on some input

[Akatsukis]

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]

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]

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]

I think the extra one SCC is caused by an error in counting the SCCs at

iSpan/src/load_print.cpp

Line 35 in af53c79

for(index_t i=0; i<vert_count+1; ++i)

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]

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]

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