DynMatch: Dynamic Matching in Practice

Part of the DynGraphLab — Dynamic Graph Algorithms open source framework. Developed at the Algorithm Engineering Group, Heidelberg University.

Description

In recent years, significant advances have been made in the design and analysis of fully dynamic maximal matching algorithms. However, these theoretical results have received very little attention from the practical perspective. Few of the algorithms are implemented and tested on real datasets, and their practical potential is far from understood. DynMatch bridges the gap between theory and practice for the fully dynamic maximal matching problem. We engineer several algorithms and empirically study them on an extensive set of dynamic instances.

An overview talk and slides explaining the algorithms are available.

Install via Homebrew

brew install DynGraphLab/dyngraphlab/dynmatch

Then run:

dynmatch FILE --algorithm=dynblossom --dynblossom_maintain_opt

Installation (from source)

git clone https://github.com/DynGraphLab/DynMatch
cd DynMatch
./compile_withcmake.sh

All binaries are placed in ./deploy/. Alternatively, use the standard CMake process:

mkdir build && cd build
cmake ../ -DCMAKE_BUILD_TYPE=Release
make && cd ..

Usage

dynmatch FILE [options]

Options

Option	Description
FILE	Path to dynamic graph sequence file
--algorithm=TYPE	One of {staticblossom, dynblossom, randomwalk, neimansolomon, baswanaguptasen}
-seed=<int>	Seed for the random number generator
-eps=<double>	Epsilon: limits search depth of random walk or augmenting path search to 2/eps-1
--dynblossom_lazy	Only start augmenting path searches after x newly inserted edges on an endpoint
--dynblossom_maintain_opt	Maintain optimum in dynblossom (without this the algorithm is called UNSAFE)
-measure_graph_only	Only measure graph construction time
-help	Print help

Input Format

Dynamic graph sequence format. The first line starts with # followed by the number of nodes and updates. Each subsequent line specifies an operation: 1 u v for edge insertion, 0 u v for edge deletion.

# 30399 87627
1 1 2
1 51 52
0 1 2

License

The program is licensed under the MIT License. If you publish results using our algorithms, please acknowledge our work by citing the following paper:

@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}
}