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)
- Parameters:
matrix_or_graph (
scipy.sparse.coo_matrix
ornetworkx.Graph
) – The incidence matrix or bipartite graph to be partitionedtop_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