Part of the DynGraphLab — Dynamic Graph Algorithms open source framework. Developed at the Algorithm Engineering Group, Heidelberg University.
Python Interface: An easy-to-use Python interface for this software is available in CHSZLabLib.
This repository implements and benchmarks state-of-the-art and new approaches for finding optimal as well as good delta-orientations in sparse graphs. The objective is to maintain an orientation of the edges in an undirected graph such that the maximum out-degree of any vertex remains low. When edges are inserted or deleted, it may be necessary to reorient some edges to prevent vertices from having excessively high out-degrees.
The repository contains two types of algorithms — exact algorithms and heuristics:
- The best heuristic algorithm, based on breadth-first search, computes the optimum result on more than 90% of instances and is on average only 2.4% worse than the optimum solution.
- The exact algorithm maintains an optimal edge orientation during both insertions and deletions, with update times up to 6 orders of magnitude faster than static exact algorithms.
For optimal static algorithms, see HeiOrient.
brew install DynGraphLab/dyngraphlab/dyndeltaorientationThen run:
dyndeltaorientation FILE --algorithm=IMPROVEDOPTgit clone https://github.com/DynGraphLab/DynDeltaOrientation cd DynDeltaOrientation ./compile_withcmake.sh -DILP=Off
All binaries are placed in ./deploy/. To enable ILP-based algorithms (requires Gurobi):
./compile_withcmake.sh -DILP=OnAlternatively, use the standard CMake process:
mkdir build && cd build cmake ../ -DCMAKE_BUILD_TYPE=Release -DILP=Off make && cd ..
dyndeltaorientation FILE [options]./deploy/delta-orientations examples/youtube-u-growth.seq --algorithm=IMPROVEDOPT ./deploy/delta-orientations examples/youtube-u-growth.seq --algorithm=NAIVE ./deploy/delta-orientations examples/youtube-u-growth.seq --algorithm=MAXDECENDING --depth=10 ./deploy/delta-orientations examples/youtube-u-growth.seq --algorithm=KFLIPS --flips=10
For all available algorithms and options:
./deploy/delta-orientations --helpDynamic 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
The program is licensed under the MIT License. If you publish results using our algorithms, please acknowledge our work by citing the following papers.
When using the heuristic algorithms:
@inproceedings{DBLP:conf/acda/BorowitzG023, author = {Jannick Borowitz and Ernestine Gro{\ss}mann and Christian Schulz}, title = {Engineering Fully Dynamic {\(\Delta\)}-Orientation Algorithms}, booktitle = {{SIAM} Conference on Applied and Computational Discrete Algorithms, {ACDA} 2023}, pages = {25--37}, publisher = {{SIAM}}, year = {2023}, doi = {10.1137/1.9781611977714.3} }
When using the exact algorithms:
@inproceedings{DBLP:conf/alenex/GrossmannR0W25, author = {Ernestine Gro{\ss}mann and Henrik Reinst{\"{a}}dtler and Christian Schulz and Fabian Walliser}, title = {Engineering Fully Dynamic Exact {\(\Delta\)}-Orientation Algorithms}, booktitle = {27th Symposium on Algorithm Engineering and Experiments, {ALENEX} 2025}, pages = {15--28}, publisher = {{SIAM}}, year = {2025}, doi = {10.1137/1.9781611978339.2} }