--- nfo/python/scripts/sixdegrees/boostgraph.py	2008/02/21 04:46:47	1.3
+++ nfo/python/scripts/sixdegrees/boostgraph.py	2008/02/21 11:29:07	1.4
@@ -1,6 +1,6 @@
 #!/usr/bin/env python
 
-# $Id: boostgraph.py,v 1.3 2008/02/21 04:46:47 joko Exp $
+# $Id: boostgraph.py,v 1.4 2008/02/21 11:29:07 joko Exp $
 
 # (c) 2008 Andreas Motl <andreas.motl@ilo.de>
 # (c) 2008 Sebastian Utz <su@rotamente.com>
@@ -63,12 +63,15 @@
 class tree_edges_dfs_visitor(bgl.dfs_visitor):
 #class tree_edges_bfs_visitor(bgl.bfs_visitor):
   
-  def __init__(self, maxdepth, name_map, color_map):
+  def __init__(self, startVertex, endVertex, maxdepth, color_map):
     
-    print dir(self)
+    #print dir(self)
     
     #bgl.dfs_visitor.__init__(self)
-    self.name_map = name_map
+    #self.name_map = name_map
+    
+    self.startVertex = startVertex
+    self.endVertex = endVertex
     
     # for recognizing path switches
     self.state = True
@@ -87,10 +90,19 @@
     self.level = 0
     
 
+  #def back_edge(self, e, g):
+  #  self.tree_edge(e, g, 'back_edge')
+
+  #def forward_or_cross_edge(self, e, g):
+  #  self.tree_edge(e, g, 'forward_or_cross_edge')
+
+  #def tree_edge(self, e, g):
+  #  self.tree_edge(e, g, 'examine_edge')
+
   def examine_edge(self, e, g):
-    self.tree_edge2(e, g, 'examine_edge')
+    self._touch_edge(e, g, 'examine_edge')
 
-  def tree_edge2(self, e, g, label='tree_edge'):
+  def _touch_edge(self, e, g, label=''):
     
     (u, v) = (g.source(e), g.target(e))
     
@@ -106,25 +118,39 @@
         end_vertex = g.target(child_edge)
         #self.color_map[end_vertex] = bgl.Color(bgl.Color.gray)
     """
-      
+    
+    name_map = g.vertex_properties['node_id']
     
     if label:
       print "%s:" % label,
-    print "Tree edge ",
-    print self.name_map[u],
+    print "edge ",
+    print name_map[u],
     print " -> ",
-    print self.name_map[v]
-    sys.stdout.flush()
-    self.state = True
-    self.current_path.append(e)
-    #return False
+    print name_map[v]
+    
+    #self.state = True
+    
+    if u == self.startVertex:
+      print "starting"
+      self.current_path = []
 
+    # skip circular references
+    if v != self.startVertex:
+      self.current_path.append(e)
+
+    if v == self.endVertex and self.current_path:
+      print "found:"
+      print self.current_path
+      self.paths.append(self.current_path)
+      self.current_path = []
+    
+
+  """
   def start_vertex(self, v, g):
     self._seperator('start_vertex')
     #pass
     #print 'sssss'
 
-
   def discover_vertex(self, v, g):
     #print '>>>'
     self._seperator('discover_vertex')
@@ -144,6 +170,7 @@
     self.current_path = []
     self.depth = 0
     self._seperator('finish_vertex')
+  """
 
   def _seperator(self, label = 'unknown'):
     if 1 or self.state:
@@ -261,6 +288,15 @@
   
   print ' -> '.join(track_ids)
 
+def dump_edges(g, edges):
+  name_map = g.vertex_properties['node_id']
+  for e in edges:
+    (u, v) = (g.source(e), g.target(e))
+    print "edge ",
+    print name_map[u],
+    print " -> ",
+    print name_map[v]
+
 def find_path_solutions(source, target, graph, paths):
   
   print
@@ -304,6 +340,7 @@
   #mst_edges = bgl.kruskal_minimum_spanning_tree(graph, weight)
   #bgl.depth_first_search(graph, root_vertex = None, visitor = None, color_map = None)
   
+  """
   for root in graph.vertices:
     print
     print '=' * 42
@@ -316,6 +353,7 @@
     #bgl.breadth_first_search(graph, root_vertex = root, visitor = visitor, color_map = None)
     #find_path_solutions(index['1'], index['4'], graph, visitor.paths)
   #sys.exit(0)
+  """
 
   startIndex = random.choice(index.keys())
   endIndex = random.choice(index.keys())
@@ -329,10 +367,13 @@
 
   def doCompute():
     cmap = graph.vertex_property_map('color')
-    visitor = tree_edges_dfs_visitor(MAX_SEARCH_DEPTH, graph.vertex_properties['node_id'], cmap)
+    visitor = tree_edges_dfs_visitor(startVertex, endVertex, MAX_SEARCH_DEPTH, cmap)
     bgl.depth_first_search(graph, root_vertex = startVertex, visitor = visitor, color_map = None)
     #bgl.depth_first_visit(graph, root_vertex = startVertex, visitor = visitor, color_map = cmap)
-    find_path_solutions(startVertex, endVertex, graph, visitor.paths)
+    #find_path_solutions(startVertex, endVertex, graph, visitor.paths)
+    for path in visitor.paths:
+      print '-' * 21
+      dump_edges(graph, path)
 
   if ENABLE_PROFILING:
     global paths