1IMPLEMENTATION OF NAGAMOCHI IBARAKI ALGORITHM TO FIND THE MINIMUM CUT IN THE GRAPHA PROJECT RERPORT Submitted byUDHAYAPRAKASH RAVINDRANUTD ID: 20210508482TABLE OF CONTENTSCHAPTER NO. TITLE PAGE NO.1 INTRODUCTION 3 1.1 OBJECTIVE 3 1.2 SHORT DESCRIPTION OF NAGAMOCHI IBARAKI ALGORITHM3 1.3 WORKING OF THE ALGORITHM32 PSEUDO CODE 43 GRAPHS AND RESULT 8 3.1 GRAPHS 8 3.2 RESULT 11APPENDIX 133CHAPTER 1INTRODUCTION1.1 OBJECTIVE:To implement the Nagamochi Ibaraki Algorithm using MATLAB to find the minimum cut in a graph and 1. Plot a graph between average degree of the graph with ‘n’ nodes and its connectivity.2. Plot a graph between average degree of the graph with ‘n’ nodes and number of critical links in it.3. Plot a graph between average lamda(Gk) of the decending degree ordered graph and ‘k’- the number of nodes of subgraph for various random graphs generated. 1.2 SHORT DESCRIPTION OF NAGAMOCHI IBARAKI ALGORITHM :Consider a graph ‘G’. The edge connectivity of the graph is denoted by λ(G). Consider 2 nodes p and q. The edge connectivity of these two nodes is λ(p,q). The edge connectivity is defined as the minimum number of edges that can disconnect the two nodes. G(p,q) is the graph that is obtained by contracting these two nodes. The minimum cut of the graph is calculated asλ(G)=min(λ(p,q)+ λ(G(p,q)))This is Nagamochi Ibaraki algorithm which is implemented recursively.1.3 WORKING OF THE ALGORITHM:The nodes p and q are obtained by Maximum Adjacency ordering. The algorithm is computed as follows:Step 1 : Maximum Adjacency ordering is computed for the graph ‘G’ with ‘n’ nodes. The ordering is done as ( v1……vn). Now the degree of the node vn is d(vn)=λ(vn,vn-1).Step 2: The nodes p and q are vn and vn-1. The graph is contracted and MA ordering is done for the new graph and again degree of the last node in the contracted graph is calculated using MA ordering.Step 3: λ(G) is calculated as minimum of degree of p and degree of the last node in the contracted graph. This is done recursively each time calling MA ordering and contracting the nodesStep 4: This function is repeated until the number of nodes reaches two. Thus the minimum cut is obtained using this algorithm.4Step 5: The λ(Gk) is calculated similar to λ(G) . The only difference is the before calculating the λ(G), we sort the graph based on decreasing degree. With predefined values of “k” (i.e) the number of nodes in the subgraph, we calculate the λ(Gk) for various random graphs say 8 random graphs. Graph is plotted between the λ(Gk) and respective “k” from all the graphs.CHAPTER 2PSEUDO CODEThe pseudo code for the Nagamoch Ibaraki Algorithm :1. Generate random number of nodes ‘n’. It is made as large as possible.2. The edges are also generated randomly and the adjacency matrix is created such that the diagonal elements are made zero(no loops). An unweighted graph is created using the adjacency matrix.3. Maximum Adjacency ordering is computed for the graph. Then minimum cut is calculated by calling the maximum adjacency function.• In this function contraction is done to obtain the MA ordering.• In the Adjacency matrix the node which has the maximum number of edges with the first node is identified and they are combined. An array is created and the combined nodes are put in the array.• Then, the node which has the maxium number of edges with the combined nodes(previous step) is identified, they are combined and that node is put in the array.• This procedure is carried out till we reach the last node. Now the array which contains the list of nodes is the Maximum adjacency ordering.• The nodes which are to be contracted are calculated from the array. The last two elements in the array are the nodes which are to be contracted. • Now the degree of the last element in the array is calculated. This is calculated by adding up the elements in that row.• The nodes which were obtained from MA ordering are now contracted. This is done by adding their rows and coloumns and5deleting the row which corresponds to the last node in the MA dordering. The new graph has n-1 nodes.• Now the minimum cut is obtained as the minimum of the degree of the node calculated and the degree of the node that is to be obtained by contracting the two nodes which is calculated by calling this function again.• Thus, the function is recursively called until the number of nodes reduces to two. Thus the minimum cut is calculated from these computations4. The minimum cut for the graph is displayed5. Number of edges ‘m’in the original graph is calculated by adding up all the elements in the graph and dividing by two(because when there is an edge between 1 and 2, then in the matrix, the element g(1,2) has 1 and g(2,1) also has 1).6. The average degree of the graph is calculated as d=((2*m)/n)7. The number of critical links for a graph is calculated as follows :• Two inner loops are run to traverse the graph. If we find an edge in the graph (i.e a 1 in the matrix) then delete the edge(i.e change the entry to 0. for e.g if g(1,2) had one then change g(1,2) and g(2,1) to 0 and break. • Then calculate the minimum cut for this modified graph.• If this minimum cut happens to be smaller than the minimum cut for the original graph, then this edge is a critical edge.• An outer loop is run from 1 to twice the number of edges to check if each edge is a critical edge. The critical links are added in each iteration based on the condition (minimum cut for the modified graph to be less than the minimum cut of the original graph) to give twice the number of critical links for the graph. Finally it is divided by two to give the number of critical links in the graph.8. A graph is drawn between average degree and connectivity (minimum cut) and another graph is drawn between average degree and number of critical links. These graphs are drawn by taking various samples of these parameters for randomly generated many graphs.6DECENDING DEGREE ORDERING OF RANDOM GRAPHS1. Eight graphs are generated in random with random number of edges and nodes. (Any number of graphs can be generate by modifying the limit).2. Generate random number of nodes 3. Generate edges randomnly.4. Assigning matrix element values to zero when (rows = colums).5. Making sure that if g(,2)= then g(2,) also equal to and making the edges undirected .6. When matrix element value equals , then assign g(j,i)= 1 7. Calculate of
View Full Document
Unlocking...