--- nfo/python/scripts/sixdegrees/boostgraph.py	2008/02/08 09:05:02	1.1
+++ nfo/python/scripts/sixdegrees/boostgraph.py	2008/02/21 01:54:28	1.2
@@ -1,6 +1,6 @@
 #!/usr/bin/env python
 
-# $Id: boostgraph.py,v 1.1 2008/02/08 09:05:02 joko Exp $
+# $Id: boostgraph.py,v 1.2 2008/02/21 01:54:28 joko Exp $
 
 # (c) 2008 Andreas Motl <andreas.motl@ilo.de>
 
@@ -23,9 +23,15 @@
 #
 # BGL-Python Homepage: http://osl.iu.edu/~dgregor/bgl-python/
 #
-# Documentation:
-#  - http://osl.iu.edu/~dgregor/bgl-python/reference/boost.graph.html
+# Documentation (Boost):
+#  - http://www.boost.org/libs/graph/doc/graph_theory_review.html
 #  - http://www.boost.org/libs/graph/doc/depth_first_search.html
+#  - http://www.boost.org/boost/graph/depth_first_search.hpp
+#  - http://www.boost.org/libs/graph/doc/DFSVisitor.html
+#  - http://www.boost.org/libs/graph/example/dfs-example.cpp
+#
+# Documentation (BGL-Python):
+#  - http://osl.iu.edu/~dgregor/bgl-python/reference/boost.graph.html
 #
 # Subversion-Repository: https://svn.osl.iu.edu/svn/projects_viz/bgl-python/
 
@@ -45,7 +51,13 @@
   def __init__(self, name_map):
     #bgl.dfs_visitor.__init__(self)
     self.name_map = name_map
+    
+    # for recognizing path switches
     self.state = True
+    
+    # for tracking paths
+    self.paths = []
+    self.current_path = []
 
   def tree_edge(self, e, g):
     (u, v) = (g.source(e), g.target(e))
@@ -54,27 +66,37 @@
     print " -> ",
     print self.name_map[v]
     self.state = True
+    self.current_path.append(e)
+    #return False
 
   def start_vertex(self, v, g):
+    #self._seperator()
+    pass
     #print 'sssss'
-    self._seperator()
 
   def initialize_vertex(self, v, g):
     #print '>>>'
-    self._seperator()
+    self._seperator('initialize_vertex')
 
   def finish_vertex(self, v, g):
     #print '<<<'
-    self._seperator()
+    if self.current_path:
+      self.paths.append(self.current_path)
+    self.current_path = []
+    self._seperator('finish_vertex')
 
-  def _seperator(self):
+  def _seperator(self, label = 'unknown'):
     if self.state:
-      print '-' * 21
+      print '-' * 21, label
       self.state = False
 
+
 def build_fixed_graph():
+  
   graph = bgl.Graph()
+  index = {}
 
+  # doesn't this work? see http://www.nabble.com/-Graph--Getting-PageRank-to-work-in-BGL-Python-td14207115.html
   #graph.add_vertex_property_map(name='my_name', type='float')
 
   # 'write_graphviz' requires property 'node_id' on vertices
@@ -85,15 +107,19 @@
 
   v1 = graph.add_vertex()
   vmap[v1] = '1'
+  index['1'] = v1
 
   v2 = graph.add_vertex()
   vmap[v2] = '2'
+  index['2'] = v2
 
   v3 = graph.add_vertex()
   vmap[v3] = '3'
+  index['3'] = v3
 
   v4 = graph.add_vertex()
   vmap[v4] = '4'
+  index['4'] = v4
 
   e1 = graph.add_edge(v1, v2)
   e2 = graph.add_edge(v1, v3)
@@ -111,15 +137,31 @@
 
   graph.write_graphviz('friends.dot')
   
-  return graph
+  return (graph, index)
 
 
 
+def find_path_solutions(source, target, graph, paths):
+  
+  print
+  print "=" * 42
+  print "find_path_solutions"
+  print "=" * 42
+
+  #print visitor.paths
+  #(u, v) = (g.source(e), g.target(e))
+  for path in paths:
+    startVertex = graph.source(path[0])
+    endVertex = graph.target(path[-1])
+    if source == startVertex and target == endVertex:
+      print "found"
+
+
 def main():
   
   # Load a graph from the GraphViz file 'mst.dot'
   #graph = bgl.Graph.read_graphviz('mst.dot')
-  graph = build_fixed_graph()
+  (graph, index) = build_fixed_graph()
 
   # Compute all paths rooted from each vertex
   #mst_edges = bgl.kruskal_minimum_spanning_tree(graph, weight)
@@ -130,7 +172,8 @@
     print 'Paths originating from node %s' % graph.vertex_properties['node_id'][root]
     visitor = tree_edges_dfs_visitor(graph.vertex_properties['node_id'])
     bgl.depth_first_search(graph, root_vertex = root, visitor = visitor, color_map = None)
-  
+    
+    find_path_solutions(index['4'], index['2'], graph, visitor.paths)
   
   # STOP HERE
   sys.exit(0)