graph/graph_simplify_utils library
Graph simplification: collapse degree-2 chains — roadmap #545.
Many graphs built from real geometry or pipelines contain long chains of "pass-through" nodes: vertices with exactly two neighbors that add no branching, only length. Routing, layout, and topology analysis usually care about the junctions (degree != 2) and the connectivity between them, not the intermediate beads. This utility contracts each maximal chain of degree-2 nodes into a single edge between the junctions at its ends, on an undirected graph given as a symmetric Adjacency list.
A component that is a pure cycle of degree-2 nodes has no junction to anchor to; its original edges are preserved unchanged so connectivity is never lost.
Functions
-
simplifyDegree2Chains(
Adjacency graph) → SimplifiedGraph -
Contracts maximal chains of degree-2 nodes in undirected
graph.