Expand description
Minimum weight cycle basis (ALGO-CY-004).
Computes a minimum weight cycle basis using a modified Horton’s algorithm. Candidate cycles are generated via BFS from each vertex of degree ≥ 3, sorted by length, deduplicated, then filtered via Gaussian elimination over GF(2) to select linearly independent cycles of minimum total weight.
Edge directions are ignored. Multi-edges and self-loops are supported.
Counterpart of igraph_minimum_cycle_basis.
Functions§
- minimum_
cycle_ basis - Compute the minimum weight cycle basis of a graph.