Graph Search

graph_search.py

import sys
from Queue import Queue as Queue
class Node():
  def __init__(self, value, children=[]):
    self.value = value
    self.children = children
    self.prev = None
    self.visited = False

# Sample Graph based on https://en.wikipedia.org/wiki/Depth-first_search
# Algorithm avoids using a Stack
# Treat tuple position as a naming scheme e.g. graph_nodes pos 0 = node0
graph_nodes = (
    Node(1, [1, 6, 7]), # n0: [1, 6, 7] ...
    Node(2, [2, 5]),   # n1: [2,5] ..
    Node(3, [3, 4]), # n2
    Node(4), # n3
    Node(5), # n4
    Node(6), # n5
    Node(7), # n6
    Node(8, [8, 11, 0]), # n7
    Node(9, [7, 10, 9, 0]), # n8;  added n7 to create a clye :)
    Node(10), # n9
    Node(11), # n10
    Node(12) # n11
)

# search for value in graph, to search entire graph start at root pos: n0
# Any other position than pos 0 searches a subgraph beginning at node "pos"
def df_search(value, graph, pos=0):
  if value and graph:
     # Initial Setup
     not_finished = True
     current_node = graph[pos]
     # Graph Traversal
     while(not_finished):
         # 1. mark visited
         current_node.visited = True
         # 2. return value if found
         if current_node.value == value:
             return value
         # 3. if leaf: either exit (I've reached the beginning) or go prev node
         elif len(current_node.children) == 0:
             if current_node.prev == None: # at my start node
                return None
             else: # go to previous node
                pos = current_node.prev
                current_node = graph[pos]
                continue
         # 4. visit unvisited nodes
         start_from_top = False # need to continue twice
         for n in current_node.children: # n is an integer
            temp_node = graph[n]
            if not temp_node.visited:
                current_node = temp_node
                current_node.prev = pos
                pos = n # update position
                start_from_top = True
                break
         if start_from_top:
             continue # normally this is where a new function would go on stack
         # 5. have explored all children so go back if possible
         pos = current_node.prev
         if pos != None:
            current_node = graph[pos]
         else:
            return None # Visited all children, and have no prev so must be done

def bf_search(value, graph, pos=0):
    q = Queue()
    current_node = graph[pos] # the root node
    not_finished = True
    while(not_finished):
        if current_node.value == value:
            return value
        current_node.visited = True
        for n in current_node.children:
            if not graph[n].visited:
                q.put(n)
                #print("added %s into queue ", n)
        #print ("size of queue %s: ", q.qsize())
        if not q.empty():
            current_node = graph[q.get()]
        else:
            return None

def init():
    start = 0
    value = None
    if len(sys.argv) == 3:
        try:
            value = int(sys.argv[1])
        except:
            pass
        start = int(sys.argv[2])
    else:
        print("Use: python graph_search.py <value> <position: 0 for entire graph>")
        exit()

    print bf_search(value, graph_nodes, 0)


init()

# Possible Hacks
# If value is a string in the standard (Latin) ascii set (int 0 - 126):
### 1. can determine if node visited by flipping first byte to int > 126
### e.g. make first character invalid ascii; or choose any escape character

Added Breadth First Search Implementation. For simplicity I used a Queue (whereas in DFS I avoided the use of any data structure).

I Initially had a hiccup with Breadth-First-Search due to an infinite loop I wasn't preventing: I forgot to mark visited nodes to prevent cycles!

I blogged about the process of getting to this code and the hiccups in BFS here: http://sabelo.io/?p=715#update-1