JuliaGraphs / JuliaGraphs/Graphs.jl
Performance discrepancy for (Weighted) DiGraphs when using weakly_connected_components() function
Nobody has claimed this yet.
- Dominant language
- Julia
- Stars
- 538
- Forks
- 128
- Avg merge
- 10h 25m
- Merged PRs (30d)
- 2
Description
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?
Contributor guide
First steps
- Read the whole issue, then the project's contributing guide.
- Comment on the issue to say you are picking it up — it saves two people doing the same work.
- Fork the repository and make your change on a branch.
- Open a pull request that references the issue number.
Research direction
Start by reproducing the benchmark with SimpleWeightedDiGraph and SimpleWeightedGraph on a large graph, then compare weakly_connected_components(g) with weakly_connected_components(g2). The issue does not name implementation files or tests, so locate the weakly connected components entry point and its graph traversal path first. Done means either resolving the performance discrepancy or documenting the observed behavior and its conditions.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- julia
- Domain
- data
- Issue type
- Bug
- Difficulty
- 4/5
- Estimated time
- 3-5 days
- Activity status
- Stale
- Clarity
- Mostly clear
- Newbie friendliness
- 35/100