Datalens.ai
← All algorithms

GRAPH-MATCHINGS

min_weight_matching

Compute a minimum-weight maximum-cardinality matching of `G`.

Example of usage

Three disjoint relationships have total collaboration strength 16.

Usage / limitations

+Use when: Find assignments and covers.

−Limitations: Check input requirements, mathematical assumptions and version-specific behaviour before using.

Mathematical formula

See method documentation: implementation and assumptions vary.
Sample dataShow 
{
  "variable": "network_data",
  "domain": "Supply-chain partnership and relationship allocation",
  "feature_names": [
    "partner_name",
    "relationship_strength"
  ],
  "partners": [
    {
      "name": "Ana",
      "sector": "Logistics"
    },
    {
      "name": "Ben",
      "sector": "Retail"
    },
    {
      "name": "Cara",
      "sector": "Procurement"
    },
    {
      "name": "Dan",
      "sector": "Manufacturing"
    },
    {
      "name": "Eva",
      "sector": "Distribution"
    },
    {
      "name": "Finn",
      "sector": "Quality"
    }
  ],
  "relationships": [
    {
      "from": "Ana",
      "to": "Ben",
      "strength": 8
    },
    {
      "from": "Ana",
      "to": "Cara",
      "strength": 4
    },
    {
      "from": "Ben",
      "to": "Cara",
      "strength": 7
    },
    {
      "from": "Cara",
      "to": "Dan",
      "strength": 2
    },
    {
      "from": "Dan",
      "to": "Eva",
      "strength": 9
    },
    {
      "from": "Eva",
      "to": "Finn",
      "strength": 6
    },
    {
      "from": "Dan",
      "to": "Finn",
      "strength": 5
    }
  ]
}

Code example (Python)

# DataLens.ai example — supply-chain partner collaboration network.
# The named network_data input is prepended when copying input + code + test.
import networkx as nx
from networkx.algorithms import approximation as approx

# Construct the supplier collaboration network with relationship strengths.
network = nx.Graph()
network.add_nodes_from(partner["name"] for partner in network_data["partners"])
network.add_weighted_edges_from(
    (relationship["from"], relationship["to"], relationship["strength"])
    for relationship in network_data["relationships"]
)

# Find a minimum-weight matching among matchings of maximum cardinality.
matching = nx.min_weight_matching(network, weight="weight")
# NetworkX prioritises maximum cardinality, then minimum total weight.
assert nx.is_matching(network, matching)
assert len(matching) == 3
assert sum(network[u][v]["weight"] for u, v in matching) == 16

# Reaching this line means every expected-output assertion passed.
print("Expected output verified")