Skip to main content

cycle_breaking_nodes

Function cycle_breaking_nodes 

Source
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 * outdegree score, 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.