Karger’s algorithm for Minimum Cut in Python

Karger’s algorithm is a type of ‘random algorithm’ because every time we run it, it gives out a solution that can not be sure to be the best solution.

The Karger’s algorithm for the minimum cut is to cut a graph into two disjoint subgraphs and we do it by eliminating a minimum number of edges in the graph.

It chooses an edge of graph uniformly at random and it may choose from any edge.

The general approach to this algorithm is to run it a lot many times and collect the best solutions. When we will run it for a lot of times, there will be various solutions which may be best or approximately the nearby best so we can doubtfully find a better solution.

Algorithm

We implement the algorithm as follows:

Let Graph G =(V, E)

While V>2 :

  1. We pick edge x from all edge E at random
  2. Now we try to merge x in single vertice
  3. Remove the self-loops we used
  4. Last we return the only cut graph with two final vertices.

Code in Python for Karger’s algorithm for Minimum Cut

The code will run after you create a data.txt file.

We can run the code as many times we want to get different answers and calculate the common answers.

from random import randint
from math import log

class KargerMinCut():

    def __init__(self, graph_file):

        # Load graph file
        self.graph = {}
        self.edges = 0
        self.vertex_count = 0
        with open(graph_file, "r") as file:
            for path in file:
                numbers = [int(x) for x in path.split('\t') if x!='\n']
                vertex = numbers[0]
                vertex_edges = numbers[1:]
                self.graph[vertex] = vertex_edges
                self.edges+=len(vertex_edges)
                self.vertex_count+=1            
        self.supervertices = {}
        for key in self.graph:
            self.supervertices[key] = [key]

    # We  search the minimum cut
    def search_min_cut(self):
        minimumcut = 0
        while len(self.graph)>2:
            # Now we  Pick a random edge
            vertice1, vertice2 = self.select_random_edge()
            self.edges -= len(self.graph[vertice1])
            self.edges -= len(self.graph[vertice2])
            # Then we  merge the edges
            self.graph[vertice1].extend(self.graph[vertice2])
            # Update every references from v2 to point to v1
            for vertex in self.graph[vertice2]:
                self.graph[vertex].remove(vertice2)
                self.graph[vertex].append(vertice1)
            # Remove the  self loop
            self.graph[vertice1] = [x for x in self.graph[vertice1] if x != vertice1]
            # Update total edges of graph
            self.edges += len(self.graph[vertice1])
            self.graph.pop(vertice2)
            #  Update cut grouping in the graph
            self.supervertices[vertice1].extend(self.supervertices.pop(vertice2))
        #  we now Calculate the minimum cut
        for edges in self.graph.values():
            minimumcut = len(edges)
        #  finally return min cut and the two supervertices
        return minimumcut,self.supervertices      

    # select a  random edge:
    def select_random_edge(self):
        rand_edge = randint(0, self.edges-1)
        for vertex, vertex_edges in self.graph.items():
            if len(vertex_edges) < rand_edge:
                rand_edge -= len(vertex_edges)
            else:
                from_vertex = vertex
                to_vertex = vertex_edges[rand_edge-1]
                return from_vertex, to_vertex

    # Now we plot our graph
    def print_graph(self):
        for clue in self.graph:
            print("{} :{}".format(clue, self.graph[clue]))

graph = KargerMinCut('data.txt')

def wholekarger(iterations):
    graph = KargerMinCut('data.txt')
    output = graph.search_min_cut()
    minimumcut = output[0]
    supervertices = output[1]

    for i in range(iterations):
        graph = KargerMinCut('data.txt')
        output = graph.search_min_cut()
        if output[0] < minimumcut:
            minimumcut = output[0]
            supervertices = output[1]
    return minimumcut, supervertices

output = wholekarger(10)
print("minimumcut: {}\nsupervertices: {}".format(output[0],output[1]))
# we have some data for the data.txt 
1	37	79	164	155	32	87	39	103	15	18	78	175	140	200	4	158	97	191	100	91	20	69	198	190	
2	123	134	10	141	13	12	43	47	3	177	101	179	77	182	120	116	36	106	51	154	162	128	30	
3	48	127	134	109	41	17	159	49	136	16	130	141	29	176	2	190	66	153	157	70	114	63	170	104	194	54	
4	91	171	118	125	158	66	107	18	73	140	42	193	127	100	84	121	60	81	99	80	150	55	1	35	23	93	
5	193	156	102	118	175	39	124	119	19	99	160	75	20	112	37	23	145	135	146	73	35	
6	157	56	52	120	131	160	124	119	14	199	144	25	75	76	166	35	87	26	20	32	23	
7	156	185	178	79	27	52	144	107	78	22	71	26	31	15	56	76	112	39	8	113	93	
8	185	155	171	178	108	64	164	53	140	25	100	133	9	52	191	46	20	150	144	39	62	131	42	119	127	31	7	
9	91	155	8	160	107	132	195	26	20	133	39	76	100	78	122	127	38	156	191	196	115	
10	190	184	154	49	2	182	173	170	161	47	189	101	153	50	30	109	177	148	179	16	163	116	13	90	185	
11	123	134	163	41	12	28	130	13	101	83	77	109	114	21	82	88	74	24	94	48	33	
12	161	109	169	21	24	36	65	50	2	101	159	148	54	192	88	47	11	142	43	70	182	177	179	189	194	33	
13	161	141	157	44	83	90	181	41	2	176	10	29	116	134	182	170	165	173	190	159	47	82	111	142	72	154	110	21	103	130	11	33	138	152	
14	91	156	58	122	62	113	107	73	137	25	19	40	6	139	150	46	37	76	39	127	
15	149	58	68	52	39	67	121	191	1	45	100	18	118	174	40	85	196	122	42	193	119	139	26	127	145	135	57	38	7	
16	48	10	36	189	43	3	114	173	111	142	129	88	189	117	128	147	141	194	180	106	167	179	66	74	134	51	59	
17	48	120	134	36	163	3	44	117	167	161	152	95	170	83	180	77	65	72	109	47	43	88	159	197	28	199	184	49	
18	193	149	56	62	15	160	67	191	140	52	178	96	107	132	1	145	89	198	4	26	73	151	126	34	115	
19	156	80	178	164	108	84	71	174	40	62	113	22	89	45	91	126	195	144	5	14	172	
20	185	122	171	56	8	52	73	191	67	126	9	119	1	89	79	107	96	31	75	55	5	6	34	23	
21	188	187	12	173	180	197	138	167	63	111	95	13	192	116	94	114	105	49	177	51	130	90	11	50	66	157	176	
22	156	27	32	131	7	56	53	81	149	23	100	146	115	26	175	121	96	75	57	39	119	71	132	19	150	140	93	
23	91	122	124	22	200	195	145	5	69	125	55	68	156	20	58	191	4	57	149	6	
24	123	134	161	163	169	72	116	167	30	33	77	162	143	159	187	63	184	130	28	50	153	12	148	11	53	
25	193	185	79	108	8	158	87	73	81	115	39	64	178	132	27	68	127	84	14	52	200	97	6	93	
26	193	58	27	108	52	144	160	18	84	81	22	75	139	166	15	107	198	131	7	9	133	6	
27	156	139	144	166	112	100	26	174	31	42	75	158	122	81	22	7	58	73	89	115	39	25	200	69	169	
28	134	188	24	184	159	29	72	114	152	116	169	173	141	17	111	61	192	90	11	177	179	77	33	66	83	136	
29	48	134	188	13	47	88	3	82	92	28	194	50	192	189	123	199	177	147	43	106	148	197	77	103	129	181	
30	165	123	10	24	41	187	47	168	92	148	197	101	50	2	179	111	130	77	153	199	70	
31	27	171	56	131	146	139	191	89	20	108	38	71	75	69	196	149	97	8	86	98	7	
32	156	149	171	62	22	185	35	124	56	38	158	97	53	121	160	1	191	58	89	127	87	120	39	99	84	60	151	174	6	
33	48	161	109	141	24	187	47	88	168	183	110	103	95	116	28	12	11	13	83	134	63	
34	37	122	171	118	76	131	166	137	40	46	97	87	80	164	127	18	62	52	20	139	
35	79	164	125	32	107	137	75	121	85	55	69	45	193	132	4	5	200	135	76	139	198	6	
36	165	188	17	106	88	16	177	110	147	154	159	179	136	41	50	141	66	162	152	168	184	12	43	72	180	190	77	2	170	61	122	
37	193	149	39	121	191	115	146	52	127	79	198	58	125	38	34	1	76	89	164	97	86	178	108	87	84	124	98	174	195	14	5	57	196	186	
38	193	37	86	32	76	107	73	85	127	100	46	89	31	57	96	158	99	160	45	15	9	
39	193	37	122	102	8	158	32	87	85	81	200	60	5	27	155	1	58	150	15	113	76	84	22	25	151	139	100	14	145	9	7	
40	91	156	122	79	118	125	52	175	87	15	81	166	132	121	19	14	160	34	78	71	
41	36	169	184	116	163	106	189	11	104	61	30	123	129	111	3	47	49	154	161	152	13	153	65	92	183	177	162	95	54	70	108	
42	178	79	27	53	171	164	102	52	87	113	15	191	131	91	62	193	8	122	89	56	4	127	145	112	
43	165	161	12	70	199	54	17	190	16	153	141	36	47	44	194	110	82	189	2	148	183	29	130	94	170	51	61	59	
44	188	163	169	17	13	43	114	173	142	154	103	129	181	105	157	148	182	101	110	66	176	49	
45	156	80	149	58	178	53	108	68	56	125	15	93	75	135	174	198	81	166	113	100	19	89	35	97	38	
46	193	58	86	122	155	8	175	160	99	127	67	14	150	144	126	146	34	131	55	38	196	
47	123	10	109	41	17	12	43	116	59	33	13	2	187	165	88	117	29	30	176	147	180	101	130	194	50	94	152	70	
48	180	128	188	197	105	51	94	190	116	29	183	114	153	33	16	49	3	63	184	17	141	168	179	162	11	66	83	193	
49	48	123	10	186	141	41	168	3	148	142	179	21	136	109	44	117	17	103	187	74	
50	165	123	10	188	36	169	24	187	12	65	29	167	47	21	134	130	111	168	77	116	138	106	66	30	
51	165	48	109	141	163	159	92	190	143	2	21	138	43	59	192	117	16	184	104	169	
52	37	178	8	6	15	200	133	80	102	96	40	119	164	166	127	151	20	42	7	26	76	18	73	99	78	25	132	139	191	150	34	
53	156	122	102	193	137	133	42	62	45	64	60	78	160	132	155	56	144	131	196	178	125	8	32	113	22	98	121	198	24	
54	123	187	12	43	168	65	129	130	147	95	41	61	59	141	3	138	114	199	66	110	
55	68	56	125	113	73	78	200	46	131	85	107	89	185	60	84	4	35	99	171	71	20	23	
56	193	122	53	108	45	55	18	125	86	171	79	6	85	133	80	140	96	31	107	20	32	87	120	42	73	84	22	112	196	7	
57	79	155	158	76	84	22	75	121	85	191	100	97	15	37	102	69	38	64	195	145	23	
58	15	146	107	193	140	84	144	86	14	150	26	60	46	166	80	87	139	195	126	45	37	27	102	62	32	175	39	124	23	93	188	
59	186	163	187	47	168	92	143	147	157	54	51	61	199	43	103	63	184	16	188	197	
60	58	86	178	53	171	125	39	144	146	73	124	4	93	32	99	158	132	80	91	96	75	174	55	196	
61	188	116	41	114	183	28	77	54	36	163	187	147	179	65	63	190	43	186	59	189	
62	193	185	79	53	171	102	146	84	198	14	58	137	8	166	175	32	113	18	115	196	42	200	132	121	19	112	133	172	34	
63	48	24	116	183	111	167	21	162	90	181	147	105	106	101	33	123	153	184	128	168	61	59	
64	91	149	122	53	8	120	113	124	119	25	132	131	193	121	144	68	185	108	175	107	57	
65	186	17	12	114	82	3	66	159	167	197	50	101	176	94	54	134	41	165	157	194	180	77	103	74	61	
66	188	36	116	3	65	183	72	180	77	16	136	177	82	159	28	95	48	50	187	21	44	54	176	
67	91	156	102	68	175	131	144	15	18	146	119	20	200	46	112	139	75	80	86	137	
68	122	171	55	78	175	96	75	71	93	118	195	115	67	79	45	158	15	120	155	193	87	146	81	25	64	23	
69	91	108	125	131	81	75	85	174	145	89	27	200	35	156	1	98	86	23	191	127	31	57	
70	165	123	163	153	12	43	168	3	114	82	148	190	129	74	176	47	110	181	41	30	
71	193	79	171	68	124	98	120	73	75	93	151	108	89	155	19	96	22	119	7	125	85	127	40	55	140	31	
72	109	169	24	116	17	114	182	190	141	186	192	28	104	13	66	165	162	36	159	77	110	129	130	181	
73	91	80	27	160	4	20	100	56	193	60	38	18	25	172	76	14	55	52	149	96	78	71	195	127	5	112	97	93	
74	88	104	197	111	130	95	11	138	123	77	159	65	179	94	165	70	141	16	153	136	83	49	
75	91	79	27	171	68	158	87	81	22	119	71	166	57	60	35	160	69	175	26	193	45	127	67	126	89	20	5	31	198	6	
76	37	178	175	120	122	57	52	34	4	156	98	115	133	131	171	149	85	38	174	39	73	99	14	140	35	135	172	9	7	6	
77	24	116	17	72	190	110	36	173	143	94	65	29	61	154	2	161	90	66	159	28	128	117	11	50	138	74	30	
78	156	80	53	164	68	131	144	107	73	195	55	175	1	126	7	149	171	81	91	52	124	40	9	
79	80	37	165	40	75	108	198	25	62	42	7	86	57	102	122	145	175	71	1	35	164	68	118	56	144	200	129	20	112	135	172	163	
80	91	144	100	118	45	78	139	112	149	98	113	87	195	124	85	73	118	19	79	99	58	56	52	146	81	4	60	137	67	126	145	97	34	134	
81	86	27	120	39	131	40	132	25	69	96	26	127	108	75	68	134	98	80	115	149	78	22	4	45	170	
82	161	186	109	153	43	159	114	101	104	70	29	197	192	116	148	65	152	184	13	154	92	110	130	11	145	66	176	
83	17	13	153	88	111	90	117	95	11	33	147	28	109	199	48	74	167	182	154	101	
84	149	58	86	178	171	62	175	113	26	135	96	198	39	19	57	144	37	118	32	56	119	4	98	25	200	150	55	
85	156	80	185	155	102	56	158	39	76	15	69	38	150	175	118	137	71	35	120	57	55	135	
86	58	84	120	81	112	37	60	46	185	193	38	125	118	175	149	99	108	126	133	102	79	56	144	67	69	31	109	
87	80	149	58	118	25	75	126	115	68	178	37	200	32	40	164	56	42	193	107	1	39	113	145	89	172	6	34	93	
88	36	116	12	47	165	168	29	83	159	154	74	148	92	176	180	33	110	194	167	17	114	173	16	11	
89	37	27	102	32	42	18	99	71	151	19	55	75	98	131	69	45	31	38	195	87	20	135	115	
90	163	116	13	173	28	110	190	77	129	117	130	10	179	92	134	194	21	63	83	157	94	152	199	
91	126	14	75	135	107	80	102	67	160	158	144	23	64	155	4	198	40	9	73	69	193	185	149	164	42	78	60	98	19	1	165	
92	161	109	163	187	88	186	141	51	117	197	59	173	192	82	29	143	116	41	30	111	148	129	90	194	152	170	
93	68	99	71	60	45	150	145	98	25	87	122	178	185	7	144	4	22	73	58	112	
94	48	163	65	173	182	154	77	21	117	11	147	74	189	43	114	47	177	192	104	90	
95	123	141	169	17	168	114	179	21	33	165	167	177	41	103	83	199	129	182	188	74	66	157	152	54	176	
96	171	164	68	56	52	18	73	84	81	124	22	71	60	126	150	20	97	38	149	158	196	115	
97	185	149	37	178	122	108	118	32	131	1	31	140	73	34	45	25	80	133	57	96	
98	80	171	164	158	120	76	99	81	71	37	91	151	144	172	140	150	160	121	84	53	139	89	69	31	133	93	
99	80	86	178	122	118	125	52	193	32	174	46	113	98	93	89	150	102	76	100	124	4	60	55	5	38	196	
100	80	185	149	27	8	113	131	15	73	99

Here in the data file  1 is the whole one graph  than file 2 is whole one graph upto 100 graph. Serial wise.

You may also create your own data.

Output

minimumcut:{2} 
Supervertices:{80, 113}
minimumcut:{3}
Supervertices:{112, 76}

 

If you have any doubt you may ask and try to run code With iteration: 100. Your feedback will be appreciated.

 

Leave a Reply

Your email address will not be published. Required fields are marked *