Performance discrepancy for (Weighted) DiGraphs when using weakly_connected_components() function

[NessInMorse]

Performance for (Weighted) DiGraphs seems to be significantly lower when using weakly_connected_components() function.
When creating a SimpleWeightedGraph from the original graph and running weakly_connected_components() is at least a factor 10 faster for larger graphs.

g = SimpleWeightedDiGraph(sources, destinations, weights)
g2 = SimpleWeightedGraph(g)

weakly_connected_components(g)

# graph parsed:  0.16762208938598633s
# graph made:  0.27382898330688477s
# nodes: 95436 0.27390098571777344s
# edges: 155856 0.3015260696411133s
# nr_strongly_connected: 93695 0.3143501281738281s
# sizes_strongly_connected: calculated 0.31586408615112305s
nr_weakly_connected: 4120 51.31790113449097s
# sizes_weakly_connected: calculated 51.31804013252258s
# density: 1.7112112220620608e-5 51.318061113357544s

weakly_connected_components(g2)

# graph parsed:  0.1746540069580078s
# graph made:  0.2806689739227295s
# nodes: 95436 0.2807300090789795s
# edges: 155856 0.30792808532714844s
# nr_strongly_connected: 93695 0.3217201232910156s
# sizes_strongly_connected: calculated 0.3229191303253174s
nr_weakly_connected: 4120 0.4120509624481201s
# sizes_weakly_connected: calculated 0.41216516494750977s
# density: 1.7112112220620608e-5 0.41220808029174805s

Maybe it's possible to consider to update the documentation for weakly_connected_components() function to indicate this behavior?

[Krastanov]

Thanks for reporting this! Does this slowdown make sense? Shouldn't these two have the exact same performance (as the weakly connected components of a digraph should be the same as the (weakly) connected components of the undirected graph)?

This seems like a performance bug, not a unavoidable fact. If you feel like investigating, I would be happy to help you along in submitting a PR to fix these issues.

[NessInMorse]

I'd love to help and investigate!
You'd expect the performance to be the same for both implementations indeed, I suspect that the current algorithm does some kind of "conversion" to a simple(weighted)graph per iteration of all the neighbors which probably hinders performance.

[Krastanov]

A couple of things that might help:

• using @edit in the REPL (or vscode with the julia extension) to open directly the file containing the source code for the slower function, might immediately reveal the issue
• doing a few rough @time or @benchmark runs (especially to check for spurious allocations that grow with the size of the graph)
• using Profiler.@profile to see if something gets called repeatedly when it should not