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:
graph (NetworkX Graph) – A bipartite graph
top_nodes (list) – One of the bipartite sets in the graph
matching (dict) – Maps each node in top_nodes to its matched node
- 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