[ACCEPTED]-karger min cut algorithm in python 2.7-min

Accepted answer
Score: 11

This code also works.

import random, copy
data = open("***.txt","r")
G = {}
for line in data:
    lst = [int(s) for s in line.split()]
    G[lst[0]] = lst[1:]   

def choose_random_key(G):
    v1 = random.choice(list(G.keys()))
    v2 = random.choice(list(G[v1]))
    return v1, v2

def karger(G):
    length = []
    while len(G) > 2:
        v1, v2 = choose_random_key(G)
        for x in G[v2]:
        while v1 in G[v1]:
        del G[v2]
    for key in G.keys():
    return length[0]

def operation(n):
    i = 0
    count = 10000   
    while i < n:
        data = copy.deepcopy(G)
        min_cut = karger(data)
        if min_cut < count:
            count = min_cut
        i = i + 1
    return count



Score: 9

So Karger's algorithm is a `random alogorithm'. That 12 is, each time you run it it produces a solution 11 which is in no way guaranteed to be best. The 10 general approach is to run it lots of times 9 and keep the best solution. For lots of 8 configurations there will be many solutions 7 which are best or approximately best, so 6 you heuristically find a good solution quickly.

As 5 far as I can see, you are only running the 4 algorithms once. Thus the solution is unlikely 3 to be the optimal one. Try running it 100 2 times in for loop and holding onto the best 1 solution.

Score: 2

As stated by Phil, I had to run my program 9 100 times. And one more correction in the 8 code was :

for edge in edgelist:
        if edge[0] == edge[1]:

This part of the code did not 7 correctly eliminate the self loops. So I 6 had to change the code like :

for i in range((len(edgelist)-1),-1,-1):
        if edgelist[i][0] == edgelist[i][1]:

And this line 5 was not needed. since the target node would 4 be automatically changed to self loop and 3 it would be removed.


Then as said earlier, the 2 program was looped for 100 times, and I 1 got the minimum cut by randomization. :)

Score: 2

While looking at this post's answers, I 5 came across Joel's comment. According to 4 Karger's algorithm, the edge must be chosen 3 uniformly at random. You can find my implementation 2 which is based on Oscar's answer and Joel's 1 comment below:

class KargerMinCutter:
def __init__(self, graph_file):
    self._graph = {}
    self._total_edges = 0
    with open(graph_file) as file:
        for index, line in enumerate(file):
            numbers = [int(number) for number in line.split()]
            self._graph[numbers[0]] = numbers[1:]
            self._total_edges += len(numbers[1:])

def find_min_cut(self):
    min_cut = 0
    while len(self._graph) > 2:
        v1, v2 = self._pick_random_edge()
        self._total_edges -= len(self._graph[v1])
        self._total_edges -= len(self._graph[v2])
        for vertex in self._graph[v2]:
        self._graph[v1] = list(filter(lambda v: v != v1, self._graph[v1]))
        self._total_edges += len(self._graph[v1])
    for edges in self._graph.values():
        min_cut = len(edges)
    return min_cut

def _pick_random_edge(self):
    rand_edge = randint(0, self._total_edges - 1)
    for vertex, vertex_edges in self._graph.items():
        if len(vertex_edges) <= rand_edge:
            rand_edge -= len(vertex_edges)
            from_vertex = vertex
            to_vertex = vertex_edges[rand_edge]
            return from_vertex, to_vertex
Score: 1

Note, my response is in Python3 as it has 9 been a few years since this post last received 8 a response.

Further iterating upon @sestus' helpful 7 answer above, I wanted to address three 6 features:

  1. Within the _pick_random_edge method of the class KarmgerMinCut(), rand_edge will ultimately match the length of vertex_edges. I adjusted the code to subtract 1 from rand_edge so rand_edge does not attempt to grab an element at a location 1 greater than the array length.
  2. Understand which vertices comprise the two subgroupings representing the minimum cut. The functions implemented upon the "supervertices" dict achieve this.
  3. Run this algorithm a large number 5 of times (in my case, 100 times) and keep 4 track of the smallest min_cut and its related 3 supervertices. That's what my outside function 2 full_karger() achieves. I am not clever 1 enough to implement this as an internal

    from random import randint
    from math import log
    class KargerMinCut():
        # 0: Initialize graph
        def __init__(self, graph_file):
            # 0.1: Load graph file
            self.graph = {}
            self.total_edges = 0
            self.vertex_count = 0
            with open(graph_file, "r") as file:
                for line in file:
                    numbers = [int(x) for x in line.split('\t') if x!='\n']
                    vertex = numbers[0]
                    vertex_edges = numbers[1:]
                    self.graph[vertex] = vertex_edges
            self.supervertices = {}
            for key in self.graph:
                self.supervertices[key] = [key]
        # 1: Find the minimum cut
        def find_min_cut(self):
            min_cut = 0
            while len(self.graph)>2:
                # 1.1: Pick a random edge
                v1, v2 = self.pick_random_edge()
                self.total_edges -= len(self.graph[v1])
                self.total_edges -= len(self.graph[v2])
                # 1.2: Merge the edges
                # 1.3: Update all references to v2 to point to v1
                for vertex in self.graph[v2]:
                # 1.4: Remove self loops
                self.graph[v1] = [x for x in self.graph[v1] if x != v1]
                # 1.5: Update total edges
                self.total_edges += len(self.graph[v1])
                # 1.6: Update cut groupings
            # 1.7: Calc min cut
            for edges in self.graph.values():
                min_cut = len(edges)
            # 1.8: Return min cut and the two supervertices
            return min_cut, self.supervertices      
        # 2: Pick a truly random edge:
        def pick_random_edge(self):
            rand_edge = randint(0, self.total_edges-1)
            for vertex, vertex_edges in self.graph.items():
                if len(vertex_edges) < rand_edge:
                    rand_edge -= len(vertex_edges)
                    from_vertex = vertex
                    to_vertex = vertex_edges[rand_edge-1]
                    return from_vertex, to_vertex
        # H.1: Helpful young man who prints our graph
        def print_graph(self):
            for key in self.graph:
                print("{}: {}".format(key, self.graph[key]))
    graph = KargerMinCut('kargerMinCut.txt')
    def full_karger(iterations):
        graph = KargerMinCut('kargerMinCut.txt')
        out = graph.find_min_cut()
        min_cut = out[0]
        supervertices = out[1]
        for i in range(iterations):
            graph = KargerMinCut('kargerMinCut.txt')
            out = graph.find_min_cut()
            if out[0] < min_cut:
                min_cut = out[0]
                supervertices = out[1]
        return min_cut, supervertices
    out = full_karger(100)
    print("min_cut: {}\nsupervertices: {}".format(out[0],out[1]))
Score: 0

I totally agree with the above answers. But 8 when I run your code with Python 3.x, it 7 turns out to produce Code 1. This code sometimes 6 works, but sometimes fails. In fact, as 5 @user_3317704 mentioned above, there is 4 a mistake in your code:

for edge in edgelist:
    if edge[0] == edge[1]:

You should not change 3 the items of the list when you do a for-do. It 2 raises mistakes. For your reference, it 1 could be

newEdgeList = edgeList.copy();
for edge in edgeList:
    if edge[0] == edge[1]:
edgeList = newEdgeList;

More Related questions