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 — python-patterns/graph_search.py at master · PhamPhi/python-patterns Expand file tree/ Copy pathgraph_search.pyMore file actions 86 lines (72 loc) · 2.4 KB / Copy pathgraph_search.pyFile metadata and controls86 lines (72 loc) · 2.4 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 #!/usr/bin/env python # -*- coding: utf-8 -*- class GraphSearch: """Graph search emulation in python, from source http://www.python.org/doc/essays/graphs/""" def __init__(self, graph): self.graph = graph def find_path(self, start, end, path=None): self.start = start self.end = end self.path = path if path else [] self.path += [self.start] if self.start == self.end: return self.path if self.start not in self.graph: return None for node in self.graph[self.start]: if node not in self.path: newpath = self.find_path(node, self.end, self.path) if newpath: return newpath return None def find_all_path(self, start, end, path=None): self.start = start self.end = end _path = path if path else [] _path += [self.start] if self.start == self.end: return [_path] if self.start not in self.graph: return [] paths = [] for node in self.graph[self.start]: if node not in _path: newpaths = self.find_all_path(node, self.end, _path[:]) for newpath in newpaths: paths.append(newpath) return paths def find_shortest_path(self, start, end, path=None): self.start = start self.end = end _path = path if path else [] _path += [self.start] if self.start == self.end: return _path if self.start not in self.graph: return None shortest = None for node in self.graph[self.start]: if node not in _path: newpath = self.find_shortest_path(node, self.end, _path[:]) if newpath: if not shortest or len(newpath) < len(shortest): shortest = newpath return shortest # example of graph usage graph = {'A': ['B', 'C'], 'B': ['C', 'D'], 'C': ['D'], 'D': ['C'], 'E': ['F'], 'F': ['C'] } # initialization of new graph search object graph1 = GraphSearch(graph) print(graph1.find_path('A', 'D')) print(graph1.find_all_path('A', 'D')) print(graph1.find_shortest_path('A', 'D')) ### OUTPUT ### # ['A', 'B', 'C', 'D'] # [['A', 'B', 'C', 'D'], ['A', 'B', 'D'], ['A', 'C', 'D']] # ['A', 'B', 'D'] |
| 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. |