ALGORITHMIC ASPECTS OF TELECOMMUNICATION NETWORKSTE 6385Project 2 Implementation of Nagamochi Ibaraki AlgorithmBy,Gurudutt NarasimhaNet Id: gxn120830SYNOPSIS:The goal of this project is to find the ‘minimum cut’ in an undirected graph by using deterministic approach proposed in the Nagamochi Ibaraki algorithm.OBJECTIVE:Using the given number of nodes and edges obtained by the randomly chosen values in the graphØTo obtain a graph matrix by implementing Nagamochi Ibaraki algorithmØTo run the algorithm for different values of m, number of edges and determine the edge connectivity of the graph.ØTo construct a graph to show how the edge connectivity of the graph depends on number of edges in the graph.ØTo construct a between the number of additional edges required to increase edge connectivity of the graph by 1 and the number of edges in the graph.GIVEN:Number of nodes in the network = 25INPUT:ØNumber of nodes N is given as input.ØRandom values of number of edges, m is provided as the input.OUTPUT:The program will result in generating the network topology according to the capacities assigned to the links.ØRun the program on various values of m(50 to 300) with N fixed (N=25).ØFind the graph matrix generated for every case.ØFind the minimum cut of the graph obtained.ØIt is required to show the relationship between edge connectivity and m, number of edges in the graph with the help of a graph. ØIt is required to show the relationship between number of additional edges required to increase connectivity by 1 and m, number of edges in the graph with the help of a graph.OVERVIEW:Minimum Cut (Edge-connectivity) for a graph G is defined as,λ (G) = minimum number of edges that need to be deleted to disconnect G.λ (x,y) = minimum number of edges that need to be deleted to disconnect nodes x ≠ y.Nagamochi Ibaraki algorithm:The deterministic algorithm finds the edge connectivity in a graph G using the relation:λ (G) = min { λ (x,y), λ (Gxy) }1. First, find the Maximum Adjacency Ordering:oChoose a node v1 randomly chosen from the given set of nodes (v1,v2, …,vn) and included the node in the MA Ordering set.oFrom the remaining nodes, choose a node that has the maximum number of edges connecting it with nodes in MA Ordering set.oThe process is recursively applied to move all nodes to MA Ordering set. 2. Do Contraction (Merging):oFrom the MA Ordering and Graph Matrix, pairs of nodes are contracted (merged) starting from the last node.oDuring contraction of nodes (lastBeforeNode, lastNode), the edges of lastNode are carried to lastBeforeNode and edges of lastnode are deleted inferring the deletion of lastNode.oParallel edges are retained and loop edges are removed.The edge-connectivity is calculated over pairs of nodes (n-1 times) using the theorem,λ (lastBeforeNode,lastNode) = degree(lastNode)λ (G) = min λ (x,y) [for all (x,y)]λ (G) is the size of minimum cut.PSEUDO CODE :Nagamochi Ibaraki algorithm described above is used to find the minimum cut of an undirected graph. The implementation is done in Java.Pseudo Code:Prompt the user to enter the number of nodes ‘n’ and number of edges ‘m’.Create Random Graph:§Input: numberOfNodes ‘n’ and numberOfEdges = ‘m’§Initialize edgeCount = 0§Initialize graphMatrix of size (n x n) = 0 ; where n = numberOfNodes§While edgeCount < numberOfEdgesPick two random nodes, Node1 ≠ Node2If graphMatrix[Node1][Node2] ≠ 1graphMatrix[Node1][Node2] = 1edgeCount++§Output: graphMatrix[n][n]Average Degree of a Graph:§Input: n, m§Output: Average degree of graph = (2 * m) / nMaximum Adjacency Matrix:§Input: graphMatrix[n][n]§Initialize counter = 0§Pick a random node and include it in MA Ordering set§Increment counter§While counter < numberOfNodesFrom the remaining nodes, pick a node that has the highest degree with the nodes in MA Ordering set§Output: maxAdjOrdering[n]Edge Connectivity /Minimum Cut:§Input: graphMatrix[n][n], maxAdjOrdering[n]§Initialize minimumCut = 0§Initialize array vertexDegree to size of ‘n’§Do contraction N – 1 timesoFind degree of lastNode of maxAdjOrdering and add it to vertexDegree[count]oMerge the lastNode and lastBeforeNode. Eliminate loops and retain parallel edges§Pick the smallest entry of vertexDegree array as minimumCut§Output: Edge-connectivity of graphNumber of additional edges required to increase connectivity by 1, f(m):§Input: graphmatrix[n][n],maxAdjOrdering[n], n , minimum cut§Initialize the numberOfAdditionalEdges = 0§Execute foreveroPick 2 random nodes nodex1,nodex2oIf graphMatrix[Node1][Node2] ≠ 1 and graphMatrix[Node1][Node2] = 1Øfm++Øobtain minimumCut of new graph, mCutØif(mCut ==(minimumCut + 1))§Output: number of additional edges required to increase connectivity by 1 given by fmRESULTS:1) For n=25 and m=50Enter the number of Nodes (n): 25Note: Given 25 nodes, Maximum number of edges = 300Enter the number of Edges (m): 500 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 1 0 1 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 1 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 1 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 1 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 1 0 0 0 0 1 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 1 0 0 0 0 1 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 1 1 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 1 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 1 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 …
View Full Document