GeezerVisonThe World Wide Web, restored to 800 pixels of glory. |
| Home|About|Gaming cabinet|Archives|How it works|Starter sites |
GeezerVison is showing github.com — pygorithm/pygorithm/data_structures/graph.py at master · OmkarPathak/pygorithm Expand file tree/ Copy pathgraph.pyMore file actions 421 lines (360 loc) · 12.8 KB / Copy pathgraph.pyFile metadata and controls421 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 <[email protected]> """ # 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 are visitor 01402520 — GeezerVison does not store the pages you look up. Best viewed with Netscape Navigator 4.7 or Internet Explorer 6 at 800×600. No cookies required. |