Algorithmic Aspects of Telecommunication Networks Implementation of Nagamochi-Ibaraki Algorithm for finding a minimum cut in an undirected graph Project 2 Nazim Uddin Ahmed [email protected] 1 Introduction: This project is an implementation of the Nagamochi-Ibaraki algorithm for finding a minimum cut in an undirected graph. After implementing the algorithm, we have to do some experiment with it. Often we want to find minimum cut in an entire graph. This cut is not for a specific source and destination. The size of the minimum cut represents the connectivity of the entire graph. Basically this minimum cut tells us how many links have to fail to disconnect the network (assuming that the original graph is connected). Another name of this minimum cut is the edge-connectivity of the graph. Nagamochi-Ibaraki algorithm is a simple deterministic algorithm for finding the edge-connectivity in a graph. In this project we have to run the program on randomly generated graphs. Number of nodes(n) for the graph is 25 while number of edges(m) will vary between 50 and 550. For each value of m, we have to find the edge-connectivity, λ(G) of the graph. Then we need to show relationship between m and λ(G) graphically in a diagram. For lower value of m, λ(G) will be low and if we increase value of m then value of λ(G) should also be increased. We will show this relationship by a diagram after implementing the algorithm. Second part of this project focus on how we can increase the connectivity of a graph by adding new random edges. In this project we denote number of new edges added to a graph to increase the connectivity by 1 as f(m). For different value of m, we will then show the relationship between m and f(m) graphically.Chapter 2 Software Design and Algorithm: 2.1 Simulation Tool: MATLAB is used in this software as programming language/simulation tool. This simulation tool is used for its built in capabilities of handling graph matrix and graph drawing. As MATLAB is well known for its reliability and it can easily plot graphs for any weight matrix, we can use it to fulfill our purpose efficiently. 2.2 Algorithm and Functions: Edge-connectivity of a graph G is denoted by λ(G) and λ(x,y) denotes the connectivity between two different nodes x and y. Let Gxy be the graph obtained from G by contracting (merging) nodes x and y. According to the Nagamochi-Ibaraki algorithm, for any two nodes x and y: λ(G) = min{ λ(x,y), λ(Gxy)} In order to implement the algorithm, I wrote several functions: genGraph(n,m): Generate a random graph with n nodes and m edges. getMinCutUsingNIAlgo(G): Find the minimum cut of graph G addEdgeInGraph(n, G): Add a random edge in the graph G with n nodes findMaximumOrdering(G): Find the maximum ordering of graph G mergeGraph(G, x, y): Merge the nodes x and y in G and return the merged graph. getDegreeOfNode(G, x): Get the degree of node x in graph G The main program will call these functions to implement the algorithm and to fulfill the requirement of the project. These functions used the pseudo codes described in the following sections. Implementations of these functions are attached in the appendix section.2.3 Pseudo-Code of Nagamochi-Ibaraki algorithm: This is a simple deterministic algorithm for finding minimum cuts of a graph. The algorithm will return the minimum cut which will tell how many links have to fail to disconnect the network. It recursively runs the process for smaller sub-graph and finally will combine the results to give the actual edge-connectivity of the graph. NAGAMOCHI-IBARAKI (G) Input: Graph G Output: Minimum connectivity λ(G) Initialization; if G has less than 2 nodes then return 0; else if G has only 2 nodes then return the degree of one of two nodes; else call procedure FIND-MA-ORDERING(G); minCutValue degree of last node in MA ordering; Gxy MERGE_NODES(G, last 2 nodes from MA ordering matrix); if Gxy has more than 2 nodes then minCutValue = min(minCutValue, NAGAMOCHI-IBARAKI(Gxy)) end return minCutValue; end end procedure NAGAMOCHI-IBARAKIFIND-MA-ORDERING(G) Input: Graph G Output: Maximum Ordering matrix of the graph and degree of last node Initialization; Choose a random node v1 ϵ V(G) MA_Ordering {v1} while all the nodes vi ϵ V(G) not included in MA_Ordering do Choose a node vi+1 which has maximum connectivity with MA_Ordering MA MA U {vi+1} return degree of last node from MA_Ordering and MA_Ordering end procedure FIND-MA-ORDERING MERGE-NODES(G, v1, v2) Input: Graph G, node v1 and v2 Output: Merge node v1 and v2 in G and return the merged graph. Initialization; Create G’ such that v’ ϵ V(G’) and v ϵ V(G) and v’ = v and v’ ≠ v1 and v’ ≠ v2 Add new node vNew in G’ for each edge (u1,v1) ϵ E(G) do add edge (u1, vNew) in G’ where u1 ≠ v2 end for each edge (u2,v2) ϵ E(G) do add edge (u2, vNew) in G’ where u2 ≠ v1 endfor each edge (v1, u1) ϵ E(G) do add edge (vNew, u1) in G’ where u1 ≠ v2 end for each edge (v1, u2) ϵ E(G) do add edge (vNew, u2) in G’ where u2 ≠ v1 end return G’ end procedure MERGE-NODESChapter 3 Results and Observations: 3.1 Connectivity of Graph: The software will find the edge-connectivity of randomly generated graphs. Number of nodes in each graph will be same but number of edges (m) will vary from 50 to 550 increasing by 5 in each step. For each value of m, we will generate a new random graph with 25 nodes and m number of edges. Then connectivity of that graph λ(G) will be calculated. In our simulation, we found that the connectivity of the graph is increasing while m is increasing. Figure 3.1: Relationship between number of edge and connectivityFrom the graph we see that value of λ(G) is increasing with value of m. This graph is not smooth as for each value of m, we are using random graph. If we take different random graph for the same m value and get the average λ(G), then the curve will be smoother which we can see in the following figure: Figure 3.2: Relationship between number of edge and average connectivity In this graph, we see that λ(G) is increasing as m is increasing. This is because, as m is increasing, more new paths between two nodes in being added and this eventually increased the connectivity of the graph.3.2 m vs f(m): Sometimes we are asked to find the number of edges need to be added (f(m)) to increase the
View Full Document
Unlocking...