Datalens.ai
← All algorithms

GRAPH-MATCHINGS

min_weighted_vertex_cover

Returns an approximate minimum weighted vertex cover.

Example of usage

Every collaboration relationship is covered by a selected partner.

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"]
)

# Approximate a small vertex cover: every relationship has an endpoint in it.
cover = approx.min_weighted_vertex_cover(network)
# Cover is feasible if every relationship has at least one selected partner.
assert all(u in cover or v in cover for u, v in network.edges())
assert len(cover) <= len(network)

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