Source Code for Module gmisclib.nbest

  1  """Beam search through a graph.""" 
  2   
  3 -class node: 
  4          __doc__ = """This is a node of a graph, it includes links to other nodes.""" 
  5   
  6 -        def __init__(self, cost=0.0, label=None, terminal=0, comment=None): 
  7                  """Create a node, with a specified cost (used in the beam search), 
  8                  and a label (arbitrary information). 
  9                  Terminal nodes are marked, and terminate the search.""" 
 10   
 11                  self.terminal = terminal 
 12                  self.out = [] 
 13                  self.cost = cost 
 14                  self.label = label 
 15                  self.comment = comment 
 16   
 17 -        def add(self, nextnode, cost=0.0, label=None): 
 18                  """Add a link from self to nextnode. 
 19                  Links can have a cost and label, too.""" 
 20                  self.out.append( (nextnode, cost, label) ) 
 21                  return nextnode 
 22   
 23   
 24 -        def __str__(self): 
 25                  return "<node term=%d label=%s nout=%d cost=%f>" % (self.terminal, str(self.label), 
 26                                                                          len(self.out), self.cost) 
 27   
 28          __repr__ = __str__ 
 29           
 30   
 31   
 32   
 33 -class _l_list: 
 34          __doc__ = """Linked list.""" 
 35   
 36 -        def __init__(self, contents, link): 
 37                  self.link = link 
 38                  self.contents = contents 
 39   
 40 -        def walk(self): 
 41                  o = [self.contents] 
 42                  while self.link is not None: 
 43                          self = self.link 
 44                          o.append(self.contents) 
 45                  return o 
 46   
 47 -        def rwalk(self): 
 48                  o = self.walk() 
 49                  o.reverse() 
 50                  return o 
 51   
 52   
 53   
 54 -def go(graph, nbeam, cbeam): 
 55          """Search the graph for the lowest cost routes. 
 56          Returns [ (cost, route), ...] where cost is the cost of a route, 
 57          and route is [node, node, node, ...] the list of nodes on the route. 
 58          Routes are sorted in order of increasing cost. 
 59          """ 
 60   
 61          assert isinstance(graph, node), "Non-node starts graph: %s" % str(graph) 
 62          # current = [ (0.0, graph, [graph]) ] 
 63          current = [ (0.0, graph, _l_list(graph, None)) ] 
 64          terminate = [ ] 
 65   
 66          while 1: 
 67                  nextstep = [] 
 68                  for (cost, anode, path) in current: 
 69                          assert isinstance(anode, node), "Non-node in graph: %s" % str(anode) 
 70                          for (nnode, c, ll) in anode.out: 
 71                                  # print anode, "->", nnode 
 72                                  newcost = cost + nnode.cost + c 
 73                                  newpath = _l_list(nnode, path) 
 74                                  # newpath = path + [nnode] 
 75                                  if nnode.terminal: 
 76                                          terminate.append( ( newcost, newpath) ) 
 77                                  else: 
 78                                          nextstep.append( (newcost, nnode, newpath) ) 
 79                  if len(nextstep) == 0: 
 80                          break 
 81                  nextstep.sort() 
 82                  if len(nextstep) > nbeam: 
 83                          nextstep = nextstep[:nbeam] 
 84                  costlimit = nextstep[0][0] + cbeam 
 85                  i = 0 
 86                  while i < len(nextstep): 
 87                          if nextstep[i][0] > costlimit: 
 88                                  break 
 89                          i += 1 
 90                  current = nextstep[:i] 
 91          terminate.sort() 
 92          if len(terminate) > nbeam: 
 93                  terminate = terminate[:nbeam] 
 94          costlimit = terminate[0][0] + cbeam 
 95          o = [] 
 96          for (cost, path) in terminate: 
 97                  if cost > costlimit: 
 98                          break 
 99                  o.append( (cost, path.rwalk() ) ) 
100          return o 
101   
102   
103   
104 -def test(): 
105          graph = node(0.0, "A") 
106          graph.add(node(0.0, "B")).add(node(0.1, "C")).add(node(0.2, "D")).add(node(-0.3, terminal=1, label="E")) 
107          graph.add(node(1.0, "a")).add(node(1, "b")).add(node(2, terminal=1, label="c")) 
108          graph.add(node(0.0, label="q", terminal=1), 1.0, label="edge") 
109          print go(graph, 100, 1000.0) 
110   
111   
112  if __name__ == '__main__': 
113          test() 
114