Skip to content

dynamic-matching.md

Latest commit

 

History

History
127 lines (93 loc) · 3.82 KB

dynamic-matching.md

File metadata and controls

127 lines (93 loc) · 3.82 KB

Dynamic Graph Matching (DynMatch)

Original Repository: https://github.com/DynGraphLab/DynMatch

Overview

DynMatch maintains a matching on a dynamic graph where edges can be inserted and deleted incrementally. A matching is a set of edges such that no two edges share a vertex. The goal is to maintain a large matching at all times as the graph changes.

Seven algorithms are available, spanning exact and approximation approaches:

Algorithm Type Description
"blossom" Exact Blossom algorithm with augmenting paths (default)
"blossom_naive" Exact Naive blossom variant
"static_blossom" Exact Recompute from scratch after each update
"random_walk" Approximate Random walk based matching
"baswana_gupta_sen" Approximate 2-approximate dynamic matching
"neiman_solomon" Approximate Neiman-Solomon dynamic matching
"naive" Heuristic Naive greedy matching

DynMatching

Constructor

DynMatching(
    num_nodes: int,
    algorithm: str = "blossom",
    seed: int = 0,
)

Or via the namespace:

DynamicProblems.matching(
    num_nodes: int,
    algorithm: str = "blossom",
    seed: int = 0,
) -> DynMatching

Parameters

Parameter Type Default Description
num_nodes int required Number of vertices.
algorithm str "blossom" Algorithm name (see table above).
seed int 0 Random seed for reproducibility.

Methods

Method Description
insert_edge(u, v) Insert an undirected edge (u, v).
delete_edge(u, v) Delete an undirected edge (u, v).
get_current_solution() Return the current matching as a DynMatchingResult.

Returns (get_current_solution)

DynMatchingResult

Field Type Description
matching_size int Number of matched edges.
matching np.ndarray (int32) Matching array: matching[v] = mate of vertex v, or -1 if v is unmatched.

Exceptions

Exception Condition
InvalidModeError algorithm is not one of the valid choices.

Example

from chszlablib import DynamicProblems

solver = DynamicProblems.matching(num_nodes=100, algorithm="blossom")

# Build a graph
solver.insert_edge(0, 1)
solver.insert_edge(2, 3)
solver.insert_edge(1, 2)

result = solver.get_current_solution()
print(f"Matching size: {result.matching_size}")

# Check who is matched to whom
for v in range(4):
    mate = result.matching[v]
    if mate >= 0:
        print(f"  Node {v} matched with node {mate}")

# Dynamic update
solver.delete_edge(0, 1)
result = solver.get_current_solution()
print(f"Matching size after deletion: {result.matching_size}")

Performance Disclaimer

This Python interface wraps the DynMatch C++ library via pybind11. While convenient for prototyping and integration into Python workflows, there is inherent overhead from the Python/C++ boundary -- especially for fine-grained per-edge updates. For maximum performance with high update throughput, use the original C++ implementation directly from the DynMatch repository.

References

@inproceedings{DBLP:conf/esa/Henzinger0P020,
  author    = {Monika Henzinger and Shahbaz Khan and Richard D. Paul and Christian Schulz},
  title     = {Dynamic Matching Algorithms in Practice},
  booktitle = {28th Annual European Symposium on Algorithms, {ESA} 2020},
  series    = {LIPIcs},
  volume    = {173},
  pages     = {58:1--58:20},
  publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
  year      = {2020},
  doi       = {10.4230/LIPIcs.ESA.2020.58}
}