Body
Hi igraph team,
I've developed a pure Python (stdlib only, zero dependencies) implementation for extracting full-rank chordless cycle bases. I'm sharing this here because igraph's MCB implementation has been my primary benchmark, and I'm eager to get feedback from experts in this domain.
What it does
Given an undirected graph, it extracts a set of algebraically independent, chordless cycles that span the cycle space (rank = E − V + C). The algorithm relies on edge-based expansion with collision elimination, diverging from the traditional shortest spanning tree approach.
Why it exists
I entered a competition requiring pure Python (no C extensions allowed). Combined with my lack of C++ expertise, I had to roll my own instead of forking igraph. The result is a library deployable anywhere Python runs, with no compilation needed.
Benchmark results
Tested against igraph's MCB on 20 synthetic graphs (5k–10k edges), including dense short-cycle, grid, and mixed long-cycle topologies. All datasets passed full-rank audits (100% rank alignment, 0 chordal cycles).
Where it wins: Pure 4-cycle grid graphs
On uniform grid topologies, the edge-expansion approach scales better than the spanning tree method. The performance advantage grows with graph size, overcoming Python's inherent runtime overhead.
Dataset V / E / Rank igraph (C) Blackhole Diffusion (Python) Speedup
edge007 2500 / 4900 / 2401 8.70s 5.56s 1.57×
edge017 4900 / 9660 / 4761 52.82s 23.38s 2.26×
Where igraph wins: Mixed/Long-cycle graphs
As expected, igraph is generally 5–17× faster on most graph types due to the C vs. Python difference. Micro-benchmarks show a baseline "~15× language tax" from Python's runtime (object allocation, GC, interpreter loop).
Dataset V / E / Rank Topology igraph BH Ratio
edge003 1666 / 4989 / 3324 Mixed 3–7 cycle 2.88s 43.82s 15.2×
edge014 2000 / 9975 / 7976 Mixed 3–6 cycle 10.86s 181.94s 16.8×
MCB Accuracy
- Exact Match (35%): 7 out of 20 datasets match igraph's MCB total edge count exactly (all dense short-cycle/pure grid graphs with MCB ≤ 5).
- Drift: On longer-cycle graphs, total edge count inflates by 1–46% (cycle length drift +1 to +8).
Questions for the community
- Algorithmic Observation: Is the grid-graph speedup pattern (edge expansion outperforming spanning tree on uniform local structure) a known property, or has this been observed before?
- Benchmarks: Are there standard benchmark graph sets for cycle basis algorithms? I used synthetic data but would prefer established suites.
- Related Work: Without a formal graph theory background, I developed this independently (avoiding Horton/de Pina/Kavitha families). Can anyone point me to related literature?
Links
Thanks for building igraph—it's the gold standard I used for validation.
Body
Hi igraph team,
I've developed a pure Python (stdlib only, zero dependencies) implementation for extracting full-rank chordless cycle bases. I'm sharing this here because igraph's MCB implementation has been my primary benchmark, and I'm eager to get feedback from experts in this domain.
What it does
Given an undirected graph, it extracts a set of algebraically independent, chordless cycles that span the cycle space (rank = E − V + C). The algorithm relies on edge-based expansion with collision elimination, diverging from the traditional shortest spanning tree approach.
Why it exists
I entered a competition requiring pure Python (no C extensions allowed). Combined with my lack of C++ expertise, I had to roll my own instead of forking igraph. The result is a library deployable anywhere Python runs, with no compilation needed.
Benchmark results
Tested against igraph's MCB on 20 synthetic graphs (5k–10k edges), including dense short-cycle, grid, and mixed long-cycle topologies. All datasets passed full-rank audits (100% rank alignment, 0 chordal cycles).
Where it wins: Pure 4-cycle grid graphs
On uniform grid topologies, the edge-expansion approach scales better than the spanning tree method. The performance advantage grows with graph size, overcoming Python's inherent runtime overhead.
Dataset V / E / Rank igraph (C) Blackhole Diffusion (Python) Speedup
edge007 2500 / 4900 / 2401 8.70s 5.56s 1.57×
edge017 4900 / 9660 / 4761 52.82s 23.38s 2.26×
Where igraph wins: Mixed/Long-cycle graphs
As expected, igraph is generally 5–17× faster on most graph types due to the C vs. Python difference. Micro-benchmarks show a baseline "~15× language tax" from Python's runtime (object allocation, GC, interpreter loop).
Dataset V / E / Rank Topology igraph BH Ratio
edge003 1666 / 4989 / 3324 Mixed 3–7 cycle 2.88s 43.82s 15.2×
edge014 2000 / 9975 / 7976 Mixed 3–6 cycle 10.86s 181.94s 16.8×
MCB Accuracy
Questions for the community
Links
Thanks for building igraph—it's the gold standard I used for validation.