Skip to content

Commit 7413d49

Browse files
prakhar1989prakhar1989
committed
Updated graph lib
1 parent 7c7c876 commit 7413d49

6 files changed

Lines changed: 326 additions & 82 deletions

File tree

‎README.md‎

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -19,6 +19,7 @@ Completed
1919
- Dijkstra's Shortest Path - O(mlogn)
2020
- Prim's Minimum Cost Spanning Tree - O(mlogn)
2121
- Kruskal's Minimum Spanning Tree - O(mlogn)
22+
- Max k Clustering
2223
- Heap datastructure
2324
- Max heaps
2425
- Min heaps (priority queue)

‎graphs/clustering.py‎

Lines changed: 239 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,239 @@
1+
data = """1 2 6808
2+
1 3 5250
3+
1 4 74
4+
1 5 3659
5+
1 6 8931
6+
1 7 1273
7+
1 8 7545
8+
1 9 879
9+
1 10 7924
10+
1 11 7710
11+
1 12 4441
12+
1 13 8166
13+
1 14 4493
14+
1 15 3043
15+
1 16 7988
16+
1 17 2504
17+
1 18 2328
18+
1 19 1730
19+
1 20 8841
20+
2 3 4902
21+
2 4 812
22+
2 5 6617
23+
2 6 6892
24+
2 7 8672
25+
2 8 1729
26+
2 9 6672
27+
2 10 1662
28+
2 11 7046
29+
2 12 3121
30+
2 13 241
31+
2 14 7159
32+
2 15 9454
33+
2 16 9628
34+
2 17 5351
35+
2 18 3712
36+
2 19 5564
37+
2 20 9595
38+
3 4 3782
39+
3 5 1952
40+
3 6 9231
41+
3 7 3322
42+
3 8 3214
43+
3 9 5129
44+
3 10 1951
45+
3 11 8601
46+
3 12 8960
47+
3 13 9755
48+
3 14 9993
49+
3 15 5195
50+
3 16 3331
51+
3 17 8633
52+
3 18 3560
53+
3 19 8778
54+
3 20 7780
55+
4 5 5000
56+
4 6 4521
57+
4 7 4516
58+
4 8 2578
59+
4 9 9923
60+
4 10 7143
61+
4 11 3981
62+
4 12 5882
63+
4 13 6886
64+
4 14 31
65+
4 15 6326
66+
4 16 2437
67+
4 17 6995
68+
4 18 3946
69+
4 19 2603
70+
4 20 3234
71+
5 6 8696
72+
5 7 6896
73+
5 8 5665
74+
5 9 5601
75+
5 10 5119
76+
5 11 5118
77+
5 12 3724
78+
5 13 1618
79+
5 14 3755
80+
5 15 9569
81+
5 16 8588
82+
5 17 4576
83+
5 18 4914
84+
5 19 8123
85+
5 20 4158
86+
6 7 2495
87+
6 8 3894
88+
6 9 3065
89+
6 10 4564
90+
6 11 5430
91+
6 12 5502
92+
6 13 6873
93+
6 14 6941
94+
6 15 8054
95+
6 16 4330
96+
6 17 2233
97+
6 18 2281
98+
6 19 9360
99+
6 20 5475
100+
7 8 2739
101+
7 9 4442
102+
7 10 4843
103+
7 11 8503
104+
7 12 5466
105+
7 13 5370
106+
7 14 8012
107+
7 15 3909
108+
7 16 3503
109+
7 17 1844
110+
7 18 5374
111+
7 19 7081
112+
7 20 9837
113+
8 9 3060
114+
8 10 5421
115+
8 11 5098
116+
8 12 4080
117+
8 13 3019
118+
8 14 8318
119+
8 15 9158
120+
8 16 2031
121+
8 17 722
122+
8 18 4052
123+
8 19 1072
124+
8 20 9529
125+
9 10 7569
126+
9 11 563
127+
9 12 5705
128+
9 13 9597
129+
9 14 4813
130+
9 15 6965
131+
9 16 8810
132+
9 17 5046
133+
9 18 17
134+
9 19 1710
135+
9 20 2262
136+
10 11 3444
137+
10 12 370
138+
10 13 8675
139+
10 14 5780
140+
10 15 6209
141+
10 16 2586
142+
10 17 9086
143+
10 18 4323
144+
10 19 1212
145+
10 20 79
146+
11 12 1975
147+
11 13 1665
148+
11 14 3396
149+
11 15 9439
150+
11 16 594
151+
11 17 5821
152+
11 18 6006
153+
11 19 836
154+
11 20 2450
155+
12 13 6821
156+
12 14 5835
157+
12 15 8470
158+
12 16 3141
159+
12 17 9413
160+
12 18 760
161+
12 19 3568
162+
12 20 7424
163+
13 14 4357
164+
13 15 6374
165+
13 16 7456
166+
13 17 6025
167+
13 18 9458
168+
13 19 3064
169+
13 20 9874
170+
14 15 9946
171+
14 16 6500
172+
14 17 2476
173+
14 18 4187
174+
14 19 6686
175+
14 20 9103
176+
15 16 8910
177+
15 17 5182
178+
15 18 4761
179+
15 19 8506
180+
15 20 4676
181+
16 17 881
182+
16 18 4769
183+
16 19 2903
184+
16 20 66
185+
17 18 2747
186+
17 19 7119
187+
17 20 2874
188+
18 19 6302
189+
18 20 7382
190+
19 20 1143
191+
"""
192+
import os, sys
193+
sys.path.append(os.path.join(os.getcwd(), os.path.pardir))
194+
from graphs.graph import graph
195+
from union_find.unionfind import UnionFind
196+
197+
def max_k_clustering(gr, k):
198+
sorted_edges = sorted(gr.get_edge_weights())
199+
uf = UnionFind()
200+
#initialize each node as its cluster
201+
for n in gr.nodes():
202+
uf.insert(n)
203+
for (w, (u, v)) in sorted_edges:
204+
if uf.count_groups() <= k:
205+
return uf.get_sets()
206+
if uf.get_leader(u) != uf.get_leader(v):
207+
uf.make_union(uf.get_leader(u), uf.get_leader(v))
208+
209+
def compute_spacing(c1, c2):
210+
min = float('inf')
211+
for n in c1:
212+
for v in c2:
213+
cost = gr.get_edge_weight((n, v))
214+
if cost < min:
215+
min = cost
216+
return min
217+
218+
def get_max_spacing(clusters):
219+
min = float('inf')
220+
for u in clusters:
221+
for v in clusters:
222+
if u!= v:
223+
spacing = compute_spacing(u,v)
224+
if spacing < min:
225+
min = spacing
226+
return min
227+
228+
if __name__ == "__main__":
229+
edges = [l.split() for l in data.splitlines()]
230+
gr = graph()
231+
232+
for (u, v, w) in edges:
233+
if u not in gr.nodes():
234+
gr.add_node(u)
235+
if v not in gr.nodes():
236+
gr.add_node(v)
237+
gr.add_edge((u, v), int(w))
238+
239+
print "Min Spacing - %s " % (get_max_spacing(max_k_clustering(gr, 4)))

‎graphs/digraph.py‎

Lines changed: 4 additions & 15 deletions
Original file line numberDiff line numberDiff line change
@@ -5,10 +5,8 @@ class digraph(graph):
55
Directed Graph class - made of nodes and edges
66
77
methods: add_edge, add_edges, add_node, add_nodes, has_node,
8-
has_edge, nodes, edges, add_node_attribute, node_attributes
9-
neighbors, del_node, del_edge, node_order, set_edge_weight,
10-
get_edge_weight, set_edge_properties, get_edge_properties
11-
clear_node_attributes, get_transpose
8+
has_edge, nodes, edges, neighbors, del_node, del_edge, node_order,
9+
set_edge_weight, get_edge_weight,
1210
"""
1311

1412
DEFAULT_WEIGHT = 1
@@ -17,12 +15,6 @@ class digraph(graph):
1715
def __init__(self):
1816
self.node_neighbors = {}
1917

20-
# Metadata about edges
21-
self.edge_properties = {} # Edge -> dict mapping
22-
23-
# Metadata about nodes
24-
self.node_attr = {} # Node -> dict mapping
25-
2618
def __str__(self):
2719
return "Directed Graph \nNodes: %s \nEdges: %s" % (self.nodes(), self.edges())
2820

@@ -33,11 +25,8 @@ def add_edge(self, edge, wt=1, label=""):
3325
with m as head and n as tail : m -> n
3426
"""
3527
u, v = edge
36-
if not self.has_node(v):
37-
raise Exception("Node %s is not there in the graph" % v)
3828
if (v not in self.node_neighbors[u]):
39-
self.node_neighbors[u].append(v)
40-
self.set_edge_properties((u, v), label=label, weight=wt)
29+
self.node_neighbors[u][v] = wt
4130
else:
4231
raise Exception("Edge (%s, %s) already added in the graph" % (u, v))
4332

@@ -49,7 +38,7 @@ def del_edge(self, edge):
4938
u, v = edge
5039
if not self.has_edge(edge):
5140
raise Exception("Edge (%s, %s) not an existing edge" % (u, v))
52-
self.node_neighbors[u].remove(v)
41+
del self.node_neighbors[u][v]
5342

5443
def del_node(self, node):
5544
"""

0 commit comments

Comments
 (0)