ALGORITHMIC ASPECTS OFTELECOMMUNICATION 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:o Choose a node v1 randomly chosen from the given set of nodes (v1,v2, …,vn) and included the node in the MA Ordering set.o From the remaining nodes, choose a node that has the maximum number of edges connecting it with nodes in MA Ordering set.o The process is recursively applied to move all nodes to MA Ordering set. 2. Do Contraction (Merging):o From the MA Ordering and Graph Matrix, pairs of nodes are contracted (merged) starting from the last node.o During contraction of nodes (lastBeforeNode, lastNode), the edges of lastNode are carried to lastBeforeNode and edges of lastnode are deleted inferring the deletion of lastNode.o Parallel 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 timeso Find degree of lastNode of maxAdjOrdering and add it to vertexDegree[count]o Merge 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 forevero Pick 2 random nodes nodex1,nodex2o If 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 …
View Full Document
Unlocking...