maximum_matching

(function from pyomo.contrib.incidence_analysis.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:

dict