PROJECT #2 NAGAMOCHI-IBARAKI ALGORITHM CS 6385 ALGORITHMIC ASPECTS/TELECOM NTWK Submitted by Anusha Doppalapudi 20211324261 | P a g e2 | P a g e Overview Nagamochi-Ibaraki algorithm is a simple deterministic algorithm discovered by Nagamochi and Ibaraki for finding minimum cut of a graph G. To describe the principle of the algorithm, let us denote the edge connectivity of a graph G by λ(G). If x, y are two different nodes, let λ(x, y) denote the edge-connectivity between them, that is, the minimum number of edges that can disconnect x and y from each other (this may be larger than λ(G)). Finally, let Gxy be the graph obtained from G by contracting (merging) nodes x, y. In this operation we omit the possibly arising loop (if x, y were connected in G), but keep the parallel edges. We can now use the following result that is not hard to prove: For any two nodes x, y λ(G) = min{ λ(x, y), λ(Gxy)} (1) Thus, if we can find two nodes x, y for which λ(x, y) can be computed easily (without a flow computation), then the above formula yields a simple recursive algorithm. One can indeed easily find such a pair x, y of nodes. This is done via the so-called Maximum Adjacency (MA) ordering. An MA ordering v1, . . . , vn of the nodes is generated recursively the by the following algorithm: - Take any of the nodes for v1. - Once v1, . . . , vi is already chosen, take a node for vi+1 that has the maximum number of edges connecting it with the set {v1, . . . , vi}. Nagamochi and Ibaraki proved that this ordering has the following nice property: Theorem: In any MA ordering v1, . . ., vn of the nodes λ(vn-1, vn) = d(vn) Holds, where d(.) denotes the degree of the node. Therefore, it is enough to create an MA ordering, as described above, and take the last 2 nodes in this ordering for x, y. Then the connectivity between them will be equal to the degree of the last node in the MA ordering. Then one can apply formula (1) recursively to get the minimum cut. Here we make use of the fact that it reduces the problem to computing λ(Gxy) and Gxy is already a smaller graph.3 | P a g e Implementation The program is written in C++ language and tested using Microsoft Visual Studio 2012 on Windows 7 system. The following functions are used in the program including main(). - Create_graph() - Find_MA_order() - Find_min_cut() - Find_critical_edges() 1. Main(): This function takes the number of nodes as 26 and finds the minimum cut of the graph taking edges in the range from 0 to maximum possible for the given number of nodes and in increments of 5%. It calls create_graph(), find_min_cut() and find_critical_edges(). 2. Create_graph(): This function takes the number of nodes and edges and creates a random graph using inbuilt function rand(). This graph is stored as a 2-dimensional array in a global variable graph[][]. It also creates a copy of the same graph and stores it in another global variable graph_copy[][]. This graph copy is used to find critical edges by the find_critical_edge() function. 3. Find_min_cut(): This function takes total number of nodes in the original graph and nodes remaining (after the graph is merged at each step) as its argument. It works on the global variable graph[][] and returns the minimum cut of the graph. It calls the find_MA_order() function to get the MA ordering and computes the minimum cut between the last two nodes in the ordering. If the graph is disconnected, find_MA_order() will return -1. The minimum cut between the last two nodes is the degree of the last node in the MA ordering. It then merges these two nodes and compares the minimum cut just found with the minimum cut of the merged graph. If only two nodes are remaining it returns the minimum cut of the last two nodes. 4. Find_MA_order(): This function takes the number of nodes in the original graph and the nodes remaining (after the graph is merged at each step) as its argument. It finds the MA ordering of the graph using graph[][] and stores the MA list in a global variable MA_order[]. This list is used by find_min_cut(). It returns -1 if the given graph is disconnected. This function selects a random node as the start node and store it in the MA_order[] list. It then finds the node which has the maximum edges connecting to the set of nodes in the MA_order[] list. This node is added to the MA_order[] list and then the above step is repeated until nodesleft is 0. If before the nodesleft count becomes 0, no new neighbors are found, it means the graph is disconnected.4 | P a g e 5. Find_critical_edges(): This function takes the edge-connectivity, the number of nodes in the original graph and the number of edges as its argument and returns the number of critical edges in the graph. It starts with the first edge in the graph[][] and checks if the edge is not already tested. If not, the edge is removed and the minimum cut of the graph is found. If this minimum cut is smaller than the original graph’s minimum cut, this edge is critical and the critical edge count is incremented by 1. This edge is marked as done and the above step is repeated until all the edges in the graph are traversed. The program was tested for graph having 25 nodes.5 | P a g e Pseudo code Main() 1. The number of nodes are taken as 26 as per the problem statement. 2. Calculate the maximum edges possible for the given number of nodes. 3. Starting from 0 to the maximum edges possible run the following loop 20 times in increments of 5%. - Print the number of edges. - Call create_graph() to create a random graph. - Call find_min_cut() to find the minimum cut of the graph. - Call find_critical_edges() to find the number of critical edges in the graph. 4. Print the result in a formatted way. Create_graph() 1. Initialize the global graph and graph_copy variables to -1. 2. Run this loop for the total number of edges in the graph. - Find a random row and column number for the array. - Check if the row and column numbers are not same and whether the edge is not added already. - Add the edge to the graph and graph_copy. Find_min_cut() 1. Call the find_MA_order(). 2. If it returns -1 then return 0 else 3. Find degree of the last node in MA ordering list created by
View Full Document
Unlocking...