JuliaGraphs / JuliaGraphs/Graphs.jl

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

Open
#465 3 comments 0 reactions 0 assignees View on GitHub

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

Open the contributing guide

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. 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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.