TE6385 ALGORITHMIC ASPECTS OF TELECOMMUNICATION NETWORKS AN IMPLEMENTATION OF NAGAMOCHI-IBARAKI ALGORITHM TO FIND MINIMUM CUT IN AN UNDIRECTED GRAPH By VARSHINI VENKATESAN (UTD ID : 2021146823)OVERVIEW OF THE PROJECT: - To implement the Nagamochi-Ibaraki algorithm for finding a minimum cut in an undirected graph and experiement with it. - Run the program on randomly generated examples. These random graphs should be generated such that the user first selects the number n of nodes and the number m of edges. While the program should work with any value of n, in the examples use n = 25. The value of m will vary. Then the program creates a graph with n nodes and m edges, in which the edges are selected randomly, with parallel edges allowed. - Experiment with random graph examples to find an experimental connection between the number of edges and the edge-connectivity ƛ(G). (If the graph happens to be disconnected, then take ƛ (G) = 0.)How does the connectivity depend on the number of edges? Show the found relationship graphically in a diagram, exhibiting ƛ (G) as a function of m, while keeping n = 25 fixed. - To find the number of new random edges need to be added to it to increase the connectivity by one. - To find f(m) (denotes the number of random nodes which increases the connectivity by one) and plot it with respect to number of edges (m). THE GIVEN INPUTS: Let the number of nodes be fixed at n=25 and the number of edges m be varying between 50 and 550 increasing in the steps of 5. Once the value of m is selected the program creates a graph with n=25 and m edges. - The edge connectivity is denoted by λ(G). - f(m) denotes the number of random nodes which increases the connectivity by one.NAGAMOCHI-IBARAKI ALGORITHM: A deterministic algorithm was given by Nagamochi and Ibaraki for finding minimum cuts in a graph. Let us take the following denotations for a any graph G: Edge Connectivity of the whole graph as λ (G) and Edge connectivity between a node pair X and Y as λ(x,y) . The Nagamochi and Ibaraki algorithm is also based on the following Contraction Algorithm. Step 1: Let (a,b) be any edge in graph G that is picked randomly from the set of edges of the graph. Step 2: Edge (a,b) is contracted and the arising loops are removed but the parallel edges are kept. Then the resulting graph is denoted by G/(a,b). Step 3: If there are more than 2 nodes in G/(a,b) then Step 1 is repeated else the set of edges between the remaining two nodes form a cut. If the graph obtained by contracting nodes x,y is also denoted as Gxy. Then the connectivity of a graph G is given by the recursive formula : λ(G) = min { λ(x,y), λ(Gxy) } To find such a pair x,y of nodes, the Nagamochi-Ibaraki algorithm uses Maximum Adjacency (MA) Ordering. An MA ordering of v1, v2, …, vn is got by the following recursive algorithm: Step 1 : A node for v1 is picked. Step 2 : once v1, v2, …, vi is chosen, vi+1 is picked such that it has the maximum number of connecting edges with the set { v1, v2, …, vi }. Now, we further describe few important terms that will be used in the implementation of the algorithm. The average degree of the graph needs to be computed for our problem. The average degree of the graph is represented by d. It can be computed using the relation d=2m/n where m and n are the number of edges and nodes of the graph respectively. The main purpose of the calculation of the average degree is to plot the following relationships : i) Average Degree vs Minimum Cut ii) Average Degree vs Critical EdgesWe have introduced another new term critical edge. Critical edge is an edge the deletion of which reduces the minimum cut of the graph. ). It can be represented as follows : _ (G - e) < _ (G) Where G – e – graph with edge e removed _ (G - e) – edge - connectivity of the graph after the edge is removed _ (G) – edge - connectivity of the original graph A graph can have many numbers of critical edges. But number of critical edges should be greater than or equal to the minimum cut of the graph λ (G). We calculate the critical edges of the graph by the following recursive algorithm : 1. The minimum cut is calculated from the program. 2. From the whole set of edges, select one edge randomly. 3. Now delete the edge and calculate the minimum cut of the new graph which has resulted after the deletion of the selected edge. 4. If this minimum cut is less the minimum cut of the original graph then the deleted edge is classified as critical edge. 5. Now steps 2-5 is repeated for all the remaining edges of the graph. 6. The sum of all such edges obtained in step 4 will give the total number of critical edges for the graph. PSEUDOCODE FOR NAGAMOCHI-IBARAKI ALGORITHM: The pseudo code for the Nagamochi-Ibaraki algorithm is given below. 1. Take the values of number of nodes and number of edges as input from the user. 2. The random number generator function to assign m random edges between n nodes. 3. Store the initial degree of each node in a 1D array and the number of edges from each node in a 2D array. 4. If the graph is disconnected the minimum cut = 0.5. Calculate the MA ordering using the following steps: a. Choose a random node as the first node. b. Once v1,.......,vi is already chosen take a node for vi+1 that has the maximum number of edges connecting with the set {v1,.......,vn}. c. This gives the MA ordering for all the nodes v1,.......,vn. d. The connectivity between the last two nodes in the MA ordering is equal to the degree of the last node. λ(vn-1,vn) = d(vn) 6. Contract the graph with the following steps. a. Merge the last two nodes in the MA ordering vector. b. This is one by putting all the edges in the last node on to the 2nd last node such that the parallel edges are kept and the loops are ignored. c. Repeat this step until there are only two nodes left. This will give the minimum cut value which is equal to the degree of the last node. 7. Calculate the number of critical edges in the following way: a. Choose a random edge from the graph and make it zero(eliminate it from the graph). b. Change the degree of the neighboring nodes of the deleted edge. c. Calculate the minimum cut of the resulting graph with m-1 edges using steps 5&6. d. If this is less than the minimum cut for the graph then update
View Full Document
Unlocking...