#! /usr/bin/python

# Searches for the shortest path from an initial set of nodes to
# a target set of nodes.  Uses Dijkstra's Single Source Shortest Path
# algorithm.

from PrioQueue import PrioQueue

def search(startNodes, deriveNodes, matchTarget):
   """
   startNodes  = [ Node, ... ]
      List of starting nodes
   deriveNodes = Node, Function(Node, Cost)
      A function that, when given a node, returns an iterator that
      produces a list of tuples of the adjacent nodes along with the
      derivation cost.
   matchTarget = Node -> Object
      Determines whether a given node is a target node.  Returns
      non-None when the target node matches.  This non-None value
      will be the third element of this function's return value.
   'Node' objects must be hashable.
   """

   # visited = { node => cost, ... }
   visited = {}

   # fringe = { node => cost, ... }
   fringe = PrioQueue()

   # Initialize all premises to be 'zero-distance' nodes.
   for node in startNodes:
      fringe[node] = 0

   while (len(fringe) > 0):
      # Get the lowest cost node
      (node, nodeCost) = fringe.pop()

      # See if it's one of the targets.  If so, return
      matchingTarget = matchTarget(node)
      if (matchingTarget != None):
         return (node, nodeCost, matchingTarget)

      # Add the new node to our confirmed visited
      visited[node] = nodeCost

      # Derive more fringe nodes from it by applying the rules
      for (newNode, derivationCost) in deriveNodes(node):
         if (visited.has_key(newNode)): continue # Skip duplicates
         newNodeCost = nodeCost + derivationCost
         fringe[newNode] = newNodeCost

   # No match found
   return (None, None, None)