MaxFlow Benchmark

Compilation:

Compile with:

:~$ g++ -o run benchmark.cpp -fopenmp

Running:

Run benchmark with:

:~$ ./run --file <input_file> --source <source_node> --sink <sink_node> --algorithm <algorithm> --threads <num_threads>

Possible algorithms are:

Edmonds-Karp algorithm (edmonds-karp), Shortest Augmenting Path (sap), and Push-Relabel (push-relabel). Only push-relabel is parallelized with OpenMP. When running push-relabel, specify the number of threads to use with the --threads parameter.

Datasets

A toy dataset is provided in input/. Larger random datasets can be generated with generate_random.py:

:~$ python3 generate_random.py <num_nodes> <num_edges>

Or run the benchmark on your own graphs, stored in a file where each line represents an edge in the format: <from> <to> <capacity>