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

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