title: Uniform Cost Search in Python
body: <p>I have implemented a simple graph data structure in Python with the following structure below. The code is here just to clarify what the functions/variables mean, but they are pretty self-explanatory so you can skip reading it.</p>
  
  <pre class="lang-python prettyprint-override"><code># Node data structure
  class Node: 
  
      def __init__(self, label):        
          self.out_edges = []
          self.label = label
          self.is_goal = False
  
  
      def add_edge(self, node, weight = 0):          
          self.out_edges.append(Edge(node, weight))
  
  
  # Edge data structure
  class Edge:
  
      def __init__(self, node, weight = 0):          
          self.node = node
          self.weight = weight
  
      def to(self):                                  
          return self.node
  
  
  # Graph data structure, utilises classes Node and Edge
  class Graph:    
  
      def __init__(self):                             
          self.nodes = []
  
      # some other functions here populate the graph, and randomly select three goal nodes.
  </code></pre>
  
  <p>Now I am trying to implement a <a href="https://algorithmicthoughts.wordpress.com/2012/12/15/artificial-intelligence-uniform-cost-searchucs/" rel="noreferrer">uniform-cost search</a> (i.e. a BFS with a priority queue, guaranteeing a shortest path) which starts from a given node <code>v</code>, and returns a shortest path (in list form) to one of three goal node. By a <em>goal node</em>, I mean a node with the attribute <code>is_goal</code> set to true. </p>
  
  <p>This is my implementation:</p>
  
  <pre class="lang-python prettyprint-override"><code>def ucs(G, v):
      visited = set()                  # set of visited nodes
      visited.add(v)                   # mark the starting vertex as visited
      q = queue.PriorityQueue()        # we store vertices in the (priority) queue as tuples with cumulative cost
      q.put((0, v))                    # add the starting node, this has zero *cumulative* cost   
      goal_node = None                 # this will be set as the goal node if one is found
      parents = {v:None}               # this dictionary contains the parent of each node, necessary for path construction
  
      while not q.empty():             # while the queue is nonempty
          dequeued_item = q.get()        
          current_node = dequeued_item[1]             # get node at top of queue
          current_node_priority = dequeued_item[0]    # get the cumulative priority for later
  
          if current_node.is_goal:                    # if the current node is the goal
              path_to_goal = [current_node]           # the path to the goal ends with the current node (obviously)
              prev_node = current_node                # set the previous node to be the current node (this will changed with each iteration)
  
              while prev_node != v:                   # go back up the path using parents, and add to path
                  parent = parents[prev_node]
                  path_to_goal.append(parent)   
                  prev_node = parent
  
              path_to_goal.reverse()                  # reverse the path
              return path_to_goal                     # return it
  
          else:
              for edge in current_node.out_edges:     # otherwise, for each adjacent node
                  child = edge.to()                   # (avoid calling .to() in future)
  
                  if child not in visited:            # if it is not visited
                      visited.add(child)              # mark it as visited
                      parents[child] = current_node   # set the current node as the parent of child
                      q.put((current_node_priority + edge.weight, child)) # and enqueue it with *cumulative* priority
  </code></pre>
  
  <p>Now, after lots of testing and comparing with other alogrithms, this implementation seemed to work pretty well - up until I tried it with this graph:</p>
  
  <p><a href="https://i.stack.imgur.com/JWrBO.png" rel="noreferrer"><img src="https://i.stack.imgur.com/JWrBO.png" alt="Graph one"></a></p>
  
  <p>For whatever reason, <code>ucs(G,v)</code> returned the path <code>H -&gt; I</code> which costs 0.87, as opposed to the path <code>H -&gt; F -&gt; I</code>, costing 0.71 (this path was obtained by running a DFS). The following graph also gave an incorrect path:</p>
  
  <p><a href="https://i.stack.imgur.com/fOhFx.png" rel="noreferrer"><img src="https://i.stack.imgur.com/fOhFx.png" alt="Graph two"></a></p>
  
  <p>The algorithm gave <code>G -&gt; F</code> instead of <code>G -&gt; E -&gt; F</code>, obtained again by the DFS. The only pattern I can observe among these rare cases is the fact that the chosen goal node always has a loop. I can't figure out what is going wrong though. Any tips will be much appreciated.</p>