Advanced Algorithms Project - Push Relabel algorithm

This repository contains the code related to the implementation of the Goldberg's algorithm, also called Push-Relabel algorithm.
Three versions of the algorithm are implemented:

• Generic algorithm: the active vertices (with excess > 0) are selected randomly
• Heighest label preflow: the active vertices are selected based on which has the larget height
• Wave implementation (Lift-to-front): when a vertex is relabeled, it is placed at the beginning of the ordered active node list
  

Requirements

Execution

The following packages are required for the execution of the algorithm:

• Python 3.x
• graph-tool: for building and manipulating graphs
• numpy: for handling vertex and edge matrices and random numbers generation
• argparse: for passing arguments to main script
• Cython: for improving runtime performance by compiling Python code into C code

Testing

The following packages are required for the execution of the test routines:

• pytest: for running unit tests
• cProfile and pstats: for performing time complexity analysis
• memory_profiler: for performing space complexity analysis
• matplotlib: for plotting complexity test results

Execution

Compilation

The three files corresponding to the different implementations must be first compiled.
It is sufficient to execute python setup.py build_ext --inplace

Execution

The algorithm can be executed by calling python main.py followed by the possible arguments:
-h --help show help message and exit
-g --graph {random, scale-free, simple, delaunay} the type of graph to generate
-n --nodes the number of nodes in the graph
-m --edges dthe number of edges in the graph (available only for random graph)
-s --seed the seed number for the graph generation
-d --directed set the graph as directed (Default)
-u --undirected set the graph as undirected
-a --algorithm {generic, height, wave} the algorithm to compute the maximum flow (Default: generic)
-c --compare if used, the maximum flow value will be compared with the one resulting from the graph-tool library

For example, to plot the execution time the Goldberg's highest label preflow algorithm on a scale-free graph with 30 nodes and comparing the result with the graph-tool's one, call:
python main.py -g scale-free -u -s 543 -n 30 -c -a height

Unit tests

To perform unit testing it sufficient to call pytest --disable-pytest-warnings.
The following tests will be executed:

test_source_sinks.py checks if the created graphs have one and only one source and one and only one sink.
The other tests check if the maximum flow returned by the implementation is correct by comparing it with the value returned by graph-tool.

Time complexity analysis

The plot of the run time can be generated by calling python time_complexity.py followed by the possible arguments:
-h --help show help message and exit
-g --graph {random, scale-free, simple, delaunay} the type of graph to generate
-n --nodes [<NODES> ...] the list of number of nodes in the graph
-m --edges [<EDGES> ...] the list of number of edges in the graph (available only for random graph)
-d --directed set the graph as directed (Default)
-u --undirected set the graph as undirected
-a --algorithm {generic, wave} the algorithm to compute the maximum flow (Default: generic)
-s --samples the number of samples for each graph size -r --reduction {average,max} how the samples are summarized (by average or by taking the maximum)

The stats of the execution will be shown in file complexity_data/time_complexity_data_DATE.txt.
The plot of the execution will be shown in file complexity_graphs/time_complexity_plot_DATE.pdf.

For example, to plot the execution time the Goldberg's wave algorithm on a delaunay graph with 20, 30, 40, 50 nodes and respectively 80, 120, 160, 200 edges, repeating the execution 5 times, call:
python time_complexity.py -g delaunay -n 20 30 40 50 -m 80 120 160 200 -s 5 -a wave