KMB algorithm for Steiner Trees

Run

Python

cd python
python3 -m venv venv
source venv/bin/activate
pip install -r requirements.txt
python main.py

C++

cd cpp
cmake .
make

To run KMB algorithm with instance050 as input from instances/ folder:

./cpp/build/kmb < instances/instance050.gr -o

Flags

• -o to run in outer parallel mode
• -i to run in inner parallel mode
• -b to run in both parallel mode
• -s to run in sequential mode

Run original research code

./cpp/build/og < instances/instance050.gr

KMB Algorithm

Input: G = (V, E, W), L ⊆ V

// S1
G1(L, E1= ∅);

// S2
for u ∈ L do
    for v ∈ L do
        Path(u,v) = shortest_path(u, v);
        W1(u,v) = |Path(u,v)|;
        G1.add_edge(u,v);
    end for
end for

// S3
T1 = minimum_spanning_tree(G1);

// S4
G2 = ∅;
for (u,v) ∈ E1(T1) do
    G2 = G2 ∪ Path(u,v);
end for

// S5
T2 = minimum_spanning_tree(G2);

Output: T2

KMB Algorithm Visualization

Steiner Tree

Stats

Processor Information

Generate Results Data results/

Modify the stats.sh file as per requirements

cd cpp/
chmod +x ./stats.sh
./stats.sh <executable_name> <output_file_name> <start_instance> <end_instance> <flags>

eg   ./stats.sh kmb test.csv 1 10 -o
This will create a test.csv file in results/ which will contain results of instances from 1 to 10. The flag -o meaning the kmb algorithm will run in outer parallel mode

Parallel Execution Performance

Our vs Original | Accuracy

Our vs Original | Time

References

Pace Challenge 2018: STP
ACM Research Paper : Accelerating Computation of Steiner Trees on GPUs