-
Notifications
You must be signed in to change notification settings - Fork 1
/
karger_mincut.py
184 lines (147 loc) · 7.16 KB
/
karger_mincut.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
"""Python implementation of Karger's mincut algorithm.
Karger Mincut is a type of Monte Carlo algorithm and has to be run
multiple times with a hope to find minimum cuts, but with no guarantee.
Implementation notes:
Three containers are in play, while node contraction progresses.
1. Copy of a graph in a form of weighted adjacency list, where weight
represents a number of connections between points.
2. Copy of edges list.
3. Index dictionary, which maps tail points with indexes of edges location in
edges list where such a node is present.
Randomness is realized by random.shuffle function.
"""
from collections import defaultdict
from random import shuffle
from copy import deepcopy
TESTCASE = {
'a': {'b': 1, 'c': 1},
'b': {'a': 1, 'c': 1, 'd': 1},
'c': {'a': 1, 'b': 1, 'd': 1},
'd': {'b': 1, 'c': 1}
}
class MinCut:
"""Public run_mincut(runs) method does the job. Results are hold by
instance variables mincuts_num and mincuts_edges.
"""
def __init__(self, graph):
"""Graph and edges variables are initialized instantly. Graph is the original
input graph and won't be changed at any point. Instead, it will be copied for
each mincut run. The edges variable will only be shuffled before each run and
then copied for further modifications.
Mincuts_num and mincuts_edges will keep the minimum cut results and will be
updated after each run if better values are discovered.
"""
self.graph = graph
self.edges = []
self._generate_edges()
self.mincuts_num = float('inf')
self.mincuts_edges = []
def _generate_edges(self):
"""Generates a list of edges. The list helps to get uniformly random distribution
of edges. Randomness will be realized by shuffling the list before each mincut run.
"""
for tail in self.graph:
for head in self.graph[tail]:
self.edges.append([tail, head])
@staticmethod
def edges_index_mapper(edges):
"""Returns a dictionary, which holds tail vertex as a key and
set of indexes as a value. Indexes point at location of an edge
in the 'edges' list.
"""
mapper = defaultdict(set)
for idx, edge in enumerate(edges):
mapper[edge[0]].add(idx)
return mapper
def contract(self):
"""Three containers are in play, while node contraction progresses.
1. Copy of a graph in form of adjacency list. Contracted points are deleted.
2. Copy of edges list, which is traversed backwards from the last index.
Original edges list is shuffled before each run and then the copy is made.
Self-loops are set to None. Edges, which are to be updated are localized by
taking use of an index dictionary.
3. Index dictionary maps tail points with indexes of edges list where such
a node exists. Indexes are updated and removed during contraction process.
Returns remaining edges after contraction is finished.
"""
shuffle(self.edges)
edges = deepcopy(self.edges)
graph_copy = deepcopy(self.graph)
indexes = self.edges_index_mapper(edges)
last_edge_idx = len(edges) - 1
while len(graph_copy) > 2:
edge = edges[last_edge_idx]
last_edge_idx -= 1
if edge is None:
continue
# Merging vertex, merged vertex
node_kept, node_merged = edge
# Replace merged node with kept node in all edges it's been a part of as head.
for vertex in graph_copy[node_merged]:
if node_kept not in graph_copy[vertex]:
graph_copy[vertex][node_kept] = graph_copy[vertex][node_merged]
else:
graph_copy[vertex][node_kept] += graph_copy[vertex][node_merged]
del graph_copy[vertex][node_merged]
# Expand kept node with edge from merged node.
if vertex not in graph_copy[node_kept]:
graph_copy[node_kept][vertex] = graph_copy[node_merged][vertex]
else:
graph_copy[node_kept][vertex] += graph_copy[node_merged][vertex]
# Change edges in edges list, using index locations from indexes dictionary.
for idx in tuple(indexes[vertex]):
if edges[idx][0] == node_kept and edges[idx][1] == node_merged: # self-loop
edges[idx] = None
indexes[node_kept].discard(idx)
elif edges[idx][1] == node_merged:
edges[idx][1] = node_kept
# Replace merged node with kept node in all edges it's been a part of as tail.
for edge_idx in tuple(indexes[node_merged]):
if edges[edge_idx][1] == node_kept: # self-loop
edges[edge_idx] = None
indexes[node_merged].discard(edge_idx)
else:
edges[edge_idx][0] = node_kept
# Remove self-loops form node_kept
graph_copy[node_kept].pop(node_kept, None)
# Add edge indexes from merged node to kept node.
indexes[node_kept].update(indexes[node_merged])
# Remove contracted node from graph and from edge index mapper.
del graph_copy[node_merged]
del indexes[node_merged]
# Return original edges that survived contraction.
return [self.edges[e] for e in indexes[list(graph_copy.keys())[0]]]
def run_mincut(self, runs):
"""Runs contraction algorithm multiple times, specified by
the 'runs' parameter. Keeps minimum cuts number and edges in
instance variables: mincuts_num and mincuts_edges.
"""
for _ in range(runs):
edges = self.contract()
current_cuts_num = len(edges)
if current_cuts_num < self.mincuts_num:
self.mincuts_num = current_cuts_num
self.mincuts_edges = edges
if __name__ == "__main__":
import networkx as nx
import matplotlib.pyplot as plt
m = MinCut(TESTCASE)
m.run_mincut(50)
all_edges = m.edges
# all_edges have duplicated edges in reversed points order. Example: [1, 2] and [2, 1].
# Duplicate edges are not necessary for applying color to the graph.
# So, either we remove duplicates from all_edges or add reversed edges to m.mincuts_edges list,
# where edges are present without their reversed reflections. We choose the latter approach.
mincut_edges = []
for anedge in m.mincuts_edges:
mincut_edges.append(anedge)
mincut_edges.append(anedge[::-1])
# Define color for every edge. Red for the mincut edges and black for the rest.
colors = ['r' if e in mincut_edges else 'black' for e in all_edges]
print(m.mincuts_edges) # Mincut edges
print('Number of mincut edges: ', m.mincuts_num)
G = nx.MultiGraph(all_edges)
# edgelist parameter has to be given to assure the right order of edges sequence,
# which otherwise, would be messed up under the hood of networkx module.
nx.draw(G, edgelist=all_edges, edge_color=colors, with_labels=True, width=1.7)
plt.show()