The University of Texas at DallasAlgorithmic Aspects of TelecommunictionsNetworksProject 2Implementation of theNagamochi-Ibaraki Algorithm forfinding the minimum cut in anundirected graphAuthor:Richard AntiabongProfessor:Andras FaragoNovember 11, 2012Chapter 1IntroductionThis project is an implementation of the Nagamochi-Ibaraki algorithm for finding the mini-mum cut in an undirected graph. The aim is to determine the impact of the average degreeon the edge connectivity of a graph λ(G) as well as the critical edges of the same graph.To investigate this, an undirected graph G (with fixed 26 nodes) is generated using thevarious m values which is the number of edges the graph can have. G is allowed to haveparallel edges and there is no specific source destination pair specified for G. The value ofm is varied between 26 and 5200 with increments of 26 every at every round. Edges arerandomly assigned to G until all m edges have been assigned. It should be noted howeverthat the density of the edges in G is increased for every round as expected.The average degree δ =2mnis computed for every m used to create G while keeping nfixed at 26 throughout the entire simulation. The edge connectivity is computed for each Gusing the algorithm given in class lecture note. The pseudo-code for finding this minimumconnectivity is given in the next chapter. The result of the edge connectivity λ(G) is plottedagainst the average degree δ for every m.The number of critical edges for each graph is also determined for every m and this againplotted against δ for every m. An edge is a critical edge if its deletion results in a graph G0whose connectivity is less than the original graph G.1Chapter 2Algorithm and Program Design2.1 Programming Language/Simulation ToolThe programming language and simulation tool used was MATLABR. This simulation toolwas selected because of its inbuilt capacity to draw graphs as well as having its own ‘verypowerful’ programming language syntax.2.2 Program InputThe algorithm was designed based on the specifications given in the lecture note. However,to simulate the algorithm, we randomly selected m pairs of vertices out the given 26 nodeswith repetitions allowed. The frequency for each selection was stored in a matrix M26×26.This resulted in an adjacency matrix representation of the graph G. m was varied between26 and 5200 at increments of 26.2.3 Algorithm and functionsThe simulation comprised Six main MATLABRm-files. The first m-file function [G k] =generateGraph(m) prepares the input graph G that would be returned to the startProgramm-file. The generateGraph m-file takes an input m which it received as argument from thestartProgram m-file. G is an adjacency matrix representation of the graph.The m-file [G k c edge avgDeg conn] = startProgram(Simrnds) takes an input argumentSimrnds and runs the simulation for Simrnds different instances of the graph G, each timewith G generated using m value that equal to 26 × Simrnds. Once each G is generated,the function [connectivity] = nagamochi(G) is called which computes the connectivity andstores it in an array for every average degree d which is also computed per m value. ThestartProgram also computes the critical edges for each G by calling another function [c edge]= criticalEgde(G, c) and also stores the result in an array for every G2The m-file [connectivity] = nagamochi(G) computes the connectivity of the graph G. Itcalls the function [ma] = MA Ordering (G) which compute the maximum adjacency MAordering vector and returns the degree δ of last node in the vector as described in the lecturenote. The function nagamochi(G) calls the function mergeNode which computes and returna graph Gxywhich is a graph one vertex less than graph G and results from a merger ofthe last two vertices in the MA vector computed above. Lastly, the function nagamochirecursively calls itself on the newly generated graph Gxy and stops on reaching the basecondition where the graph has just two vertices. It then computes the connectivity selectingthe smaller of δ and nagamochi(Gxy). The pseudocode for this algorithm is described below.Finally the m-file [c edge] = criticalEgde(G, c) computes the connectivity for the graph(G − e) and checks whether this value is less than the connectivity for G. If this is true,then e is a critical edge. This functions checks all the possible edges in G and increments avariable c edge for every critical edge found in G.Pseudocode for the Nagamochi-Ibaraki AlgorithmNagamochi(G)Data: Graph GResult: minimum connectivity λ(G)initialization;if G has only 2 nodes thenreturn the degree one of the two nodes;elsecall procedure MA Ordering( G);λ1= δ(last node in MA Ordering vector);Gxy= Merge Nodes(last two nodes in MA Ordering vector above);λ2= Nagamochi(Gxy);λ(G) = minimum{λ1, λ2};return λ(G);endend procedure NagamochiAlgorithm 1: Pseudocode for Nagamochi-Ibaraki Algorithm for finding minimum cutImplementation details of the six m-files discussed is presented in the Appendix sectionof this report.3Chapter 3Results and DiscussionThe results of this project is presented pictorially as graphs. Figures 3.1 - 3.2 depict thehow the average edge of a graph affects its connectivity and critical edges. In Figure 3.1,we can see that the relationship is a linear growing function. This makes sense as a highlyconnected graph with many parallel edges is expected to have higher connectivity.Figure 3.2 though an increasing function, shows another kind of relationship which is loga-rithmic in nature. It can be observed that when m the number of edges becomes sufficientlylarge (resulting in a large average degree for each node), the number of critical edges stabilizesbetween 50 and 55. This is about twice the number of vertices which 26. This phenomenoncan be explained as follows: The overall increase in average degree leads to an increase inthe number of critical edges. However, at a large enough value for average degree (greaterthan 50), where the critical edges converge at values between (50 - 52), every node now hassufficiently large number of parallel edges between every other node. This means that weexpect a critical edge to exist between every pair of node. At this point, no matter howmuch the average degree is increased, it doesn’t increase the critical edges as all adjacentvertices have already been covered.40 50 100 150 200 250 300 350 400050100150200250300350400450Avg Degree (d)ConnectivityFigure 3.1: Plot showing
View Full Document
Unlocking...