# Random Contraction Min Cut (Karger) - performance issues

(Offtopic note: I can't add a "networkx" tag.)

I reworked an old algorithm, this time not implementing the graph on my own, but building on the networkx module.

Script works fine for the tests and the small test file, but takes forever (estimated at around 8 hours) on the large file.

I had trouble breaking the program and getting the profiling data as ctrl+c failed on powershell and windows cmd shell (no profiling data output).

To resolve this issue, I added a couple lines to print when the REPETITION was 300, a good enough number to sys.exit.

A good chunk of the time comes from the call to multigraph.py:567(edges_iter)'.

A note on how to examine who calls edges_iter so many times and any note on how to improve the performance would be appreciated.

Full code (rcontract_min_cut.py), small test file, big data file and old solution file here

Code:

'''
Created on Nov 1, 2015

@author: Ofer

Question 1
http://spark-public.s3.amazonaws.com/algo1/programming_prob/kargerMinCut.txt

The file contains the adjacency list representation of a simple undirected
graph. There are 200 vertices labeled 1 to 200. The first column in the file
represents the vertex label, and the particular row (other entries except the
first column) tells all the vertices that the vertex is adjacent to.

So for example, the 6th row looks like : "6 155 56 52 120 ......".
This just means that the vertex with label 6 is adjacent to
(i.e., shares an edge with) the vertices with labels 155,56,52,120,...,etc

Your task is to code up and run the randomized contraction algorithm for the
min cut problem and use it on the above graph to compute the min cut
(i.e., the minimum-possible number of crossing edges)

(HINT: figure out an implementation of edge contractions. You might want to do
this naively, creating a new graph from the old every time there's an edge
contraction. Think about more efficient implementations.)

(WARNING: Make sure to run the algorithm many times with different random
seeds, and remember the smallest cut that you ever find.)

Educational notes:
http://effbot.org/pyfaq/how-do-i-generate-random-numbers-in-python.htm
http://www.python-course.eu/graphs_python.php
http://shahriar.svbtle.com/underscores-in-python
https://wiki.python.org/moin/PythonDecoratorLibrary
http://pythoncentral.io/validate-python-function-parameters-and-return-types-with-decorators/

'''

# TODO: profiling and performance (300 REPETITION on large file)
#    ncalls  tottime  percall  cumtime  percall filename:lineno(function)
# 121342596   76.635    0.000   82.183    0.000 multigraph.py:567(edges_iter)
#     64603   13.865    0.000   96.048    0.001 multigraph.py:516(edges)
#  86584047    5.925    0.000    5.925    0.000 {method 'items' of 'dict' objects}
# 4774200/300    5.877    0.000   13.566    0.045 copy.py:137(deepcopy)
#   3163334    5.340    0.000    6.234    0.000 multigraph.py:175(add_edge)
#     59400    4.099    0.000   12.907    0.000 rcontract_min_cut.py:67(merge_nodes)
# 1631400/300    4.054    0.000   13.545    0.045 copy.py:242(_deepcopy_dict)
#      9814    3.964    0.000    3.964    0.000 {built-in method sorted}
#       300    3.540    0.012  115.882    0.386 rcontract_min_cut.py:81(rcontract_min_cut)
#  11406601    1.516    0.000    1.516    0.000 {method 'get' of 'dict' objects}

from copy import deepcopy
from random import choice as rchoice
from math import ceil, log
import logging
import matplotlib.pyplot as plt
import networkx as nx
import sys
import unittest

class ExtendedMultiGraph(nx.MultiGraph):
"""
MultiGraph - graph class that allows multiple undirected edges between
pairs of nodes.

Using netwrokx module:
-----
>>> import networkx as nx
>>> G=nx.Graph()
>>> print(sorted(G.nodes()))
[1, 2, 42]
>>> print(sorted(G.edges()))
[(1, 2)]
"""

def merge_nodes(self, v, u):
for node in self[u]:
for parallel_index in range(len(self[u][node])):  # @UnusedVariable
self.remove_node(u)

self_loops = True
while self_loops is True:
try:
self.remove_edge(v, v)
except nx.NetworkXError:
self_loops = False

def rcontract_min_cut(self):
"""
David Karger's '90s Random Contraction Algorithm

-    While there are more than 2 vertices:
i.    Pick a remaining edge (u,v) uniformly at random.
ii.    Merge (or “contract”) u and v into a single vertex.
iii.   Remove self-loops
-    Return cut represented by final 2 vertices.
"""
min_cut = 0
tmp_graph = deepcopy(self)
total_of_nodes = len(tmp_graph.nodes())

# edge cases:
if total_of_nodes in (0, 1):
return min_cut

# contraction loop (need to contract len-2 times to reach 2 nodes)
for nodes_count in reversed(range(3, total_of_nodes+1)):
# i. Pick a remaining edge (u,v) uniformly at random.
v, u = rchoice(tmp_graph.edges())
# ii. Merge (or “contract”) u and v into a single vertex.
# iii.   Remove self-loops
tmp_graph.merge_nodes(v, u)

# result passing
total_of_nodes = len(tmp_graph.nodes())
if total_of_nodes is 2:
min_cut = len(tmp_graph.edges())
return min_cut
else:
print("Error in rcontract_min_cut")
return min_cut
return min_cut

def get_min_cut(self):
min_cut = float('inf')
len_nodes = len(self.nodes())

# TODO: test repetition value + efficacy
# Repetition = n**2 -> p[fail]=1/e
# Repetition = n**2*ln(n) -> p[fail]=1/n
# We'd be happy enough with 95% chance of success:
# Repetition = n**2*3 -> (1/e)**-3 < 5 %
if len_nodes <= 10:
REPETITION = 1000  # reduce chances of failure further than 1/n
else:
REPETITION = ceil(pow(len_nodes, 2)*3)
print("Reps:", REPETITION)

# run randomized contraction + save best min_cut result
for rep in range(REPETITION):
if rep % 100 is 0:
print(rep, "complete, min_cut=", min_cut)
if rep % 300 is 0 and rep is not 0:
sys.exit()
temp_min_cut = self.rcontract_min_cut()
if temp_min_cut < min_cut:
min_cut = temp_min_cut
return min_cut

@staticmethod
def init_graph_wstrings(node_data_strings):
"""
Initialize a new ExtendedMultiGraph:
Accepts a list of strings, each holding information regarding
a single node (first element) and its connections (separated by spaces)
Returns a graph_object of type ExtendedMultiGraph(nx.MultiGraph)
Holding node and edge information of the input data.
"""
graph_object = ExtendedMultiGraph()
for line in node_data_strings:
assigned_node = False
line_elements = list(map(int, line.split()))
if line_elements[0] in graph_object.nodes():
assigned_node = True
# TODO: test without initial node assignment
# else:
for element_index in range(1, len(line_elements)):
# if edge already listed, skip
if (
# edge has been assigned by another
assigned_node and
# edge entered already into graph
tuple(
sorted(
(line_elements[0],
line_elements[element_index])
)
) in sorted(graph_object.edges())):
continue
(graph_object
return graph_object

class ExtendedMultiGraphTestCase(unittest.TestCase):
"""Tests for rcontract_min_cut.py"""

def test_networkx_module(self):
my_graph = ExtendedMultiGraph()
self.assertEqual(sorted(my_graph.nodes()), [1, 2, 42])
self.assertEqual(sorted(my_graph.edges()), [(1, 2)])

def test_init_graph_wstrings(self):
"1    4    3",
"2    3",
"3    1    2",
"4    1"
]

self.assertEqual(sorted(my_graph.nodes()), [1, 2, 3, 4])
self.assertEqual(sorted(my_graph.edges()), [(1, 3), (1, 4), (2, 3)])

def test_get_min_cut(self):

my_graph1 = ExtendedMultiGraph()  # empty graph
min_cut1 = my_graph1.get_min_cut()
self.assertEqual(min_cut1, 0)

my_graph2 = ExtendedMultiGraph()  # single node graph
self.assertEqual(sorted(my_graph2.nodes()), [1])
self.assertEqual(sorted(my_graph2.edges()), [(1, 1)])
min_cut2 = my_graph2.get_min_cut()
self.assertEqual(min_cut2, 0)

my_graph3 = ExtendedMultiGraph()  # isolated node
self.assertEqual(sorted(my_graph3.nodes()), [1, 2, 42])
self.assertEqual(sorted(my_graph3.edges()), [(1, 2), (1, 2)])
min_cut3 = my_graph3.get_min_cut()
self.assertEqual(min_cut3, 0)

my_graph3.remove_node(42)
min_cut4 = my_graph3.get_min_cut()
self.assertEqual(min_cut4, 2)

def test_somthing(self):
# TODO: implement some tests
pass

def main(file_name):
# take values from file and run quick_sort
with open(file_name) as fh:
if file_name[:4] == 'test':

# populate graph
node_data_strings = [line.strip() for line in fh]
my_graph = ExtendedMultiGraph.init_graph_wstrings(node_data_strings)

min_cut = my_graph.get_min_cut()

print(min_cut)

if __name__ == '__main__':
# working with argv to accept file input
if len(sys.argv) > 2:
sys.exit("Usage: inv_count <file_name> (leave empty for testing)")
if len(sys.argv) == 1:
print("No filename input, testing...")
unittest.main()
# else: argv == 2
main(sys.argv[1])