pub fn cycle_breaking_nodes<O, A>(
f: &OpenHypergraph<O, A>,
) -> Option<Vec<NodeId>>Expand description
Choose nodes whose spiderization is guaranteed to break every directed cycle.
This computes a greedy directed feedback vertex set on the bipartite incidence graph
node -> operation -> node.Basic idea:
- Construct a bipartite node-operation incidence graph.
- Vertices with indegree zero or outdegree zero cannot participate in a cycle.
- Repeatedly peel those vertices until no more acyclic fringe can be removed.
- Select the remaining wire node with the largest
indegree * outdegreescore, remove it, and repeat.
Selecting high-degree nodes in this way tends to break several cycles at once.
The result is deterministic and is guaranteed to make
f.clone().spiderize_nodes(&result) acyclic. It is a heuristic: the
returned set need not have minimum size.
Returns None if f has pending node identifications. Quotienting can
create cycles, so cycle breaking must operate on the semantic, quotiented
graph. When successful, the returned IDs refer directly to f.