Dulmage-Mendelsohn Partition

class pyomo.contrib.incidence_analysis.dulmage_mendelsohn.ColPartition(unmatched, underconstrained, overconstrained, square)

Named tuple containing the subsets of the Dulmage-Mendelsohn partition when applied to matrix columns (variables).

overconstrained: Alias for field number 2

square: Alias for field number 3

underconstrained: Alias for field number 1

unmatched: Alias for field number 0

class pyomo.contrib.incidence_analysis.dulmage_mendelsohn.RowPartition(unmatched, overconstrained, underconstrained, square)

Named tuple containing the subsets of the Dulmage-Mendelsohn partition when applied to matrix rows (constraints).

overconstrained: Alias for field number 1

square: Alias for field number 3

underconstrained: Alias for field number 2

unmatched: Alias for field number 0

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