Design, I decided to adjacency list implementation, as underlying data structures there are: a list of vertices and list of lists (list of adjacent vertices for any given). I could have used a symbol table (more operation), but decided to keep things as simple as possible (graph algorithms are complicted on its own). A sample of code:
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 | # Simple graph API in Python, implementation uses adjacent lists. # look also here: # Classes: Graph, Depth_first_search, Depth_first_paths # Usage: # Creating new graph: gr1 = Graph(v) - creates new # graph with no edges and v vertices; # Search object: gr2 = Depth_first_search(graph, vertex) - # creates search object, # gr2.marked_vertex(vertex) - returns true if # given vertex is reachable from source(above) # Path object: gr3 = Depth_first_paths(graph, vertex)- # creates a new path object, # gr3.has_path(vertex) - thee same as above # gr3.path_to(vertex) - returns path from source vertex (to the given) from collections import deque class Graph: """Class graph, creates a graph - described by integers - number of vertices - V : v0, v1, ..., v(V-1)""" def __init__(self, v_in): """constructor - takes number of vertices and creates a graph with no edges (E = 0) and an empty adjacent lists of vertices""" self.V = v_in self.E = 0 self.adj = [] for i in range(v_in): self.adj.append([]) def V(self): """returns number of vertices""" return self.V def E(self): """returns number of edges""" return self.E def add_edge(self, v, w): """adds an edge to the graph, takes two integers (two vertices) and creates an edge v,w - by modifying appropriate adjacent lists """ self.adj[v].append(w) self.adj[w].append(v) self.E += 1 def adj_list(self, v): """Takes an integer - a graph vertex and returns the adjacency lists of it""" return self.adj[v] def __str__(self): """to string method, prints the graph""" s = str(self.V) + " vertices, " + str(self.E) + " edges\n" for v in range(self.V): s += str(v) + ": " for w in self.adj[v]: s += str(w) + " " s += "\n" return s class Depth_first_search: """class depth forst search, creates an object, constructor takes graph and a vertex""" def __init__(self, gr_obj, v_obj): self.marked = [False] * gr_obj.V self.cnt = 0 self.__dfs(gr_obj, v_obj) def __dfs(self, gr, v): """private depth first search, proceed recursively, mutates marked - marks the all possible to reach from given (v) vertices; also mutates cnt - number of visited vert""" self.marked[v] = True self.cnt += 1 for w in gr.adj_list(v): if self.marked[w] == False: self.__dfs(gr, w) def marked_vertex(self, w): """Takes an integer - a graph vertex and returns True if it's reachable from vertex v (source)""" return self.marked[w] def count(self): """returns number of visited verticles (from given in the constructor vertex)""" return self.cnt |
Why I did it in the java style? (Additional classes to given graph opertions) Primarly to avoid set and mutate global variables (in that case cnt in class Depth_first_search, I don't know how to solve it using function no object :/), also there is lots of graph tasks and operatons, and, imo, this approach is more clear (Did I really write this?:)). There are going to be updates on this definitely! Code obviously, also on github. Thanks, till the next time!
