Partition a bipartite graph or incidence matrix according to the
Dulmage-Mendelsohn characterization
The Dulmage-Mendelsohn partition tells which nodes of the two bipartite
sets can possibly be unmatched after a maximum cardinality matching.
Applied to an incidence matrix, it can be interpreted as partitioning
rows and columns into under-constrained, over-constrained, and
well-constrained subsystems.
As it is often useful to explicitly check the unmatched rows and columns,
dulmage_mendelsohn partitions rows into the subsets:
underconstrained - The rows matched with possibly unmatched
columns (unmatched and underconstrained columns)
square - The well-constrained rows, which are matched with
well-constrained columns
overconstrained - The matched rows that can possibly be unmatched
in some maximum cardinality matching
unmatched - The unmatched rows in a particular maximum cardinality
matching
and partitions columns into the subsets:
unmatched - The unmatched columns in a particular maximum cardinality
matching
underconstrained - The columns that can possibly be unmatched in
some maximum cardinality matching
square - The well-constrained columns, which are matched with
well-constrained rows
overconstrained - The columns matched with possibly unmatched
rows (unmatched and overconstrained rows)
While the Dulmage-Mendelsohn decomposition does not specify an order within
any of these subsets, the order returned by this function preserves the
maximum matching that is used to compute the decomposition. That is, zipping
“corresponding” row and column subsets yields pairs in this maximum matching.
For example:
>>> row_dmpartition, col_dmpartition = dulmage_mendelsohn(matrix)
>>> rdmp = row_dmpartition
>>> cdmp = col_dmpartition
>>> matching = list(zip(
... rdmp.underconstrained + rdmp.square + rdmp.overconstrained,
... cdmp.underconstrained + cdmp.square + cdmp.overconstrained,
... ))
>>> # matching is a valid maximum matching of rows and columns of the matrix!
- Parameters:
matrix_or_graph (scipy.sparse.coo_matrix or networkx.Graph) – The incidence matrix or bipartite graph to be partitioned
top_nodes (list) – List of nodes in one bipartite set of the graph. Must be provided
if a graph is provided.
matching (dict) – A maximum cardinality matching in the form of a dict mapping
from “top nodes” to their matched nodes and from the matched
nodes back to the “top nodes”.
- Returns:
-