{"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=”banner”]\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

C++ Program<\/span> <\/div> 
\/\/ Karger's algorithm to find Minimum Cut in an\/\/ undirected, unweighted and connected graph.#include <stdio.h>#include <stdlib.h>#include <time.h> \/\/ a structure to represent a unweighted edge in graphstruct Edge{    int src, dest;}; \/\/ a structure to represent a connected, undirected\/\/ and unweighted graph as a collection of edges.struct Graph{    \/\/ V-> Number of vertices, E-> Number of edges    int V, E;     \/\/ graph is represented as an array of edges.    \/\/ Since the graph is undirected, the edge    \/\/ from src to dest is also edge from dest    \/\/ to src. Both are counted as 1 edge here.    Edge* edge;}; \/\/ A structure to represent a subset for union-findstruct subset{    int parent;    int rank;}; \/\/ Function prototypes for union-find (These functions are defined\/\/ after kargerMinCut() )int find(struct subset subsets[], int i);void Union(struct subset subsets[], int x, int y); \/\/ A very basic implementation of Karger's randomized\/\/ algorithm for finding the minimum cut. Please note\/\/ that Karger's algorithm is a Monte Carlo Randomized algo\/\/ and the cut returned by the algorithm may not be\/\/ minimum alwaysint kargerMinCut(struct Graph* graph){    \/\/ Get data of given graph    int V = graph->V, E = graph->E;    Edge *edge = graph->edge;     \/\/ Allocate memory for creating V subsets.    struct subset *subsets = new subset[V];     \/\/ Create V subsets with single elements    for (int v = 0; v < V; ++v)    {        subsets[v].parent = v;        subsets[v].rank = 0;    }     \/\/ Initially there are V vertices in    \/\/ contracted graph    int vertices = V;     \/\/ Keep contracting vertices until there are    \/\/ 2 vertices.    while (vertices > 2)    {       \/\/ Pick a random edge       int i = rand() % E;        \/\/ Find vertices (or sets) of two corners       \/\/ of current edge       int subset1 = find(subsets, edge[i].src);       int subset2 = find(subsets, edge[i].dest);        \/\/ If two corners belong to same subset,       \/\/ then no point considering this edge       if (subset1 == subset2)         continue;        \/\/ Else contract the edge (or combine the       \/\/ corners of edge into one vertex)       else       {          printf("Contracting edge %d-%d\\n",                 edge[i].src, edge[i].dest);          vertices--;          Union(subsets, subset1, subset2);       }    }     \/\/ Now we have two vertices (or subsets) left in    \/\/ the contracted graph, so count the edges between    \/\/ two components and return the count.    int cutedges = 0;    for (int i=0; i<E; i++)    {        int subset1 = find(subsets, edge[i].src);        int subset2 = find(subsets, edge[i].dest);        if (subset1 != subset2)          cutedges++;    }     return cutedges;} \/\/ A utility function to find set of an element i\/\/ (uses path compression technique)int find(struct subset subsets[], int i){    \/\/ find root and make root as parent of i    \/\/ (path compression)    if (subsets[i].parent != i)      subsets[i].parent =             find(subsets, subsets[i].parent);     return subsets[i].parent;} \/\/ A function that does union of two sets of x and y\/\/ (uses union by rank)void Union(struct subset subsets[], int x, int y){    int xroot = find(subsets, x);    int yroot = find(subsets, y);     \/\/ Attach smaller rank tree under root of high    \/\/ rank tree (Union by Rank)    if (subsets[xroot].rank < subsets[yroot].rank)        subsets[xroot].parent = yroot;    else if (subsets[xroot].rank > subsets[yroot].rank)        subsets[yroot].parent = xroot;     \/\/ If ranks are same, then make one as root and    \/\/ increment its rank by one    else    {        subsets[yroot].parent = xroot;        subsets[xroot].rank++;    }} \/\/ Creates a graph with V vertices and E edgesstruct Graph* createGraph(int V, int E){    Graph* graph = new Graph;    graph->V = V;    graph->E = E;    graph->edge = new Edge[E];    return graph;} \/\/ Driver program to test above functionsint main(){    \/* Let us create following unweighted graph        0------1        | \\    |        |   \\  |        |     \\|        2------3   *\/    int V = 4;  \/\/ Number of vertices in graph    int E = 5;  \/\/ Number of edges in graph    struct Graph* graph = createGraph(V, E);     \/\/ add edge 0-1    graph->edge[0].src = 0;    graph->edge[0].dest = 1;     \/\/ add edge 0-2    graph->edge[1].src = 0;    graph->edge[1].dest = 2;     \/\/ add edge 0-3    graph->edge[2].src = 0;    graph->edge[2].dest = 3;     \/\/ add edge 1-3    graph->edge[3].src = 1;    graph->edge[3].dest = 3;     \/\/ add edge 2-3    graph->edge[4].src = 2;    graph->edge[4].dest = 3;     \/\/ Use a different seed value for every run.    srand(time(NULL));     printf("\\nCut found by Karger's randomized algo is %d\\n",           kargerMinCut(graph));     return 0;}<\/code><\/pre> <\/div>\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
 <\/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=”banner”]\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}]}}