IMPLEMENTATION AND VISUALIZATION OF EDMOND KARP MAXIMUM FLOW FINDING ALGORITHM

Abstract

Graph is an effective data structure to solve the complex problems in Computer Sciences. Maximum Flow Problem is one of those problems, which are based on Graph data structure. The basic problem of finding a maximal flow in a network occurs not only in transportation and communication networks but also in currency arbitrage, image enhancement, machine scheduling and many other applications. There are many algorithms designed to solve the maximum flow problems. The Edmond Karp algorithm is also included in the list of those algorithms, which provides the efficient and optimal solution for the maximum problems. It is upgraded version of Ford Fulkerson Method. The performance of the Edmond Karp algorithm is better than the Ford Fulkerson Method regarding to searching of paths in network graph. Edmond Karp algorithm uses the Breadth-first search (BFS) algorithm to find the augmenting paths in the network graph [6]. In this research, the performance of the Edmond Karp algorithm is analysed and evaluated through a given conditions in the form of input data. For this purpose, simulation is designed to monitors the efficiency of the algorithm in respect of different output parameters, like running time, number of paths and maximum flow. The concept of the busy node is also elaborated in this research work. Busy node is the particular node in the network graph, which is existed in maximum number of augmenting paths. Normally it contains maximum share of the flow in the graph. The idea of the busy node can be utilized for optimal solutions of image processing and network related problems. The simulation uses datasets for the experimental evaluation of the Edmond Karp algorithm. These datasets are collected through different methods: first one includes “Auto Generated Random Graphs” and other is “User Defined Graphs”. The simulation is also stored the experiment results to observe the behaviour of the algorithm. At the end of this report, cumulative average time is calculated from the experiment results. These cumulative average times indicate the best as well as worst case scenarios of the algorithm. In best case, it produces 2.851ms and in worst case 19.7143ms.