Skip to main content
`Ctrl`+`K`

# minimum_weight_full_matching

minimum_weight_full_matching(G, top_nodes=None, weight='weight')

  Returns a minimum weight full matching of the bipartite graph `G`.

  Let \(G = ((U, V), E)\) be a weighted bipartite graph with real weights \(w : E \to \mathbb{R}\). This function then produces a matching \(M \subseteq E\) with cardinality

  \[\lvert M \rvert = \min(\lvert U \rvert, \lvert V \rvert),\]

  which minimizes the sum of the weights of the edges included in the matching, \(\sum_{e \in M} w(e)\), or raises an error if no such matching exists.

  When \(\lvert U \rvert = \lvert V \rvert\), this is commonly referred to as a perfect matching; here, since we allow \(\lvert U \rvert\) and \(\lvert V \rvert\) to differ, we follow Karp [1] and refer to the matching as full.

  Parameters:
    G NetworkX graph

      Undirected bipartite graph

    top_nodes container

      Container with all nodes in one bipartite node set. If not supplied it will be computed.

    weight string, optional (default=’weight’)

      The edge data key used to provide each value in the matrix. If None, then each edge has weight 1.

  Returns:
    matches dictionary

      The matching is returned as a dictionary, `matches`, such that `matches[v] == w` if node `v` is matched to node `w`. Unmatched nodes do not occur as a key in `matches`.

  Raises:
    ValueError

      Raised if no full matching exists.

    ImportError

      Raised if SciPy is not available.

  Notes

  The problem of determining a minimum weight full matching is also known as the rectangular linear assignment problem. This implementation defers the calculation of the assignment to SciPy.

  References

  [1]

  Richard Manning Karp: An algorithm to Solve the m x n Assignment Problem in Expected Time O(mn log n). Networks, 10(2):143–152, 1980.