MINISTRY OF EDUCATION AND SCIENCE OF THE RUSSIAN FEDERATION State autonomous educational institution of higher education «Lobachevsky State University of Nizhni Novgorod» Institute of Information Technology

MINISTRY OF EDUCATION AND SCIENCE OF THE RUSSIAN FEDERATION
State autonomous educational institution of higher education
«Lobachevsky State University of Nizhni Novgorod»

Institute of Information Technology, Mathematics and Mechanics:
Major (field): Fundamental Computer Science and Information Technologies

We Will Write a Custom Essay Specifically
For You For Only $13.90/page!


order now

Research Project Report

Topic:
«Methods for the maximum flow problem»

Prepared by: student of group 2014BIT
___________________ Dlamini Gcinizwe
Signature

Supervised by:
D.Sc., Prof.
__________________ Nikolai Yu. Zolotykh
Signature

Nizhni Novgorod
2018

2

???????????? ??????????? ? ????? ?????????? ?????????
??????????? ??????????????? ?????????? ??????????????? ??????????
??????? ???????????
«????????????? ??????????????? ???????????
??. ?.?. ????????????»

???????? ?????????????? ?????????? ?????????? ? ????????

????????????? (???????????): ??????????????? ??????????? ?
?????????????? ??????????

????????? ???????????????? ?????? ?????????

????:
«?????? ??????? ?????? ? ???????????? ?????? ? ????»

????????: ??????? ?????? 2014IT
_______________ ??????? ???????? ???????
???????

??????? ????????????:
?. ?.-?. ?., ????. ???. ????
____________________ ??????? ?.?.

???????

?????? ????????
2018

3

Contents
Introduction …………………………………………………………………………………………………………………… 4
1. Problem statement ……………………………………………………………………………………………………. 5
2. Ford–Fulkerson method ……………………………………………………………………………………………. 8
2.1 Basic concepts ………………………………………………………………………………………………….. 8
2.1 General description …………………………………………………………………………………………. 10
2.3 Implementation ………………………………………………………………………………………………. 11
3 Push-relabel algorithm ……………………………………………………………………………………………. 14
3.1 Basic concepts and operations …………………………………………………………………………… 14
3.2 General description …………………………………………………………………………………………. 15
3.3 Implementation ………………………………………………………………………………………………. 16
4 Computational evaluation………………………………………………………………………………………… 19
Conclusion…………………………………………………………………………………………………………………… 22
Literature …………………………………………………………………………………………………………………….. 23
Appendix A. Source code listing ……………………………………………………………………………………… 24

4

Introduction
The maximum flow problems are a group of important and well-studied optimization
problems with numerous applications 1-5. This research project studies the maximum flow problem
in a network with a single source and sink, which is a classical problem of computer science, and
solving it with the help of the two most popular methods namely Ford-Fulkerson method and Push-
relabel generic algorithm.
The goals of this project are as follows:
1. Study the literature on the maximum flow problem.
2. Get familiar with the Ford-Fulkerson method and Push-relabel generic algorithm.
3. Develop a C++ implementation of the methods.
4. Test the created implementations.
5. Perform computational evaluation and compare performance of the implemented algorithms.

5

1. Problem statement
Network !=($,&) is a connected directed graph where by each edge ( ?& is associated with
its weight known as capacity +(()?0 3, 6. Flow network is formed under certain principles. It has
two special vertices called the source (s) and the sink (t) where (.?0), antiparallel edges are
disallowed meaning if (1,2)?& then (2,1)?& 3, 6. Figure 1 is an example of a network and
flow network modelling the definitions stated above.

Figure 1. A network G=(V,E) where vertex s and t is the source and sink. Each edge (u,v) is labelled with its
own weight which is referred as capacity c(u,v).
A flow in ! given that !=($,&), . is the source, 0 is the sink and + is the capacity function that
complies with the two subsequent properties:
1. Capacity constrains: Flow on edge (1,2) (1,2)?+(1,2)
2. Skew symmetry: For every node (vertex) 1 ?$? {.,0} incoming flow should be equal to
outgoing flow.
B>(1,2)
C?D
=B>(2,1)
C?D

If (2,1)?& then >(2,1)=0.
Therefore, a flow in network ! is defined a s real valued function that models a net flow of
units between two nodes (vertices). It can be briefly defined as >?$ × $ ? ? satisfying the two
above properties. The flow value of network ! is defined as follows:
|>| = B>(.,2)
C?D
?B>(2,0)
C?D

An example of flow in network is shown in Figure 2. The following notation is used to denote flow:
flow and the capacity on each edge (1,2) are given with a slash notation >(1,2)/+(1,2)

6

Figure 2 A flow > in the above given network !=($,&) value |>|=13. In separation of flow and the capacity on
each edge (1,2) a slash notation is used >(1,2)/+(1,2). Therefore, the slash does not denote division operation sign.
In maximum flow problem, the goal is to maximize the value of a flow from source to sink
in a network with respect to the flow constrains.
In modelling, real world problems using maximum flow, a network can contain antiparallel
edges whereby antiparallel edges in network !?{(1,2) ,(2,1)}. This violates the original assumption
that if an edge (1,2)?& then (2,1)?&. A fix for such contradiction is transformation of the
network to an equivalent one containing no antiparallel edges. First step to the fix, one of the two
antiparallel edges is chosen and split by adding a new vertex. Secondly, the chosen edge is replaced
by two edges, one to the new vertex and one out of the new vertex. Lastly, the capacities of the new
edges are set to the capacity of the original edge. The resulting network after the fix will definitely
satisfy the property disallowing reverse edges. The figure below displays the fix for network with
antiparallel edges.

Figure 3 Left: !=($,&) with antiparallel edges (S,T) and (T,S). Right: ! after the antiparallel edges fix. New vertex E was
introduced in the process of the removing the antiparallel edges
Moreover, it is possible that a resulting network contains multiple sinks and sources, rather than just
one each. In determining the maximum flow in network of this kind, modification has to introduced
for the network to fit the ordinary maximum-flow problem whereby the flow network has one sink
and one source. In a case of a flow network having multiple sources, a supersource vertex is added
having directed edges to all the sources. Every directed edge from the supersource assigned with

7

infinity as value for capacity. Likewise, in the case of multiple sinks, a supersink is introduced to the
network, directed edges from all the sinks to the supersink added with capacity infinity. The resulting
flow network after modification of the network with either multiple sources, multiple sinks or both
satisfies the properties of a flow network and is reduced to a simpler problem.
There are several real-world applications of maximum flow problem and can model many
problems in real life, namely circulation-demand problem, airline scheduling, network reliability,
liquids flowing through pipes, information through communication networks and liquids passing
through pipes. In modelling liquids flowing through pipes, a pipe can be modelled as the directed
edge, capacity as the maximum amount of the liquid can flow through a pipe and vertices excluding
the source and sink as the junctions and sink thought as destination. Circulation-demand problem can
be transformed to maximum flow problem by representing the source as a factory, channel as road,
capacity as maximum goods that can flow through a road, vertices as cities between the factory and
consumer/demand 1. To know how much goods, have to be sent on a particular road for satisfying
the demands maximum flow must be calculated.
In an endeavour to solve the maximum flow problem, different algorithms and methods have been
developed having different complexities and runtimes 1-4, 7. Such methods are also covered in many
textbooks on computer science, including references 8-11. First most basic method which is mostly
used is called Ford–Fulkerson method 1. Another method which is one of the most efficient
maximum flow problem algorithms is called Push-Relabel algorithm. Both listed methods to the
solution of maximum flow problem are taken into consideration in this paper with examples,
implementations and experiments to check the implementation correctness. The following sections
discusses each method in detail and its implementation.

8

2. Ford–Fulkerson method
In simplification of soviet railway traffic flow model T.E Harris and F.S Ross formulated the
maximum flow problem, then a year later Lester R. Ford, Jr. and Delbert R. Fulkerson formulated the
first known method for calculating maximum flow 1. The method is called Ford–Fulkerson method.
It is called a “method” rather than an “algorithm” because it defines a general framework of steps to
be performed, and different algorithms with different complexities can be used. The method is solely
dependent and implemented on three basic concepts: residual networks, augmenting paths and cuts.
The description of the method below is mainly based on the classical textbook 9.
2.1 Basic concepts
Residual network for a network ! is defined as follows. Suppose flow network G is given
having flow f, its residual network is defined as !U=($,&U) consisting of edges with capacities that
show how the flow in edges of ! can be changed. The properties which define the residual network’s
identity as follows:
• The vertex set of !Uis the same as that of the original network !
• !U can contain edges which are not present in original network ! but having positive residual
capacity.
• Each edge is assigned with capacity also known as residual capacity +U which indicates the
possible amount of flow which can be added or deducted from the original edge flow value.
For each edge (=(1,2) in ! on which ;(()(1,2),(1,2)?;,
;(2,1),(2,1)?;,
0, otherwise.

• Reverse edges are possible in residual network. The reverse edges imply back flow which
means decreasing the flow of the edge to increase the overall flow of the network.
• Each edge of the residual network can admit a flow that is greater than zero.
;U={(1,2)?$×$? +U
(1,2);0
• The edges are either edges of the original network or their reversals.
;U
? 2|;|.
It is notable that for each edge (=(1,2) in ! can transform into one or two edges in residual
network if 0(() with value |;|=13. Right: the corresponding residual network !U.
Given residual network !U of network ! with flow f, . as source and 0 as sink an augmenting
path ^ is the simple path in !U from s to t. The augmenting path ^ is aimed increasing the flow on
edge (1,2) in ^ by up to +U(1,2) without violating the the capacity constrains defined for either (1,2)
or (2,1) in the original network !. The maximum value by which the flow can be increase each edge
in path ^ which is also called residual capacity is given by
+U
(^)=min`+U
(1,2)?(1,2) is on ^a.
Using the residual capacity network ! is updated and the ; flow gets increased. For each edge
(1,2) in path p and exist in original network (1,2)?; the flow of that edge is increased by the
residual capacity. Else if the edge is not part of ! edges (1,2)?; but part of the residual network
edges (1,2)?;U, the reverse corresponding edge flow ;(2,1) is decreased by the residual capacity.
The figure below shows an example of an augmenting path and how it is used to modify a flow of a
network.

Figure 6 Left: a residual network !Uwith augmenting path ^ highlighted and having residual capacity +U
(^)=7.
Right: the result network after flow update using the highlighted augmenting path ^ in residual network !U.
To obtain the maximum flow in network !, the Ford–Fulkerson method repeatedly arguments
the flow along augmenting paths. To terminate the repetition of the algorithm and return the maximum
flow, Max-flow min-cut theorem 9 is used. The theorem tells us that the flow is maximum if and
only if the residual network contains no augmenting path.

10

The Max-flow min-cut theorem uses the notion of a cuts whereby a cut (c,d) of a flow-
network !=($,;) is a partition of the vertices into c and d=$?c such that the . ?c and 0 ?d.
Net flow ;(c,d) being the flow across the cut (c,d) which is defined as
;(c,d)= BB;(1,2)
C?ef?g
? BB;(2,1)
C?ef?g
.
The cut(c,d) capacity being
+(c,d)= BB+(1,2)
C?ef?g
.
And finally, a minimum cut of a network as a cut whose capacity is minimal over all cuts of
the network. Using the above defined theorem basis, the correctness of max-flow min-cut theorem is
illustrated in the next section.
2.1 General description
The general Ford–Fulkerson method is designed such that it firstly initializing the flow to zero
by assigning every edge flow to zero ;(1,2)=0 for all 1,2 ?$. Secondly, iteratively find an
augmenting path in an associated residual network, after an augmenting path is found, specific edges
flow in G are updated thus the flow of the network is increased and updating the residual network.
Lastly, if there is no existing augmenting path in a corresponding residual network, the algorithm
terminates and returns the maximum flow. However, in the process of increasing the flow of the
network, any particular edge flow value can be also decreased in order to enable the algorithm to send
more flow from the source to the sink. A pseudocode of the method 9. is given below.
Ford–Fulkerson method (G, s, t)
1. for each edge (u,v)?E
2. f(u,v)=0
3. while exist a path p from s to t in the residual network Gj
4. cj
(p)=min{cj
(u,v)?(u,v) is in path p}
5. for each (u,v) in p
6. if (u,v)?E
7. f(u,v)=f(u,v)+ cj
(p)
8. else f(v,u)=f(v,u)? cj
(p)
9. End for
10. End while
The pseudocode above shows the result of a single iteration in a simple run. Lines 1-2 assigns
the flow to zero. The beginning of while loop produces the corresponding residual network which is
used in the construction of the augmenting path. In finding the augmenting path which is a classical

11

graph problem, many algorithms could be used including breath-first search (BFS) and depth-first
search (DFS) 1. The chosen path finding algorithm influences the total running time of the method.
The augmenting path is then used in obtaining residual capacity which is being assigned in line 5.
Line 6 – 8 updates the original flow network by either decreasing or increasing the flow of edges using
the capacity flow found in line 4. To prove the proficiency of the method to calculate the maximum
flow, a series of proofs for correctness have been formulated by different mathematicians and included
them in the classic algorithms book 9. One of the most important proofs included in the book proves
that the flow capacity from any augmenting path increases the flow.
To ensure that the method while loop terminates and the current flow is maximum, the max-
flow maximum cuts theorem states two conditions which must be true. The conditions are as follows:
3 Absence of augmenting path in the residual network.
4 The flow maximum value is equal capacity of some cut in (c,d) in flow network. |;|=+(c,d).
A detailed proof for this theorem is given in 9.
Ford–Fulkerson method complexity depends on the algorithm used to find the augmenting
path in the residual network. It is possible that the algorithm could not terminate while the flow
increases but not converging to the maximum flow value. This could be caused by a poor choice of
augmenting path and the network having irrational values as edges capacities. Using BFS in finding
the augmenting path having integer edges capacities, the algorithm runs in polynomial time. With
right data structure, flow values being integers and augmenting path finding algorithm which runs in
linear-time, the total Ford–Fulkerson method running time can be approximated to m(; |;
?
|) where
|;
?
| denotes a maximum flow 9.
A version of Ford–Fulkerson method which its approach is to find the augmenting path with
a breath-first search and choosing the shortest path from source to sink is called Edmonds-Karp
algorithm has a better complexity of m($;
o
) 9. One advantage is that the runtime is independent of
the maximum flow value.
2.3 Implementation
In my implementation of the Ford–Fulkerson method, I used C++ programming language
which helps in resembling of the flow network components with its object-oriented programming
techniques. Visual Studio 2010 Ultimate was used as an IDE for performing experiments. With the
aim of choosing an ideal data structure to improve the method run time, the Standard Template
Library was put into use.
The program is composed of header files paired with source files. In representation of the
method’s basic components which is mainly the flow network composed of vertices and weighed
edges, residual network and the augmenting path. A vertex was modelled as a separate class in a pair

12

of files (header and source code file) having vector of incoming edges, outgoing edges and index for
identification as data members. The vertex class consist of get and set methods. The edge which is a
connection of two vertices being resembled by a class modelling the attributes of the edge namely
flow value, edge capacity, direction as pointer to the edge start vertex and end vertex. Edge class get
and set methods included. The main component of the method being flow network represented as a
class incorporate the vertex class and edge class. Data members of the network class are source vertex,
sink vertex and the vertices between the sink and the source. In the function members, modify edge
function and calculate total vertices implemented.
To smoothly calculate the maximum flow and implement the basic concepts of Ford–
Fulkerson method which are residual network, flow update and augmenting path computations, I set
apart a source and header file. All header files contain declarations and definitions while source files
contain implementations. The main function of the program creates the input network flow and
implements the while loop of the flow method. In the while loop firstly a residual corresponding
network is computed. Secondly, a function to compute augmenting path is executed and if it
successfully returns a path the input flow network, the original flow is updated else the while loop is
terminated which is a signal of reaching the maximum flow in the given flow network. Lastly, the
memory allocated for the flow network is freed.
The diagrams below illustrate the program implementation execution in the while loop where
the residual network, augmenting path are computed and the input flow network is updated. Each
loop iteration is resembled by a pair of network diagrams, one showing the residual network with a
highlighted consequent augmenting path while the other shows the corresponding updated network
flow. The input flow network is the one is the one used in the definition in the section above.

Figure 7 Left: a residual network !Uwith augmenting path ^ highlighted and having residual capacity +U
(^)=7.
Right: the result network after flow update using the highlighted augmenting path ^ in residual network !U.

13

Figure 8 Left: a residual network !Uwith augmenting path ^ highlighted and having residual capacity +U
(^)=5.
Right: the result network after flow update using the highlighted augmenting path ^ in residual network !U.

Figure 9 Left: a residual network !Uwith augmenting path ^ highlighted and having residual capacity +U
(^)=2.
Right: the result network after flow update using the highlighted augmenting path ^ in residual network !U.

Figure 10 Left: a residual network !Uwith augmenting path ^ highlighted and having residual capacity +U
(^)=9.
Right: the result network after flow update using the highlighted augmenting path ^ in residual network !U.
Last iteration

Figure 11: Residual graph with no possible path from source to sink. The value of maximum flow = 23.

14

3 Push-relabel algorithm
Nowadays asymptotically fastest maximum-flow algorithms are based on the push-relabel
method 9. In the process of developing an algorithm with better running time compared to the
Edmonds-Karp algorithm running in m($&
o
) Andrew V. Goldberg and Robert Tarjan designed the
push-relabel algorithm having running time of m($
o
&), which is an improvement and better solution
compared to the Ford-Fulkerson method 2, 3. The push-relabel method is mainly based on the
concept of preflow which was originally designed by Alexander V. Karzanov and published 1974
which is 15 years before the designing of the push-relabel algorithm 2, 3. The essence of the
algorithm is pushing as much flow as possible out of the source, and get it to the sink and return
excess flow back to the source. The method is dependent and implemented on three basic concepts
and operations: residual network (in practical implementation), preflows, push and relabel operations.
3.1 Basic concepts and operations
The preflow is a function >: $×$?? that satisfies the capacity constrains while allowing
flow into a vertex to exceed the flow out of the vertex called the relaxation of flow conservation 9.
Excess flow in each vertex is therefore accumulated as a consequence of the preflow. The relaxation
of flow conservation and the excess flow are defined as follows:
• For all vertices 1 ?$?{.,0}.
B>(2,1)
C?D
?B>(1,2)
C?D
?0.
• Excess flow at vertex 1
((1)=B>(2,1)
C?D
?B>(1,2)
C?D
.
A vertex 1?$?{.,0} with positive excess flow is said to be overflowing 9. The push-
relabel algorithm is based on the physical intuition that flow finds its way downhill meaning that each
node is assigned with a label indicating height from the ground. The vertices heights also known as
distance labels are defined and maintained by the algorithm. A height function ??$ ?? is
responsible for heights definition having initial conditions:
• ?(.)=|$|,
• ?(0)=0,
• ?(1)??(2)+1, for every residual edge (1,2)?&U.
If vertex 1 is overflowing, +U
(1,2)>0 and ?(1)=?(2)+1, then >(1,1) can be modified
by pushing the excess flow from 1 to 2. This operation is called the push operation. The total flow

15

being pushed from 1 to 2 is the minimum value between 1 excess flow and (1,2) capacity and it’s
all to avoid 1 excess becoming negative or capacity constrain violation. The push operation makes
sure that the flow is being pushed downhill as per basis of the push-relabel algorithm. The flow pushed
from 1 to 2 is said to be a saturating push if 12 becomes saturated (+(1,2)=0) after the operation;
otherwise it is a nonsaturating push. The pseudo code below illustrates the push operation 9
PUSH (u,v)
1. Applies when: u is overflowing, cj
(1,2);0 and ?(1)=?(2) + 1
2. ?j
(u,v)=min( e(1),+U
(1,2))
3. if (u,v)?E
4. f(u,v)=f(u,v)+?j
(u,v)
5. else
6. f(v,u)=f(v,u)??j
(u,v)
7. e(u)=e(u)??j
(u,v)
8. e(v)=e(v)+?j
(u,v)

If the excess of overflowing vertex 1 cannot be pushed along any vertex 1 outgoing edge
because of the height constrain which implies that flow can be only be pushed downhill (?(1)?
?(2)+1), vertex 1 needs to be raised to a certain height and to accomplish this, a relabel operation
comes into execution. After the relabel operation, u is said to be relabelled. As a consequence of
relabel operation, flow push to one of vertices connected to u gets to be possible. The relabel operation
algorithm is as follows 9:
Relabel (u)
1. Applies when: u is overflowing and for all v?V such that (1,2)?;U,
we have h(u)?h(v)
2. Action: increase the height of u
3. h(u)=1+min{h(v)?(u,v)?Ej
}
3.2 General description
The generic push relabel starts by creating a residual network, initializing preflow values and
performing a set of saturating push operations on all the edges outgoing from the source. The preflow
initialization subroutine also initializes the vertices heights using the height function given by
cj
(u,v)=v
|V|if u=s
0otherwise
.
Initialize-Preflow (G)
1. for each vertex 2?!.$

16

2. h(v)=0
3. e(v)=0
4. for each edge (u,v)?G.E
5. f(u,v)=0
6. h(s)=|V|
7. for each vertex 2?..wxy
8. f(s,v)=c(s,v)
9. e(v)=c(s,v)
10. e(s)=e(s)?c(s,v).
The initialization procedure is then followed by a by sequence of push and relabel operations
executed in no particular order whereby in overall gives the GENERIC-PUSH-RELABEL algorithm.
GENERIC-PUSH-RELABEL (G)
1. INITIALIZE-PREFLOW (G)
2. while there exists an applicable push, or relabel operation
3. select an applicable push or relabel operation and perform it
In formulation and determining the algorithm complexity it is necessary to ensure the
termination of the algorithm. This can be achieved by analysing the number of operations it preforms
which are bound on relabel operation, bound on saturating pushes and bound on non-saturating
pushes. With the realisation of these bounds and data structure designed to choose and execute an
appropriate operation in m(1) time, the time complexity of the algorithm is reduced to m($
o
😉
whereby the bound on relabel operation is m($
o
), bound on saturating pushes is m($;) and time
bound on non-saturating pushes is m($
o
;).
3.3 Implementation
In my implementation of the Push-relabel algorithm, I used the same approach as in my
implementation of Ford–Fulkerson method but with a couple of modifications in the approach. C++
on Visual Studio 2010 Ultimate as an IDE and programming language was used. The Standard
Template Library was also put into use.
As the Push-relabel algorithm is based on the intuition of pushing flow downhill and preflow,
this called for the vertex element to be modified and include excess and height variables. Modular
programming was kept intact as it was the approach used in the previous implementation. With the
bases of modular programming I added two files dedicated to the implementation of the algorithm.
The header file contained the declarations of all the basic operations functions used the execution of

17

the algorithm in whole and in correspondence to the header file I added a source file which had all
the definitions of the functions declared in the pair header file.
The main function which puts all the components of the Generic Push-relabel algorithm takes
a Network as an argument and begins by creating a residual network from the input network given as
an argument. The residual network is the base of all the operations in the algorithm and later at the
end it is used to modify the original network. Secondly, preflow is initialized and the function which
checks for an overflowing vertex in the network is executed. If the vertex overflow function returns
true, the while loop is started whereby it checks every vertex if it’s overflowing and applies the push
or relabel operation depending on the vertex state. The while loop terminates when all the vertices
except for the source and the sink are not overflowing. Lastly, the residual network is transformed to
a flow Network.
The diagrams below illustrate the program implementation execution from the beginning
where the network is transformed into residual network, while loop where the push and relabel
operations are executed and updating the residual network and the residual network being transformed
into flow network. Each loop iteration is resembled by a pair of network diagrams, one showing the
residual network with a highlighted consequent augmenting path while the other shows the
corresponding updated network flow. The input flow network is the one is the one used in the
definition in the section above. The red colour on a vertex indicates that a vertex is active.

Figure 1 Left: an original input flow network ! with a flow > with value |>|=0. Right: the corresponding residual
network !U.

Figure 2 Left: Resulting network after a successful preflow initialization which leaves node a and b active. Right: the
corresponding residual network !U after node S is relabelled in order to push its excess flow towards the sink. The excess

18

at S is then pushed to + and x in two subsequent saturating pushes then pushed to b in a nonsaturating push. Node a
removed from active nodes

Figure 3 Left: flow network ! after relabelling T, pushing its excess to x with saturating push, S and back to source.
Node T removed from active nodes Right: node + gets relabelled then pushes all of its excess to sink and removed from
active nodes.

Figure 4 Left: nod d relabelled, performs saturating push to the sink then remaining excess to node c and gets removed
from active nodes. Node c added to active nodes. Right: node a relabelled and pushes all its excess to the source.

Figure 5 Left: node c pushes all of its flow to the sink thus leaving the network with no active nodes and terminating
the algorithm. Right: the resulting updated flow network ! with the value of maximum flow = 23.

19

4 Computational evaluation
For computational evaluation and proving correctness of my implementations, I performed
computational experiments. The main goal was realizing the most efficient algorithm amongst the
two implemented and these was archived by measuring the time it takes for each method to compute
maximum flow with given number of vertices and edges. Random graph generating algorithm was
implemented which took number of vertices to be generated and number of outgoing edges of each
vertex as arguments. The experiments were done using an intel c++ compiler (parallel studio XE
composer edition 2018) on an intel core i5 CPU. On the first part of the experiment I fixed the number
of vertices to 800 and increased the total outgoing edges per vertex. On the second part I fixed the
number of outgoing edges for each vertex and increased the total number of vertices in the random
network. The experimental results are shown by the figures below.

Figure 1 The above scatter graph with smooth line and markers shows the relation of the increasing number of edges
to the computational time for the two implemented methods. The total number of vertices in the network is fixed to 800.
01020304050607080900100200300400500600Time, secNumber of Out Edges per NodeFord-FulkersonPush-relabel

20

Figure 2 The above scatter graph with smooth line and markers shows the relation of the increasing number of vertices
in the input network to the computational time for the two implemented methods. The total number of outgoing edges
per vertex were fixed to between 200 and 250.

Figure 3: The above scatter graph with smooth line and markers shows the relation of the increasing number of
vertices in the input network to the computational iteration count for the two implemented methods. The total number of
out edges per vertex is fixed to 250.
051015202530300400500600700800900Time, secTotal vertices in networkFord-FulkersonPush-relabel1101001000100001000001000000200300400500600700800900iteration countNumber of nodes in networkFord-FulkersonPush-relabel

21

Figure 4: The above plot shows the behaviour of the Ford-Fulkerson’s method iteration count as the number of nodes
in the network increases. Using the experimental data, the method polynomial curve tends to a constant value
(asymptote) when the method polynomial is divided by its higher degree.

Figure 5: The above plot shows the behaviour of the Push-Relabel algorithm iteration count as the number of nodes in
the network increases. Using the experimental data, the algorithm polynomial curve tends to a constant value
(asymptote) when the method polynomial is divided by the term with higher degree.

22

Conclusion
This research project concerns the maximum flow problem in a network with a single source
and sink.
The main results of the project are as follows:
1. The literature on the maximum flow problem has been studied.
2. The problem statement and a description of the Ford-Fulkerson and Edmonds-Karp algorithm
method have been written.
3. A C++ implementation of the methods has been developed for both algorithms stated in
problem statement.
4. The correctness of the implementations has been verified on a test problem.
5. The experiments show the Push-Relabel algorithm out preforms the Edmonds-Karp algorithm
(Ford-Fulkerson algorithm special implementation) in terms of time.

23

Literature
1. L.R. Ford, D.R. Fulkerson. Maximal flow through a network. Canadian Journal of
Mathematics. 8, 399 (1956)
2. A.V. Goldberg, R.E. Tarjan. A new approach to the maximum-flow problem. Journal of the
ACM. 35 (4), 921 (1988)
3. A.V. Goldberg, É. Tardos, R.E. Tarjan. Network flow algorithms. Tech. Report STAN-CS-
89-1252, Stanford University CS Dept. (1989)
4. R.K. Ahuja, T.L. Magnanti, J.B. Orlin. Network Flows: Theory, Algorithms and Applications.
Prentice Hall (1993)
5. A. Schrijver. On the history of the transportation and maximum flow problems. Mathematical
Programming. 91 (3), 437–445 (2002)
6. A. Gibbons. Algorithmic Graph Theory. Cambridge University Press (1985)
7. V. King, S. Rao; R. Tarjan. A Faster Deterministic Maximum Flow Algorithm. Journal of
Algorithms. 17 (3), 447–474 (1994)
8. J. Kleinberg, É. Tardos. Algorithm design / first edition. Addison-Wesley (2006)
9. T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein. Introduction to algorithms / third edition.
MIT Press (2009)
10. S. Dasgupta, C. Papadimitriou, U. Vazirani. Algorithms / first edition. McGraw-Hill
Education (2006)
11. R. Sedgewick, K. Wayne. Algorithms / fourth edition. Addison-Wesley (2011)

24

Appendix A. Source code listing
//Edge.h
#pragma once
class Vertex;

class Edge{
private:
int value; // edge flow
int capacity;
/// use indexes in Network::vertices instead of pointers
Vertex * start;
Vertex * end;

public:

Edge(int val = 0, int cap = 0, Vertex * s = 0, Vertex * e = 0);

void AddValue(int a); //modifying edge flow

int getCapacity() const;
void setCapacity(int cap);
void upateCapacity(int capacity);

int getValue() const;
void setValue(int val);

Vertex* getStart() const ;
void setStart(Vertex * s) ;

Vertex* getEnd() const ;
void setEnd(Vertex * e) ;
};
//edge.cpp
#include “Edge.h”
#include “Vertex.h”

Edge::Edge(int val, int cap, Vertex * s, Vertex * e): value(val), capacity(cap),
start(s), end(e)
{}

void Edge::AddValue(int a){

25

value +=a;
}

int Edge::getCapacity() const{
return capacity;
}

void Edge::setCapacity(int cap){
capacity = cap;
}

void Edge::upateCapacity(int capacity)
{
this-;capacity += capacity;
}

int Edge::getValue() const{
return value;
}

void Edge::setValue(int val){
value = val;
}

Vertex* Edge::getStart() const {
return start;
}

void Edge::setStart(Vertex * s) {
start = s;
}

Vertex* Edge::getEnd() const {
return end;
}

void Edge::setEnd(Vertex * e) {
end = e;
}
//Vertex.h
#pragma once

26

#include “Edge.h”

#include
#include

class Vertex {
private:
std::vector edgesOut;
std::vector edgesIn;
size_t index;
int height = 0;
int excess = 0;

public:
Vertex()
{}
Vertex (size_t ind, int h, int ex): index(ind), height(h), excess(ex)
{}
void addEdge(const Edge; edge);
std::vector; getEdgesOut();
const std::vector; getEdgesOut() const;
std::vector; getEdgesIn();
const std::vector getEdgesIn() const;
int sizeEdgesOut()const;
void setIndex(size_t newIndex);
size_t getIndex() const;
void setEdgeIn(size_t idx, Edge edge);
void setEdgeOut(size_t idx, Edge edge);

//For height init and modification
void setHeight(int h);
int getHeight() const;

//for ecxess init and modification
void addEcxess(int ex);
void setEcxess(int ex);
int getExcess() const;

// Temporary for debugging
void print() const {
std::cout getIndex();
Vertex* oldEnd = newVerticesedgesOutj.getEnd()-;getIndex();
if (edgesOutj.getValue() == edgesOutj.getCapacity())
result-;AddEdge(Edge(0, edgesOutj.getCapacity(), oldEnd,
oldStart));
else if (edgesOutj.getValue() == 0)
result-;AddEdge(Edge(0, edgesOutj.getCapacity(), oldStart,
oldEnd));
else //if (edgesOutj.getValue() AddEdge(Edge(0, (abs(edgesOutj.getCapacity() –
edgesOutj.getValue())), oldStart, oldEnd));
result-;AddEdge(Edge(0, edgesOutj.getValue(), oldEnd,
oldStart));
}
}
}

return result;

35

}

vector constructPath(const Network * G, map; distance) {
vector invertedPath;
Vertex* currentVertex = G-;getSink();
while (currentVertex != G-;getSource()) {
const vector edgesIn = currentVertex-;getEdgesIn();
int dist = distancecurrentVertex;
for (size_t i = 0; i = 0; i–)
path.push_back(invertedPathi);
return path;
}

vector computeAugmentingPath(const Network * G) {
vector next;
map distance;
Vertex* source = G-;getSource();
next.push_back(source);
distancesource = 0;
for (size_t i = 0; i getSink())
return constructPath(G, distance);
const vector edgesOut = currentVertex-;getEdgesOut();
for (size_t j = 0; j ; edgesOut.size(); j++) {
Vertex* endVertex = edgesOutj.getEnd();
if (distance.count(endVertex) == 0)
{
distanceendVertex = distancecurrentVertex + 1;
next.push_back(endVertex);
}
}
}

36

// If the loop is over and we did not construct a path, there is no path
return vector();
}

int minCapacity(const vector; augPath) {
int result = abs(augPath0.getCapacity());
for (size_t i = 0; i ; augPath.size(); i++) {
if (abs(augPathi.getCapacity()) getVertices();
for (size_t i = 0; i getIndex();
int endIdx = (int)augPathi.getEnd()-;getIndex();
// Check if edge in the path is same direction as in network
std::vector edgesOut = verticesstartIdx-;getEdgesOut();
for (size_t j = 0; j getIndex() == endIdx) {
// found edge in the same direction as in the path
Edge newEdge = edgesOutj;
newEdge.setValue(newEdge.getValue() + valueIncrement);
Original-;changeEdge(newEdge);
break;
}
// Check if edge in the path in opposite direction as in network
std::vector edgesIn = verticesstartIdx-;getEdgesIn();
for (size_t j = 0; j getIndex() == endIdx) {
// found edge in the same direction as in the path
Edge newEdge = edgesInj;
newEdge.setValue(abs(newEdge.getValue() – valueIncrement));
Original-;changeEdge(newEdge);
break;
}
}
}

37

void FordFulkerson(Network * n)
{
int count = 0;
Network * residual = NULL;
bool stop = false;
while (stop == false) {
//std::cout

x

Hi!
I'm Mia

Would you like to get a custom essay? How about receiving a customized one?

Check it out