{"id":26593,"date":"2017-12-21T20:11:52","date_gmt":"2017-12-21T14:41:52","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=26593"},"modified":"2017-12-21T20:11:52","modified_gmt":"2017-12-21T14:41:52","slug":"c-programming-kargers-algorithm-minimum-cut-introduction-implementation","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/c-programming-kargers-algorithm-minimum-cut-introduction-implementation\/","title":{"rendered":"C++ Programming – Karger\u2019s algorithm for Minimum Cut Introduction and Implementation"},"content":{"rendered":"

Given an undirected and unweighted graph, find the smallest cut (smallest number of edges that disconnects the graph into two components).<\/span>
\nThe input graph may have parallel edges.<\/p>\n

For example consider the following example, the smallest cut has 2 edges.<\/p>\n

\"first\"<\/p>\n

A Simple Solution use Max-Flow based s-t cut algorithm to find minimum cut. Consider every pair of vertices as source \u2018s\u2019 and sink \u2018t\u2019, and call minimum s-t cut algorithm to find the s-t cut. Return minimum of all s-t cuts. Best possible time complexity of this algorithm is O(V5) for a graph. [How? there are total possible V2 pairs and s-t cut algorithm for one pair takes O(V*E) time and E = O(V2)].<\/p>\n[ad type=\u201dbanner\u201d]\n

Below is simple Karger\u2019s Algorithm for this purpose. Below Karger\u2019s algorithm can be implemented in O(E) = O(V2) time.<\/p>\n

1) Initialize contracted graph CG as copy of original graph
\n2) While there are more than 2 vertices.
\na) Pick a random edge (u, v) in the contracted graph.
\nb) Merge (or contract) u and v into a single vertex (update
\nthe contracted graph).
\nc) Remove self-loops
\n3) Return cut represented by two vertices.
\nLet us understand above algorithm through the example given.<\/p>\n

Let the first randomly picked vertex be \u2018a\u2018 which connects vertices 0 and 1. We remove this edge and contract the graph (combine vertices 0 and 1). We get the following graph.<\/p>\n

\"\"<\/p>\n

Let the next randomly picked edge be \u2018d\u2019. We remove this edge and combine vertices (0,1) and 3.<\/p>\n

\"three\"<\/p>\n

We need to remove self-loops in the graph. So we remove edge \u2018c\u2019<\/p>\n

\"\"<\/p>\n

Now graph has two vertices, so we stop. The number of edges in the resultant graph is the cut produced by Karger\u2019s algorithm.<\/p>\n

Karger\u2019s algorithm is a Monte Carlo algorithm and cut produced by it may not be minimum.<\/p>\n

For example, the following diagram shows that a different order of picking random edges produces a min-cut of size 3.<\/p>\n

\"four\"<\/p>\n

Below is C++ implementation of above algorithm. The input graph is represented as a collection of edges and union-find data structure is used to keep track of components.<\/p>\n[pastacode lang=\u201dcpp\u201d manual=\u201d%2F%2F%20Karger\u2019s%20algorithm%20to%20find%20Minimum%20Cut%20in%20an%0A%2F%2F%20undirected%2C%20unweighted%20and%20connected%20graph.%0A%23include%20%3Cstdio.h%3E%0A%23include%20%3Cstdlib.h%3E%0A%23include%20%3Ctime.h%3E%0A%20%0A%2F%2F%20a%20structure%20to%20represent%20a%20unweighted%20edge%20in%20graph%0Astruct%20Edge%0A%7B%0A%20%20%20%20int%20src%2C%20dest%3B%0A%7D%3B%0A%20%0A%2F%2F%20a%20structure%20to%20represent%20a%20connected%2C%20undirected%0A%2F%2F%20and%20unweighted%20graph%20as%20a%20collection%20of%20edges.%0Astruct%20Graph%0A%7B%0A%20%20%20%20%2F%2F%20V-%3E%20Number%20of%20vertices%2C%20E-%3E%20Number%20of%20edges%0A%20%20%20%20int%20V%2C%20E%3B%0A%20%0A%20%20%20%20%2F%2F%20graph%20is%20represented%20as%20an%20array%20of%20edges.%0A%20%20%20%20%2F%2F%20Since%20the%20graph%20is%20undirected%2C%20the%20edge%0A%20%20%20%20%2F%2F%20from%20src%20to%20dest%20is%20also%20edge%20from%20dest%0A%20%20%20%20%2F%2F%20to%20src.%20Both%20are%20counted%20as%201%20edge%20here.%0A%20%20%20%20Edge*%20edge%3B%0A%7D%3B%0A%20%0A%2F%2F%20A%20structure%20to%20represent%20a%20subset%20for%20union-find%0Astruct%20subset%0A%7B%0A%20%20%20%20int%20parent%3B%0A%20%20%20%20int%20rank%3B%0A%7D%3B%0A%20%0A%2F%2F%20Function%20prototypes%20for%20union-find%20(These%20functions%20are%20defined%0A%2F%2F%20after%20kargerMinCut()%20)%0Aint%20find(struct%20subset%20subsets%5B%5D%2C%20int%20i)%3B%0Avoid%20Union(struct%20subset%20subsets%5B%5D%2C%20int%20x%2C%20int%20y)%3B%0A%20%0A%2F%2F%20A%20very%20basic%20implementation%20of%20Karger\u2019s%20randomized%0A%2F%2F%20algorithm%20for%20finding%20the%20minimum%20cut.%20Please%20note%0A%2F%2F%20that%20Karger\u2019s%20algorithm%20is%20a%20Monte%20Carlo%20Randomized%20algo%0A%2F%2F%20and%20the%20cut%20returned%20by%20the%20algorithm%20may%20not%20be%0A%2F%2F%20minimum%20always%0Aint%20kargerMinCut(struct%20Graph*%20graph)%0A%7B%0A%20%20%20%20%2F%2F%20Get%20data%20of%20given%20graph%0A%20%20%20%20int%20V%20%3D%20graph-%3EV%2C%20E%20%3D%20graph-%3EE%3B%0A%20%20%20%20Edge%20*edge%20%3D%20graph-%3Eedge%3B%0A%20%0A%20%20%20%20%2F%2F%20Allocate%20memory%20for%20creating%20V%20subsets.%0A%20%20%20%20struct%20subset%20*subsets%20%3D%20new%20subset%5BV%5D%3B%0A%20%0A%20%20%20%20%2F%2F%20Create%20V%20subsets%20with%20single%20elements%0A%20%20%20%20for%20(int%20v%20%3D%200%3B%20v%20%3C%20V%3B%20%2B%2Bv)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20subsets%5Bv%5D.parent%20%3D%20v%3B%0A%20%20%20%20%20%20%20%20subsets%5Bv%5D.rank%20%3D%200%3B%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20%2F%2F%20Initially%20there%20are%20V%20vertices%20in%0A%20%20%20%20%2F%2F%20contracted%20graph%0A%20%20%20%20int%20vertices%20%3D%20V%3B%0A%20%0A%20%20%20%20%2F%2F%20Keep%20contracting%20vertices%20until%20there%20are%0A%20%20%20%20%2F%2F%202%20vertices.%0A%20%20%20%20while%20(vertices%20%3E%202)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%2F%2F%20Pick%20a%20random%20edge%0A%20%20%20%20%20%20%20int%20i%20%3D%20rand()%20%25%20E%3B%0A%20%0A%20%20%20%20%20%20%20%2F%2F%20Find%20vertices%20(or%20sets)%20of%20two%20corners%0A%20%20%20%20%20%20%20%2F%2F%20of%20current%20edge%0A%20%20%20%20%20%20%20int%20subset1%20%3D%20find(subsets%2C%20edge%5Bi%5D.src)%3B%0A%20%20%20%20%20%20%20int%20subset2%20%3D%20find(subsets%2C%20edge%5Bi%5D.dest)%3B%0A%20%0A%20%20%20%20%20%20%20%2F%2F%20If%20two%20corners%20belong%20to%20same%20subset%2C%0A%20%20%20%20%20%20%20%2F%2F%20then%20no%20point%20considering%20this%20edge%0A%20%20%20%20%20%20%20if%20(subset1%20%3D%3D%20subset2)%0A%20%20%20%20%20%20%20%20%20continue%3B%0A%20%0A%20%20%20%20%20%20%20%2F%2F%20Else%20contract%20the%20edge%20(or%20combine%20the%0A%20%20%20%20%20%20%20%2F%2F%20corners%20of%20edge%20into%20one%20vertex)%0A%20%20%20%20%20%20%20else%0A%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20printf(%22Contracting%20edge%20%25d-%25d%5Cn%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20edge%5Bi%5D.src%2C%20edge%5Bi%5D.dest)%3B%0A%20%20%20%20%20%20%20%20%20%20vertices\u2013%3B%0A%20%20%20%20%20%20%20%20%20%20Union(subsets%2C%20subset1%2C%20subset2)%3B%0A%20%20%20%20%20%20%20%7D%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20%2F%2F%20Now%20we%20have%20two%20vertices%20(or%20subsets)%20left%20in%0A%20%20%20%20%2F%2F%20the%20contracted%20graph%2C%20so%20count%20the%20edges%20between%0A%20%20%20%20%2F%2F%20two%20components%20and%20return%20the%20count.%0A%20%20%20%20int%20cutedges%20%3D%200%3B%0A%20%20%20%20for%20(int%20i%3D0%3B%20i%3CE%3B%20i%2B%2B)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20int%20subset1%20%3D%20find(subsets%2C%20edge%5Bi%5D.src)%3B%0A%20%20%20%20%20%20%20%20int%20subset2%20%3D%20find(subsets%2C%20edge%5Bi%5D.dest)%3B%0A%20%20%20%20%20%20%20%20if%20(subset1%20!%3D%20subset2)%0A%20%20%20%20%20%20%20%20%20%20cutedges%2B%2B%3B%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20return%20cutedges%3B%0A%7D%0A%20%0A%2F%2F%20A%20utility%20function%20to%20find%20set%20of%20an%20element%20i%0A%2F%2F%20(uses%20path%20compression%20technique)%0Aint%20find(struct%20subset%20subsets%5B%5D%2C%20int%20i)%0A%7B%0A%20%20%20%20%2F%2F%20find%20root%20and%20make%20root%20as%20parent%20of%20i%0A%20%20%20%20%2F%2F%20(path%20compression)%0A%20%20%20%20if%20(subsets%5Bi%5D.parent%20!%3D%20i)%0A%20%20%20%20%20%20subsets%5Bi%5D.parent%20%3D%0A%20%20%20%20%20%20%20%20%20%20%20%20%20find(subsets%2C%20subsets%5Bi%5D.parent)%3B%0A%20%0A%20%20%20%20return%20subsets%5Bi%5D.parent%3B%0A%7D%0A%20%0A%2F%2F%20A%20function%20that%20does%20union%20of%20two%20sets%20of%20x%20and%20y%0A%2F%2F%20(uses%20union%20by%20rank)%0Avoid%20Union(struct%20subset%20subsets%5B%5D%2C%20int%20x%2C%20int%20y)%0A%7B%0A%20%20%20%20int%20xroot%20%3D%20find(subsets%2C%20x)%3B%0A%20%20%20%20int%20yroot%20%3D%20find(subsets%2C%20y)%3B%0A%20%0A%20%20%20%20%2F%2F%20Attach%20smaller%20rank%20tree%20under%20root%20of%20high%0A%20%20%20%20%2F%2F%20rank%20tree%20(Union%20by%20Rank)%0A%20%20%20%20if%20(subsets%5Bxroot%5D.rank%20%3C%20subsets%5Byroot%5D.rank)%0A%20%20%20%20%20%20%20%20subsets%5Bxroot%5D.parent%20%3D%20yroot%3B%0A%20%20%20%20else%20if%20(subsets%5Bxroot%5D.rank%20%3E%20subsets%5Byroot%5D.rank)%0A%20%20%20%20%20%20%20%20subsets%5Byroot%5D.parent%20%3D%20xroot%3B%0A%20%0A%20%20%20%20%2F%2F%20If%20ranks%20are%20same%2C%20then%20make%20one%20as%20root%20and%0A%20%20%20%20%2F%2F%20increment%20its%20rank%20by%20one%0A%20%20%20%20else%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20subsets%5Byroot%5D.parent%20%3D%20xroot%3B%0A%20%20%20%20%20%20%20%20subsets%5Bxroot%5D.rank%2B%2B%3B%0A%20%20%20%20%7D%0A%7D%0A%20%0A%2F%2F%20Creates%20a%20graph%20with%20V%20vertices%20and%20E%20edges%0Astruct%20Graph*%20createGraph(int%20V%2C%20int%20E)%0A%7B%0A%20%20%20%20Graph*%20graph%20%3D%20new%20Graph%3B%0A%20%20%20%20graph-%3EV%20%3D%20V%3B%0A%20%20%20%20graph-%3EE%20%3D%20E%3B%0A%20%20%20%20graph-%3Eedge%20%3D%20new%20Edge%5BE%5D%3B%0A%20%20%20%20return%20graph%3B%0A%7D%0A%20%0A%2F%2F%20Driver%20program%20to%20test%20above%20functions%0Aint%20main()%0A%7B%0A%20%20%20%20%2F*%20Let%20us%20create%20following%20unweighted%20graph%0A%20%20%20%20%20%20%20%200\u2014\u20141%0A%20%20%20%20%20%20%20%20%7C%20%5C%20%20%20%20%7C%0A%20%20%20%20%20%20%20%20%7C%20%20%20%5C%20%20%7C%0A%20%20%20%20%20%20%20%20%7C%20%20%20%20%20%5C%7C%0A%20%20%20%20%20%20%20%202\u2014\u20143%20%20%20*%2F%0A%20%20%20%20int%20V%20%3D%204%3B%20%20%2F%2F%20Number%20of%20vertices%20in%20graph%0A%20%20%20%20int%20E%20%3D%205%3B%20%20%2F%2F%20Number%20of%20edges%20in%20graph%0A%20%20%20%20struct%20Graph*%20graph%20%3D%20createGraph(V%2C%20E)%3B%0A%20%0A%20%20%20%20%2F%2F%20add%20edge%200-1%0A%20%20%20%20graph-%3Eedge%5B0%5D.src%20%3D%200%3B%0A%20%20%20%20graph-%3Eedge%5B0%5D.dest%20%3D%201%3B%0A%20%0A%20%20%20%20%2F%2F%20add%20edge%200-2%0A%20%20%20%20graph-%3Eedge%5B1%5D.src%20%3D%200%3B%0A%20%20%20%20graph-%3Eedge%5B1%5D.dest%20%3D%202%3B%0A%20%0A%20%20%20%20%2F%2F%20add%20edge%200-3%0A%20%20%20%20graph-%3Eedge%5B2%5D.src%20%3D%200%3B%0A%20%20%20%20graph-%3Eedge%5B2%5D.dest%20%3D%203%3B%0A%20%0A%20%20%20%20%2F%2F%20add%20edge%201-3%0A%20%20%20%20graph-%3Eedge%5B3%5D.src%20%3D%201%3B%0A%20%20%20%20graph-%3Eedge%5B3%5D.dest%20%3D%203%3B%0A%20%0A%20%20%20%20%2F%2F%20add%20edge%202-3%0A%20%20%20%20graph-%3Eedge%5B4%5D.src%20%3D%202%3B%0A%20%20%20%20graph-%3Eedge%5B4%5D.dest%20%3D%203%3B%0A%20%0A%20%20%20%20%2F%2F%20Use%20a%20different%20seed%20value%20for%20every%20run.%0A%20%20%20%20srand(time(NULL))%3B%0A%20%0A%20%20%20%20printf(%22%5CnCut%20found%20by%20Karger\u2019s%20randomized%20algo%20is%20%25d%5Cn%22%2C%0A%20%20%20%20%20%20%20%20%20%20%20kargerMinCut(graph))%3B%0A%20%0A%20%20%20%20return%200%3B%0A%7D\u201d message=\u201dC++ Program\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n

Output:<\/strong><\/p>\n

Contracting edge 0-2\r\nContracting edge 0-3\r\n\r\nCut found by Karger's randomized algo is 2<\/pre>\n
\u00a0<\/p>\n
Note that the above program is based on outcome of a random function and may produce different output.<\/strong><\/em><\/p>\n
In this post, we have discussed simple Karger\u2019s algorithm and have seen that the algorithm doesn\u2019t always produce min-cut. The above algorithm produces min-cut with probability greater or equal to that 1\/(n2<\/sup>).<\/p>\n[ad type=\u201dbanner\u201d]\n","protected":false},"excerpt":{"rendered":"
A Simple Solution use Max-Flow based s-t cut algorithm to find minimum cut. Consider every pair of vertices as source \u2018s\u2019 and sink \u2018t\u2019.<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[69969,83515,1,73906],"tags":[79250,79244,79246,79247,79249,79241,79243,79240,79248,79242,79245],"class_list":["post-26593","post","type-post","status-publish","format-standard","hentry","category-algorithm","category-c-programming-3","category-coding","category-graph-algorithms","tag-c-programming-kargers-algorithm-for-minimum-cut","tag-david-karger","tag-david-karger-mit","tag-david-r-karger","tag-ef-karger","tag-karger","tag-karger-algorithm","tag-karger-journals","tag-karger-password","tag-kargers-algorithm","tag-s-karger"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/26593","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/comments?post=26593"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/26593\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=26593"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=26593"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=26593"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}