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) 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) old_vertice = list_vertices.index(edge) # 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 in Graph[index_vertice]: subtitute_all_elements(Graph, index_vertice, edge, edge) if vertice == edge: # I remove the self-connection Graph[index_vertice] = filter( lambda a: a != edge, 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?
find_min_cutis 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.