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: