You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
2.3 KiB
2.3 KiB
Max Flow using Dinic's Algorithm
Installation
This project does not have any specific requirements other than a cpp compiler. The installations process follows the CMake procedure:
git clone https://git.pranger.xyz/sp/MaxFlowDinic
cd MaxFlowDinic
mkdir build
cd build
cmake .. && make
Usage
To display the help message:
> ./build/maxFlow -h
You need to pass either and input graph file or an input graph string.
Allowed options:
-h, --help Print this help message.
-f, --input-file arg Filename of input graph file.
-s, --input-string arg Input graph string.
-o, --stdout Output to stdout.
-p, --output-file arg Filename for output.
-u, --check-uniqueness Check uniqueness of maximum flow and minimum cut.
-a, --max-flow Include verbose information about the maximum flow to the output.
-m, --minimum-cut Include the minimum cut set to the output.
-v, --verbose Output verbose algorithmic information and runtime. Pass twice to get information about all augmenting paths computed.
The examples folder features a few toy examples. Using the -f option to pass the path to an input file and -mavv gives a verbose output.
For example:
>./build/maxFlow -f examples/1.txt -mavv
#Vertices: 10
#Arc: 14
Source: 1, Sink: 10
Vertices: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
1 -> 2 capacity = 5
2 -> 10 capacity = 4
1 -> 10 capacity = 7
1 -> 3 capacity = 8
3 -> 10 capacity = 9
1 -> 4 capacity = 3
4 -> 7 capacity = 1
7 -> 10 capacity = 1
1 -> 5 capacity = 3
5 -> 8 capacity = 4
8 -> 10 capacity = 6
1 -> 6 capacity = 7
6 -> 9 capacity = 6
9 -> 10 capacity = 5
Found max flow |x| = 28
Max Flow per arc:
1 -> 2 flow = 4/5
2 -> 10 flow = 4/4
1 -> 10 flow = 7/7
1 -> 3 flow = 8/8
3 -> 10 flow = 8/9
1 -> 4 flow = 1/3
4 -> 7 flow = 1/1
7 -> 10 flow = 1/1
1 -> 5 flow = 3/3
5 -> 8 flow = 3/4
8 -> 10 flow = 3/6
1 -> 6 flow = 5/7
6 -> 9 flow = 5/6
9 -> 10 flow = 5/5
Min Cut X: {1, 2, 4, 6, 9}
Complement(X): {3, 5, 7, 8, 10}
Elapsed time: 1ms (1046µs).
Computation Statistics:
#level graphs built: 4
#augmenting paths computed: 6
1 > 10 | flow = 7
1 > 2 > 10 | flow = 4
1 > 3 > 10 | flow = 8
1 > 4 > 7 > 10 | flow = 1
1 > 5 > 8 > 10 | flow = 3
1 > 6 > 9 > 10 | flow = 5
#recursive buildPath calls: 32