{{ message }}
Repository navigation
Expand file tree
/
Copy pathgraph.py
More file actions
421 lines (360 loc) · 12.8 KB
/
Copy pathgraph.py
File metadata and controls
421 lines (360 loc) · 12.8 KB
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
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
"""
Author: OMKAR PATHAK
Created On: 12th August 2017
"""
from collections import defaultdict
import inspect
import math
class Graph(object):
"""Graph object
Creates the graph
"""
def __init__(self):
self.graph = defaultdict(list)
self.count = 0
def print_graph(self):
"""
Prints the contents of the graph
"""
for i in self.graph:
print(i, '->', ' -> '.join([str(j) for j in self.graph[i]]))
def add_edge(self, from_vertex, to_vertex):
"""
Adds an edge in the graph
"""
# check if vertex is already present
self.graph[from_vertex].append(to_vertex)
self.count += 1
def get_code(self):
"""
returns the code for the current class
"""
return inspect.getsource(Graph)
class WeightedGraph(object):
"""WeightedGraph object
A graph with a numerical value (weight) on edges
"""
def __init__(self):
self.vertexes = set()
self.graph = {}
self._forest = None
def get_weight(self, u, v):
"""
Returns the weight of an edge between vertexes u and v.
If there isnt one: return None.
"""
return self.graph.get((u,v), self.graph.get((v,u), None))
def add_edge(self, u, v, weight):
"""
:param u: from vertex - type : integer
:param v: to vertex - type : integer
:param weight: weight of the edge - type : numeric
"""
if self.get_weight(u, v) != None:
print("Such edge already exists!")
else:
self.vertexes.update((u, v))
self.graph[(u,v)] = weight
def print_graph(self):
"""
Print the graph
:return: None
"""
for (u, v) in self.graph:
print("%d -> %d weight: %d" % (u, v, self.graph[(u, v)]))
def _set_of(self, vertex):
"""
Helper method
:param vertex:
:return:
"""
for tree in self._forest:
if vertex in tree:
return tree
return None
def _union(self, u_set, v_set):
"""
Helper method
:param u_set:
:param v_set:
:return:
"""
self._forest.remove(u_set)
self._forest.remove(v_set)
self._forest.append(v_set + u_set)
def kruskal_mst(self):
"""
Kruskal algorithm for finding the minimum spanning tree of a weighted graph.
This version use a union-find data structure.
More detailed info here: https://en.wikipedia.org/wiki/Kruskal%27s_algorithm
Author: Michele De Vita <mik3dev@gmail.com>
"""
# sort by weight
self.graph = {k: self.graph[k] for k in sorted(self.graph, key=self.graph.get, reverse=False)}
edges_explored = []
self._forest = [[v] for v in self.vertexes]
for (u, v) in self.graph:
u_set, v_set = self._set_of(u), self._set_of(v)
if u_set != v_set:
self._union(u_set, v_set)
edges_explored.append(((u, v), self.graph[u, v]))
return edges_explored
# TODO: Is this necessary?
@staticmethod
def kruskal_time_complexity():
"""
Return time complexity of kruskal
:return: string
"""
return "Worst case: O(E log(V)) where E in the number of edges and V the number of vertexes"
@classmethod
def kruskal_code(cls):
"""
Returns the code for current class
"""
return inspect.getsource(cls.kruskal_mst)
class WeightedUndirectedGraph(object):
"""WeightedUndirectedGraph object
A graph with a numerical value (weight) on edges, which
is the same for both directions in an undirected graph.
"""
def __init__(self):
self.graph = {}
self.weights = {}
def add_edge(self, u, v, weight):
"""
Adds the specified edge to this graph. If the edge already exists,
this will only modify the weight (not create duplicates).
:param u: from vertex
:param v: to vertex
:param weight: weight of the edge - type : numeric
"""
changing_weight = (u, v) in self.weights.keys()
self.weights[(u, v)] = weight
self.weights[(v, u)] = weight
if changing_weight:
return
if u in self.graph.keys():
self.graph[u].append(v)
else:
self.graph[u] = [v]
if v in self.graph.keys():
self.graph[v].append(u)
else:
self.graph[v] = [u]
def get_edge_weight(self, u, v):
"""
Gets the weight between u and v if such an edge
exists, or None if it does not.
:param u: one edge
:param v: the other edge
:return: numeric or None
"""
return self.weights.get((u, v), None)
def remove_edge(self, edge, other_edge_or_none=None):
"""
Removes the specified edge from the grid entirely or,
if specified, the connection with one other edge.
Behavior is undefined if the connection does not
exist.
:param edge: the edge to remove
:param other_edge_or_none: an edge connected to edge or none
"""
if other_edge_or_none is not None:
del self.weights[(edge, other_edge_or_none)]
del self.weights[(other_edge_or_none, edge)]
edge_list = self.graph[edge]
other_edge_list = self.graph[other_edge_or_none]
if len(edge_list) == 1:
del self.graph[edge]
else:
self.graph[edge].remove(other_edge_or_none)
if len(other_edge_list) == 1:
del self.graph[other_edge_or_none]
else:
self.graph[other_edge_or_none].remove(edge)
else:
edge_list = self.graph[edge]
del self.graph[edge]
for other_edge in edge_list:
del self.weights[(edge, other_edge)]
del self.weights[(other_edge, edge)]
other_edge_list = self.graph[other_edge]
if len(other_edge_list) == 1:
del self.graph[other_edge]
else:
other_edge_list.remove(edge)
def gridify(self, size, weight):
"""
Constructs connections from a square grid starting at (0, 0)
until (size-1, size-1) with connections between adjacent and
diagonal nodes. Diagonal nodes have a weight of weight*sqrt(2)
:param size: the size of the square grid to construct - type : integer
:param weight: the weight between orthogonal nodes. - type: numeric
:return: None
"""
rt2 = math.sqrt(2)
acceptable_offsets = [
(-1, -1, rt2), (-1, 0, 1), (-1, 1, rt2),
(0, -1, 1), (0, 1, 1),
(1, -1, rt2), (1, 0, 1), (1, 1, rt2)
]
for x in range(0, size):
for y in range(0, size):
for offset in acceptable_offsets:
nx = x + offset[0]
ny = y + offset[1]
if nx >= 0 and ny >= 0 and nx < size and ny < size:
self.add_edge((x, y), (nx, ny), weight * offset[2])
class TopologicalSort(Graph):
def topological_sort(self):
"""
function for sorting graph elements using topological sort
"""
# Marking all vertices as not visited
visited = [False] * self.count
# Stack for storing the vertex
stack = []
for vertex in range(self.count):
# Call the recursive function only if not visited
if not visited[vertex]:
self.__topological_sort_rec(vertex, visited, stack)
return stack
def __topological_sort_rec(self, vertex, visited, stack):
"""
Recursive function for topological Sort
"""
# Mark the current node in visited
visited[vertex] = True
# mark all adjacent nodes of the current node
try:
for adjacent_node in self.graph[vertex]:
if not visited[adjacent_node]:
self.__topological_sort_rec(adjacent_node, visited, stack)
except KeyError:
return
# Push current vertex to stack which stores the result
stack.insert(0, vertex)
def get_code(self):
"""
returns the code for the current class
"""
return inspect.getsource(TopologicalSort)
class CheckCycleDirectedGraph(object):
"""CheckCycleDirectedGraph
Class to check cycle in directed graph
"""
def __init__(self):
self.graph = {}
self.count = 0
def print_graph(self):
"""
for printing the contents of the graph
"""
for i in self.graph:
print(i, '->', ' -> '.join([str(j) for j in self.graph[i]]))
def add_edge(self, from_vertex, to_vertex):
"""
function to add an edge in the graph
"""
# check if vertex is already present
if from_vertex in self.graph.keys():
self.graph[from_vertex].append(to_vertex)
self.count += 1
else:
self.graph[from_vertex] = [to_vertex]
self.count += 1
def check_cycle(self):
"""
This function will return True if graph is cyclic else return False
"""
visited = [False] * len(self.graph)
stack = [False] * len(self.graph)
for vertex in range(len(self.graph)):
if not visited[vertex]:
if self.__check_cycle_rec(visited, stack, vertex):
return True
return False
def __check_cycle_rec(self, visited, stack, vertex):
"""
Recursive function for finding the cycle
"""
# Mark the current node in visited and also add it to the stack
visited[vertex] = True
stack[vertex] = True
# mark all adjacent nodes of the current node
for adjacentNode in self.graph[vertex]:
if not visited[adjacentNode]:
if self.__check_cycle_rec(visited, stack, adjacentNode):
return True
elif stack[adjacentNode]:
return True
# The node needs to be popped from
# recursion stack before function ends
stack[vertex] = False
return False
@staticmethod
def get_code():
"""
returns the code for the current class
"""
return inspect.getsource(CheckCycleDirectedGraph)
class CheckCycleUndirectedGraph(object):
"""CheckCycleUndirectedGraph
Class to check cycle in undirected graph
"""
def __init__(self):
self.graph = {}
self.count = 0
def print_graph(self):
"""
for printing the contents of the graph
"""
for i in self.graph:
print(i, '->', ' -> '.join([str(j) for j in self.graph[i]]))
def add_edge(self, from_vertex, to_vertex):
"""
for adding the edge between two vertices
"""
# check if vertex is already present,
if from_vertex in self.graph.keys():
self.graph[from_vertex].append(to_vertex)
else:
# otherwise add it to the graph
self.graph[from_vertex] = [to_vertex]
if to_vertex in self.graph.keys():
self.graph[to_vertex].append(from_vertex)
else:
self.graph[to_vertex] = [from_vertex]
def check_cycle(self):
"""
This function will return True if graph is cyclic else return False
"""
# Marking all vertices as not visited
visited = [False] * len(self.graph)
for vertex in range(len(self.graph)):
# Call the recursive function only if not visited
if not visited[vertex]:
if self.__check_cycle_rec(visited, -1, vertex):
return True
return False
def __check_cycle_rec(self, visited, parent, vertex):
"""
Recursive function for finding the cycle
"""
# Mark the current node in visited
visited[vertex] = True
# mark all adjacent nodes of the current node
for adjacentNode in self.graph[vertex]:
if not visited[adjacentNode]:
if self.__check_cycle_rec(visited, vertex, adjacentNode):
return True
elif parent != adjacentNode:
return True
return False
@staticmethod
def get_code():
"""
returns the code for the current class
"""
return inspect.getsource(CheckCycleUndirectedGraph)
You can’t perform that action at this time.