dulmage_mendelsohn

(function from pyomo.contrib.incidence_analysis.dulmage_mendelsohn)

pyomo.contrib.incidence_analysis.dulmage_mendelsohn.dulmage_mendelsohn(matrix_or_graph, top_nodes=None, matching=None)[source]

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:

  • row_dmp (RowPartition) – The Dulmage-Mendelsohn partition of rows

  • col_dmp (ColPartition) – The Dulmage-Mendelsohn partition of columns