get_scc_of_projection
(function from pyomo.contrib.incidence_analysis.triangularize)
- pyomo.contrib.incidence_analysis.triangularize.get_scc_of_projection(graph, top_nodes, matching=None)[source]
Return the topologically ordered strongly connected components of a bipartite graph, projected with respect to a perfect matching
The provided undirected bipartite graph is projected into a directed graph on the set of “top nodes” by treating “matched edges” as out-edges and “unmatched edges” as in-edges. Then the strongly connected components of the directed graph are computed. These strongly connected components are unique, regardless of the choice of perfect matching. The strongly connected components form a directed acyclic graph, and are returned in a topological order. The order is unique, as ambiguities are resolved “lexicographically”.
The “direction” of the projection (where matched edges are out-edges) leads to a block lower triangular permutation when the top nodes correspond to rows in the bipartite graph of a matrix.
- Parameters:
- Returns:
The outer list is a list of strongly connected components. Each strongly connected component is a list of tuples of matched nodes. The first node is a “top node”, and the second is an “other node”.
- Return type:
list of lists