PACE 2018 Steiner Tree Algorithms – Archive

This repository contains Rust implementations for the Tracks 1 and 3 of the 2018 PACE challenge.

I wrote this for an oral exam for an algorithm engineering class at university. It is probably not suitable for real-world applications.

I implemented the following algorithms:

• Dreyfus-Wagner Algorithm
• Algorithm of Kou et al.
• Algorithm of Takahashi and Matsuyama (H. Takahashi and A. Matsuyama. An approximate solution for the Steiner problem in graphs. 1980)

Usage (Benchmarks)

The easiest way to run the benchmarks is by running the benchmark.sh script in this repository. The usage is as follows:

./benchmark.sh results.csv path/to/pace_instance_directory

The benchmark results are then stored in results.csv.

Usage (Tests, Example)

For a "real" example program that runs all the algorithms and does some sanity-checking of the results see examples/run_all.rs. You can e.g. execute it on Instance 001 of PACE 2018 Track 1.

cargo run --release --example=run_all path/to/instance001.gr