""" graphutils.py Some utilities for searching graphs. See the comments at the end of the file for tests and an example. Jim Mahoney | cs.bennington.college | MIT License | April 2021 """ from random import choice # --- Stack and Queue helper classes ------------- class Stack: """ A Stack is a last-in, first-out data structure. In addition to the typical pop and push, this also implements len(stack) and a fast pythonic "x in stack" membership test. Here's an example of what you can do with it : >>> s = Stack() >>> s.push(1); s.push(2); s.push(3) >>> s.peek() # if we popped, what would we get? 3 >>> 1 in s True >>> (s.pop(), s.pop(), s.pop()) (3, 2, 1) >>> len(s) 0 """ # implemented with both a python list (self.value) and set (self.contains) def __init__(self): self.values = [] # Put values into a list ... self.contains = set() # and into a set def __len__(self): # This magic method is used by python to implement "len(stack") return len(self.values) def __contains__(self, value): # This magic method is used by python to implement "s in stack" return value in self.contains def push(self, value): self.values.append(value) # Put it at the end of the list self.contains.add(value) # ... and add it to the set. def pop(self): value = self.values.pop() # Pull it off of the end of the list self.contains.remove(value) # ... and remove it from the set. return value def peek(self): """ Return what pop would give us, but don't remove it. """ return self.values[-1] class Queue(Stack): """ A Queue is a first-in, first out data structure. This one has the same operations as the Stack above, but its pop operation pulls values in a different order. Here's an example of what you can do with it : >>> q = Queue() >>> q.push(1); q.push(2); q.push(3) >>> q.peek() # if we popped, what would we get? 1 >>> 5 in q False >>> (q.pop(), q.pop(), q.pop()) (1, 2, 3) >>> len(q) 0 """ # Inherit all behavior from Stack, except pop, which works differently. # This pope removes values from the start of the list, not the end. def pop(self): value = self.values.pop(0) # Pull it off of the start of the list self.contains.remove(value) # ... and remove it from the set. return value def peek(self): return self.values[0] # --- depth-first and breadth-first search, using a loop and a fringe ----- def just_print(vertex): """ For any vertex, print its str() description, and return False """ # This can be used for the is_target(vertex) function in graph_search. # It'll print each vertex in the order that the search finds them. # (Since this never returns True, the search doesn't stop print(vertex) return False def traverse(vertex): """ For any vertex, return False """ # Another is_target function that does a full traverse of the whole tree. return False def graph_search(depth_or_breadth, start, get_neighbors, is_target): """ Search a graph. If we find a vertex where is_target(v) is True, stop and return it. The arguments are : depth_or_breadth 'depth' or 'breadth' i.e. search order start the vertex where the search should start get_neighbors(v) a function that returns neigbors of a vertex is_target(v) a function applied to each vertex The vertices can any hashable data type. Since is_target(vertex) is passed each vertex as the search runs, it can have side-effects which accomplish whatever you like, in addition to just looking for a specific target. """ # The "visited" vertices are ones we've seen before and are done with. visited = set() # The "fringe" contains those that are scheduled to be examined later. fringe = Stack() if depth_or_breadth == 'depth' else Queue() fringe.push(start) # Initialize the fringe. while len(fringe) > 0: # More vertices to look at ? vertex = fringe.pop() # Get the next vertex. visited.add(vertex) # Remember not to use it again. if is_target(vertex): return vertex # Is this the one we want? for neighbor in get_neighbors(vertex): # Grow fringe with its neighbors. # Schedule this one to be looked at later # if we haven't seen it before and it isn't already scheduled. if not neighbor in visited and not neighbor in fringe: fringe.push(neighbor) # We looked at everything # Since is_target() never returned True, just return nothing. return None def get_search_tree(depth_breadth, start, get_neighbors, is_target=traverse): """ Search a graph, in exactly the same way that graph_search does, with exactly the same inputs. But this time, return a list of edges [(vertex,neighbor), ...] that were used to add each neighbor to the fringe. Only some of the edges from the graph will be in the tree, since we only put vertices into the fringe the first time the search finds them. Graph eges that "loop around" are not followed in the search. This list of edges will form a tree, with the start of the search at the top, and extending outward. """ tree = [] # The "visited" vertices are ones we've seen before and are done with. visited = set() # The "fringe" contains those that are scheduled to be examined later. fringe = Stack() if depth_breadth == 'depth' else Queue() fringe.push(start) # Initialize the fringe. while len(fringe) > 0: # More vertices to look at ? vertex = fringe.pop() # Get the next vertex. visited.add(vertex) # Remember not to use it again. if is_target(vertex): return tree # Is this the one we want? for neighbor in get_neighbors(vertex): # Grow fringe with its neighbors. # Schedule this one to be looked at later # if we haven't seen it before and it isn't already scheduled. if not neighbor in visited and not neighbor in fringe: tree.append( (vertex,neighbor) ) # Remember this tree edge. fringe.push(neighbor) return tree def random_backtrack_edges(start, get_neighbors): """ Return a list of edges generated by depth-first-backtrack """ # See https://en.wikipedia.org/wiki/Maze_generation_algorithm . # This is a variation of depth-first, which gives longer tunnels, # and therefore more satisfying mazes (connected acyclic graphs). # The differences here are (a) the order of the neighbors is randomized, # and (b) there is no fringe; instead we choose one neighbor to look # at next, and keep track of our path outwards with a Stack. When # a deadend is reached (a vertex with no unvisited neighbors), # we backtrack until we find an vertex with an unvisited neighbor, # and continue from there. tree = [] visited = set() path = Stack() path.push(start) while len(path) > 0: path_end = path.peek() # next vertex to visit, at end of path visited.add(path_end) # mark it as visited neighbors = get_neighbors(path_end) # get neighbors unvisited = set(neighbors).difference(visited) # ... that are unvisited if unvisited: # Any left along this path? path_next = choice(list(unvisited)) # Yes; continue path outwards. tree.append((path_end, path_next)) path.push(path_next) else: path.pop() # No; backtrack. return tree # --- an example ------------------------------------ # # Here's a small demo graph : # # A - B # | | # C - D - E # | # F # # Here's a dictionary of tuples giving its "adjacency matrix" . # For each vertex (letter), it's "neighbors" are the ones nearby, # connected with a - or | line. demo_graph = {'A' : ('B', 'C'), # A's neighbors are B, C 'B' : ('A', 'D'), # B's neighbors are A, D 'C' : ('A', 'D', 'F'), 'D' : ('C', 'B', 'E'), # D has three neighbors 'E' : ('D', ), # ... while E has only one. 'F' : ('C', ) } # And here's a get_neighbors(letter) function in a form # that can be used by the search funcions. def demo_neighbors(vertex): """ return neighbors of a vertext A through E in the demo graph """ return demo_graph[vertex] # Here's a "find target D" function def find_D(vertex): return vertex == 'D' # return True if this is 'D' def main(): """ --- some doctests ------- breadth-first printing search of demo_graph starting at A (closest to A found first: B,C are 1 away; D,F are 2 away; E is 3) >>> graph_search('breadth', 'A', demo_neighbors, just_print) A B C D F E >>> tree = get_search_tree('breadth', 'A', demo_neighbors, traverse) >>> tree [('A', 'B'), ('A', 'C'), ('B', 'D'), ('C', 'F'), ('D', 'E')] So that search used these edges : A ... which form a tree. 1/ \2 The C-D edge wasn't used. B C 3\ \4 D F 5/ E depth-first printing search of demo_graph starting at A (B is first neighbor of A; we visit it last.) >>> graph_search('depth', 'A', demo_neighbors, just_print) A C F D E B >>> tree = get_search_tree('depth', 'A', demo_neighbors, traverse) >>> tree [('A', 'B'), ('A', 'C'), ('C', 'D'), ('C', 'F'), ('D', 'E')] So that search used these edges : A ... which form a tree. 1/ \2 This time the B-D edge wasn't used. B C 3/ \4 D F 5/ E """ pass if __name__ == '__main__': import doctest doctest.testmod() main() # ----------------------------------------------------------- # --- output from running doctests with -v (verbose) flag --- # # mahoney@greymaple:Desktop$ python graphutils.py -v # Trying: # q = Queue() # Expecting nothing # ok # Trying: # q.push(1); q.push(2); q.push(3) # Expecting nothing # ok # Trying: # 5 in q # Expecting: # False # ok # Trying: # (q.pop(), q.pop(), q.pop()) # Expecting: # (1, 2, 3) # ok # Trying: # len(q) # Expecting: # 0 # ok # Trying: # s = Stack() # Expecting nothing # ok # Trying: # s.push(1); s.push(2); s.push(3) # Expecting nothing # ok # Trying: # 1 in s # Expecting: # True # ok # Trying: # (s.pop(), s.pop(), s.pop()) # Expecting: # (3, 2, 1) # ok # Trying: # len(s) # Expecting: # 0 # ok # Trying: # graph_search('breadth', 'A', demo_neighbors, just_print) # Expecting: # A # B # C # D # F # E # ok # Trying: # tree = get_search_tree('breadth', 'A', demo_neighbors, traverse) # Expecting nothing # ok # Trying: # tree # Expecting: # [('A', 'B'), ('A', 'C'), ('B', 'D'), ('C', 'F'), ('D', 'E')] # ok # Trying: # graph_search('depth', 'A', demo_neighbors, just_print) # Expecting: # A # C # F # D # E # B # ok # Trying: # tree = get_search_tree('depth', 'A', demo_neighbors, traverse) # Expecting nothing # ok # Trying: # tree # Expecting: # [('A', 'B'), ('A', 'C'), ('C', 'D'), ('C', 'F'), ('D', 'E')] # ok # 13 items had no tests: # __main__ # __main__.Queue.pop # __main__.Stack.__contains__ # __main__.Stack.__init__ # __main__.Stack.__len__ # __main__.Stack.pop # __main__.Stack.push # __main__.demo_neighbors # __main__.find_D # __main__.get_search_tree # __main__.graph_search # __main__.just_print # __main__.no_target # 3 items passed all tests: # 5 tests in __main__.Queue # 5 tests in __main__.Stack # 6 tests in __main__.main # 16 tests in 16 items. # 16 passed and 0 failed. # Test passed. # mahoney@greymaple:Desktop$ #