7
\$\begingroup\$

I implemented Karger's algorithm with the function find_min_cut and it works, but I don't feel satisfied with the code I wrote.

from numpy import inf
from random import choice
from copy import deepcopy

# We use the karger method for finding the minimum cut in a graph.
# Each row of "original_Graph" needs to match a vertice and each element of
# the row corrispond to the vertices to which it's connected.
# In addition in the first row there needs to be the first vertice, the second
# row the second vertice and so on.
# You also need to input the number of times you want the random "find_cut" to
# be performed.


def find_min_cut(original_Graph, num_repeats):
    min_cut = inf
    for ith_repeat in range(1, num_repeats + 1):
        print ith_repeat, "th repeat"
        Graph = deepcopy(original_Graph)
        cut = find_cut(Graph)
        if cut < min_cut:
            min_cut = cut
    return min_cut


def find_cut(Graph):
    # list_vertices keeps the the list of vertices and can be used for
    # selecting a vertice in the graph by using list_vertices.index(vertice).
    # It basically helps to keep track of the vertices in the graph.

    list_vertices = range(1, len(Graph) + 1)

    # I contract the edges until there are only two vertices
    for num_contraction in range(len(Graph) - 2):
        contract_edge(Graph, list_vertices)
    return count_cut(Graph)


def contract_edge(Graph, list_vertices):

    # I choose randomly two vertices connected to select and edge.
    rand_vertice = choice(list_vertices)
    edge = [rand_vertice, choose_edge(Graph, rand_vertice, list_vertices)]

    unite_edge(Graph, edge, list_vertices)
    clean_graph(Graph, edge, list_vertices)


def count_cut(Graph):
    # When you finished contracting the number of connection between the two
    # vertices is the length of the row containing the connection of the
    # vertices
    return len(Graph[0])


def choose_edge(Graph, vertice, list_vertices):
    # I choose a random connected vertice
    return choice(Graph[list_vertices.index(vertice)])


def unite_edge(Graph, edge, list_vertices):
    new_vertice = list_vertices.index(edge[0])
    old_vertice = list_vertices.index(edge[1])

    # Extend the first vertice with the connection of the second
    Graph[new_vertice].extend(Graph[old_vertice])

    # delete the copied vertice both from the graph and the list of vertices
    del Graph[old_vertice]
    del list_vertices[old_vertice]


def clean_graph(Graph, edge, list_vertices):
    # I iterate over the vertices and save the index of the row matching
    # of each vertice.
    for vertice in list_vertices:
        index_vertice = list_vertices.index(vertice)
        # I substitute the vertice deleted in unite_edge with the remaining
        # one
        if edge[1] in Graph[index_vertice]:
            subtitute_all_elements(Graph, index_vertice, edge[1], edge[0])
        if vertice == edge[0]:
            # I remove the self-connection
            Graph[index_vertice] = filter(
                lambda a: a != edge[0], Graph[index_vertice])


def subtitute_all_elements(Graph, index_vertice, old, new):
    for i in range(len(Graph[index_vertice])):
        if Graph[index_vertice][i] == old:
            Graph[index_vertice][i] = new

So I'm asking for a review. I have some main point that I would like to have commented:

  • The quality of my comments. Are they clear enough? too many? or to little?
  • The variables names are good enough?
  • using deepcopy in find_min_cut is a bad choice? would you have done differently?
  • Are there ways that can make it faster?
  • Would you have approached the problem differently? If yes why?

If you have other suggestions or thoughts please tell.

edit. An example of a graph is:

[[2, 3, 4, 7], [1, 3, 4], [1, 2, 4], [2, 3, 5], [4, 6, 7, 8], [5, 7, 8], [1, 5, 6, 8], [8, 5, 6, 7]]

the first list in the list corrispond to the vertice connected with the first vertice, the second list in the list corrispond to the vertice connected with the second vertice and so on. It is an undirected graph.

\$\endgroup\$
2
\$\begingroup\$

contract_edge does not select edges with uniform distribution, because first a random vertex is selected and then a random edge of that vertex is chosen. This produces a skewed distribution on edges, with edges on low degree vertices having a higher chance of beeing selected than those of high degree vertices.

\$\endgroup\$
1
\$\begingroup\$

One small way to improve it would be to remove the count_cut function. The body of the function is basically the same size as what you use to call it, so you might as well replace it with len(Graph[0]). This will make it more apparent what your code is doing, and will probably give a slight speed boost as well.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.