minimum_weight_full_matching(G, top_nodes=None, weight='weight')
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 and refer to the matching as full.
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.
Undirected bipartite graph
Container with all nodes in one bipartite node set. If not supplied it will be computed.
The edge data key used to provide each value in the matrix.
Raised if no full matching exists.
Raised if SciPy is not available.
The matching is returned as a dictionary, :None:None:`matches`, such that matches[v] == w
if node :None:None:`v` is matched to node w. Unmatched nodes do not occur as a key in :None:None:`matches`.
Returns a minimum weight full matching of the bipartite graph G.
Hover to see nodes names; edges to Self not shown, Caped at 50 nodes.
Using a canvas is more power efficient and can get hundred of nodes ; but does not allow hyperlinks; , arrows or text (beyond on hover)
SVG is more flexible but power hungry; and does not scale well to 50 + nodes.
All aboves nodes referred to, (or are referred from) current nodes; Edges from Self to other have been omitted (or all nodes would be connected to the central node "self" which is not useful). Nodes are colored by the library they belong to, and scaled with the number of references pointing them