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
