1 ALGORITHMIC ASPECTS OF TELECOMMUNICATION NETWORKS CS 6385 PROJECT #2 IMPLEMENTATION OF NAGAMOCHI – IBARAKI ALGORITHM Submitted by Devangna Kaushish ID:20211724992 CONTENTS OBJECTIVE ........................................................................................................ 3 NAGAMOCHI AND IBARAKI ALGORITHM ................................................ 4 IMPLEMENTATION ............................................................................................5 FLOWCHART .......................................................................................................6 RESULTS ...............................................................................................................7 CONCLUSION .......................................................................................................11 APPENDIX .............................................................................................................12 REFERNCES ..........................................................................................................173 OBJECTIVE The aim of this project is to create an implementation of the Nagamochi – Ibaraki Algorithm for finding the minimum cut in an undirected graph and experiment with it. The tasks to be performed are:- - Implementation of the Nagamochi – Ibaraki Algorithm, explaining how it works and providing its pseudo code. - Writing a computer program showing its implementation. - Run the program on randomly generated examples. Consider the number of nodes to be fixed at n=25. Let m be the number of edges which vary between 50 and 550, increasing in steps of 5. Once a value of m is selected, the program creates a graph with n=25 nodes and m edges. Actual edges are selected randomly with parallel edges allowed and excluding self loops. - Experiment with your random graph examples to find an experimental connection between the average degree of the graph and its edge- connectivity λ(G). λ(G ) is taken to be 0 if the graph happens to be disconnected. The connectivity depends on the average degree. The average degree in a graph characterizes the density of the graph, as it is expressible as d = 2m/n, where m; n are the number of edges and nodes, respectively. The relationship between λ(G) as a function of the average degree d, while keeping n = 25 fixed is exhibited through a diagram. - Let us call an edge critical, if its deletion decreases the connectivity. That is, an edge e is critical, if λ(G-e)< λ(G), where G-e denotes the graph G with edge e deleted. Let C(G) denote the number of critical edges in graph G. Using the random graphs generated above, show an experimental relationship between the number of critical edges and the average degree d of the graph. That is, show C(G) graphically as the function of d, while keeping n = 25 fixed. - To give a short explanation to describe why the functions in items (4) and (5) look the way the look. We need to explain what behaviour is expected.4 NAGAMOCHI-IBARAKI ALGORITHM Nagamochi-Ibaraki Algorithm is a simple deterministic algorithm discovered by Nagamochi and Ibaraki for finding minimum cuts of a graph G. Let the edge connectivity of a graph G be denoted by λ(G) and connectivity between two different nodes x and y be denoted by λ(x,y). Let Gxy be the graph obtained from G by merging the nodes x and y. In this operation we omit the possibly arising loop (if x, y were connected in G), but keep the parallel edges. We can now use the following result that is not hard to prove: For any two nodes x and y λ(G) =min{ λ(x,y) , λ(Gxy) } Thus, if we can find two nodes x,y for which λ(x,y) can be computed easily (without a flow computation), then the above formula yields a simple recursive algorithm. One can easily find such a pair of nodes. This is done via the Maximum Adjacency (MA) ordering. An MA ordering v1,....,vn of the nodes is generated recursively by the following algorithm:- - Take any of the nodes for v1. - Once v1,....,vn is already chosen, take a node for vi+1 that has the maximum number of edges connecting it with the set { v1,....,vn }. Nagamochi and Ibaraki proved that this ordering has the following nice property: Theoram: In any MA ordering v1,....,vn of the nodes λ(vn-1,vn)=d(vn) holds, where d(.) denotes the degree of the node. Therefore, it is enough to create an MA ordering, as described above, and take the last 2 nodes in this ordering for x, y. Then the connectivity between them will be equal to the degree of the last node in the MA ordering. Then one can apply the above formula recursively to get the minimum cut. Here we make use of the fact that it reduces the problem to computing λ(Gxy) and Gxy is already a smaller graph.5 IMPLEMENTATION Implementation – C language Graph Implementation - Excel The Implementation of the Nagamochi-Ibaraki Algorithm for nodes=25 and value of m between 50 to 550 is done as follows:- The main method contains the four functions-createGraph(),MA_Order(),CutMinimum() and Generation_CriticalEdges(). 1. The number of nodes are taken as 25 and we find the minimum cut of the graph by taking edges in the range 50 to 550 in increments of 5% , for the given number of the nodes. Then we create the graph, find the minimum cut and find the critical edges. This entire action is performed by the main() method. 2. A graph is created by using the function rand() which is stored as a 2-dimensional array in the variable graph[][]. A copy of this is stored in graph_copy[][] which is used to find the critical edges. This is performed by the createGraph() method. 3. Then we find the minimum cut of the graph. This is done by taking the total number of nodes in the original graph and the remaining nodes as its argument. This works on the variable graph[][] and the minimum cut of the graph is returned. Then MA ordering helps to compute the minimum cut between the last two nodes in the ordering. If the graph is disconnected, 0 is returned. The degree of the last node in MA ordering is the minimum cut between the last two nodes. These two nodes are then merged and is compared with the minimum cut of the merged graph. However, if only two nodes remain then the minimum cut of the last two nodes is returned. This is performed by the CutMinimum()
View Full Document
Unlocking...