Maximum Matching
-
pyomo.contrib.incidence_analysis.matching.
maximum_matching
(matrix_or_graph, top_nodes=None)[source] Return a maximum cardinality matching of the provided matrix or bipartite graph
If a matrix is provided, the matching is returned as a map from row indices to column indices. If a bipartite graph is provided, a list of “top nodes” must be provided as well. These correspond to one of the “bipartite sets”. The matching is then returned as a map from “top nodes” to the other set of nodes.
Parameters: - matrix_or_graph (SciPy sparse matrix or NetworkX Graph) – The matrix or graph whose maximum matching will be computed
- top_nodes (list) – Integer nodes representing a bipartite set in a graph. Must be provided if and only if a NetworkX Graph is provided.
Returns: max_matching – Dict mapping from integer nodes in the first bipartite set (row indices) to nodes in the second (column indices).
Return type: