/[cvs]/nfo/python/scripts/sixdegrees/boostgraph.py

Diff of /nfo/python/scripts/sixdegrees/boostgraph.py

Parent Directory | Revision Log | View Patch Patch

-revision 1.1 by joko,
Fri Feb  8 09:05:02 2008 UTC
+revision 1.6 by joko,
Tue Feb 26 10:11:13 2008 UTC
 Line 3
  # $Id$
  # (c) 2008 Andreas Motl <andreas.motl@ilo.de>
+ # (c) 2008 Sebastian Utz <su@rotamente.com>
  # This program is free software: you can redistribute it and/or modify
  # it under the terms of the GNU Affero General Public License as published by
-Line 23
+Line 24
  #
  # BGL-Python Homepage: http://osl.iu.edu/~dgregor/bgl-python/
  #
- # Documentation:
+ # Documentation (Boost):
- #  - http://osl.iu.edu/~dgregor/bgl-python/reference/boost.graph.html
+ #  - 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/
+ RANDOM_MAX_NODES = 10
+ RANDOM_MAX_CHILDREN_PER_NODE = 10
+ MAX_SEARCH_DEPTH = 50
+ DEBUG = True
+ DEBUG = False
+ ENABLE_PROFILING = False
+ if ENABLE_PROFILING:
+   import profile
+   from profile import Profile
  import sys, os
+ import random
  sys.path.append('bgl_python')
  os.environ['PATH'] += ';' + './bgl_python'
-Line 40 
 import boost.graph as bgl
+Line 63 
 import boost.graph as bgl
  # from http://www.boost.org/libs/graph/doc/DFSVisitor.html
- class tree_edges_dfs_visitor(bgl.dfs_visitor):
+ #class tree_edges_dfs_visitor(bgl.dfs_visitor):
+ class dfs_visitor_debug(bgl.dfs_visitor):
+ #class tree_edges_bfs_visitor(bgl.bfs_visitor):
-   def __init__(self, name_map):
+   def __init__(self, startVertex, endVertex, maxdepth, color_map):
+     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
+     # for tracking paths
+     self.paths = []
+     self.current_path = []
+     # for limiting search depth
+     """
+     self.color_map = color_map
+     self.maxdepth = maxdepth
+     self.depth = 0
+     """
+     self.level = 0
+   def back_edge(self, e, g):
+     self._touch_edge(e, g, 'back_edge')
+   def forward_or_cross_edge(self, e, g):
+     self._touch_edge(e, g, 'forward_or_cross_edge')
    def tree_edge(self, e, g):
+     self._touch_edge(e, g, 'tree_edge')
+   def examine_edge(self, e, g):
+     self._touch_edge(e, g, 'examine_edge')
+   def _touch_edge(self, e, g, label=''):
      (u, v) = (g.source(e), g.target(e))
-     print "Tree edge ",
-     print self.name_map[u],
+     # increase current search depth (level)
+     """
+     self.depth += 1
+     # check if maximum depth reached
+     if self.depth == self.maxdepth:
+       # color all succeeding vertices to black (mark as "already visited")
+       # BUG!!! marks too many nodes
+       for child_edge in g.out_edges(v):
+         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:\t" % label,
+     #print "edge ",
+     print name_map[u],
      print " -> ",
-     print self.name_map[v]
+     print name_map[v]
-     self.state = True
+     #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 _touch_vertex(self, v, g, label=''):
+     name_map = g.vertex_properties['node_id']
+     id = name_map[v]
+     print '%s:\t%s' % (label, id)
    def start_vertex(self, v, g):
+     self._touch_vertex(v, g, 'start_vertex')
+   def discover_vertex(self, v, g):
+     self._touch_vertex(v, g, 'discover_vertex')
+   def initialize_vertex(self, v, g):
+     self._touch_vertex(v, g, 'initialize_vertex')
+   def examine_vertex(self, v, g):
+     self._touch_vertex(v, g, 'examine_vertex')
+   def finish_vertex(self, v, g):
+     self._touch_vertex(v, g, 'finish_vertex')
+   """
+   def start_vertex(self, v, g):
+     self._seperator('start_vertex')
+     #pass
      #print 'sssss'
-     self._seperator()
+   def discover_vertex(self, v, g):
+     #print '>>>'
+     self._seperator('discover_vertex')
+     #pass
    def initialize_vertex(self, v, g):
      #print '>>>'
-     self._seperator()
+     self._seperator('initialize_vertex')
+   def examine_vertex(self, v, g):
+     self._seperator('examine_vertex')
    def finish_vertex(self, v, g):
      #print '<<<'
-     self._seperator()
+     if self.current_path:
+       self.paths.append(self.current_path)
+     self.current_path = []
+     self.depth = 0
+     self._seperator('finish_vertex')
+   """
-   def _seperator(self):
+   def _seperator(self, label = 'unknown'):
-     if self.state:
+     if 1 or self.state:
-       print '-' * 21
+       print '-' * 21, label
        self.state = False
+ class tree_edges_dfs_visitor(bgl.dfs_visitor):
+   def __init__(self, startVertex, endVertex, maxdepth, color_map):
+     #print dir(self)
+     #bgl.dfs_visitor.__init__(self)
+     #self.name_map = name_map
+     self.startVertex = startVertex
+     self.endVertex = endVertex
+     # for recognizing path switches
+     self.state = True
+     # for tracking paths
+     self.paths = []
+     self.current_path = []
+     # for limiting search depth
+     """
+     self.color_map = color_map
+     self.maxdepth = maxdepth
+     self.depth = 0
+     """
+     self.level = 0
+   def tree_edge(self, e, g):
+     self._touch_edge(e, g, 'tree_edge')
+   def forward_or_cross_edge(self, e, g):
+     #self._touch_edge(e, g, 'forward_or_cross_edge')
+     self.find_new_variations_from_source(e, g)
+     self.find_new_variations_to_target(e, g)
+   def find_new_variations_from_source(self, e, g):
+     # find additional solutions as parts of already established ones (e.g. shortcuts)
+     localEndVertex = g.target(e)
+     path_additional = []
+     for path in self.paths:
+       found = False
+       for edge in path:
+         if found:
+           path_additional.append(edge)
+         else:
+           if g.source(edge) == localEndVertex:
+             #print "found2"
+             found = True
+             path_additional.append(e)
+             path_additional.append(edge)
+     #print "find_new_variations_from_source:", path_additional
+     if path_additional:
+       self.paths.append(path_additional)
+   def find_new_variations_to_target(self, e, g):
+     # find additional solutions as parts of already established ones (e.g. shortcuts)
+     localStartVertex = g.source(e)
+     localEndVertex = g.target(e)
+     #return
+     #if not (self.endVertex == localEndVertex and self.startVertex != localStartVertex):
+     if not (self.endVertex == localEndVertex):
+       return
+     # find "direct" solution (start- and end-vertices are directly connected)
+     if self.startVertex == localStartVertex:
+       self.paths.append([e])
+       return
+     #print "check"
+     path_additional = []
+     for path_iter in self.paths:
+       found = False
+       path = list(path_iter)
+       path.reverse()
+       for edge in path:
+         if found:
+           path_additional.insert(0, edge)
+         else:
+           if g.target(edge) == localStartVertex:
+             #print "found2"
+             found = True
+             path_additional.append(e)
+             path_additional.insert(0, edge)
+     #print "find_new_variations_to_target:", path_additional
+     if path_additional:
+       self.paths.append(path_additional)
+   def _touch_edge(self, e, g, label=''):
+     (u, v) = (g.source(e), g.target(e))
+     # increase current search depth (level)
+     """
+     self.depth += 1
+     # check if maximum depth reached
+     if self.depth == self.maxdepth:
+       # color all succeeding vertices to black (mark as "already visited")
+       # BUG!!! marks too many nodes
+       for child_edge in g.out_edges(v):
+         end_vertex = g.target(child_edge)
+         #self.color_map[end_vertex] = bgl.Color(bgl.Color.gray)
+     """
+     name_map = g.vertex_properties['node_id']
+     if DEBUG:
+       if label:
+         print "%s:\t" % label,
+       #print "edge ",
+       print name_map[u],
+       print " -> ",
+       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)
+     # finish current path if target found
+     if v == self.endVertex and self.current_path:
+       #print "found:"
+       #print self.current_path
+       self.paths.append(self.current_path)
+       self.current_path = []
  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
-Line 85 
 def build_fixed_graph():
+Line 358 
 def build_fixed_graph():
    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)
    e3 = graph.add_edge(v3, v4)
+   e4 = graph.add_edge(v1, v4)
+   e5 = graph.add_edge(v2, v3)
+   e6 = graph.add_edge(v2, v4)
    """
    for vertex in graph.vertices:
-Line 111 
 def build_fixed_graph():
+Line 392 
 def build_fixed_graph():
    graph.write_graphviz('friends.dot')
-   return graph
+   return (graph, index)
+ def build_random_graph():
+   graph = bgl.Graph()
+   index = {}
+   vmap = graph.vertex_property_map('string')
+   graph.vertex_properties['node_id'] = vmap
+   count = 0
+   for parent_id in range(1, RANDOM_MAX_NODES + 1):
+     count += 1
+     if count % 100 == 0:
+       sys.stderr.write('.')
+     parent_id_str = str(parent_id)
+     v1New = False
+     if not index.has_key(parent_id_str):
+       #print "adding v1:", parent_id_str
+       myVertex1 = graph.add_vertex()
+       vmap[myVertex1] = parent_id_str
+       index[parent_id_str] = myVertex1
+       v1New = True
+   count = 0
+   #for j in range(1, random.randint(1, RANDOM_MAX_CHILDREN_PER_NODE)):
+   for j in range(1, RANDOM_MAX_CHILDREN_PER_NODE):
+     count += 1
+     if count % 100 == 0:
+       sys.stderr.write('.')
+     parent_id_str = random.choice(index.keys())
+     child_id_str = parent_id_str
+     while child_id_str == parent_id_str:
+       child_id_str = random.choice(index.keys())
+       #print child_id_str
+       myVertex1 = index[parent_id_str]
+       myVertex2 = index[child_id_str]
+       graph.add_edge(myVertex1, myVertex2)
+   sys.stderr.write("\n")
+   return (graph, index)
+ def dump_track(graph, track):
+   track_ids = []
+   for node in track:
+     node_id = graph.vertex_properties['node_id'][node]
+     track_ids.append(node_id)
+   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
+   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])
+     track = []
+     track.append(startVertex)
+     for edge in path:
+       endVertex = graph.target(edge)
+       track.append(endVertex)
+       if source == startVertex and target == endVertex:
+         #print "found:", track
+         dump_track(graph, track)
+ def dump_graph(graph):
+   for edge in graph.edges:
+     (u, v) = (graph.source(edge), graph.target(edge))
+     startIndex = graph.vertex_properties['node_id'][u]
+     endIndex = graph.vertex_properties['node_id'][v]
+     print "%s -> %s" % (startIndex, endIndex)
+ def dump_edges_vertices(graph, edge_list):
+   startVertex = graph.source(edge_list[0])
+   track = []
+   track.append(startVertex)
+   for edge in edge_list:
+     endVertex = graph.target(edge)
+     track.append(endVertex)
+   dump_track(graph, track)
+ def print_path_solutions(graph, paths):
+   for path in paths:
+     if DEBUG:
+       print '-' * 21
+       dump_edges(graph, path)
+     dump_edges_vertices(graph, path)
-Line 119 
 def main():
+Line 514 
 def main():
    # Load a graph from the GraphViz file 'mst.dot'
    #graph = bgl.Graph.read_graphviz('mst.dot')
-   graph = build_fixed_graph()
+   # 1. fixed graph with fixed required solution
+   (graph, index) = build_fixed_graph()
+   startIndex = '1'
+   endIndex = '4'
+   # 2. random graph with according solution
+   #(graph, index) = build_random_graph()
+   #startIndex = random.choice(index.keys())
+   #endIndex = random.choice(index.keys())
+   print '-' * 42
+   print "complete graph:"
+   dump_graph(graph)
+   print '-' * 42
    # Compute all paths rooted from each vertex
    #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
      print 'Paths originating from node %s' % graph.vertex_properties['node_id'][root]
-     visitor = tree_edges_dfs_visitor(graph.vertex_properties['node_id'])
+     #cmap = graph.vertex_property_map('color')
+     cmap = None
+     visitor = tree_edges_dfs_visitor(3, graph.vertex_properties['node_id'], cmap)
+     #visitor = tree_edges_bfs_visitor(3, graph.vertex_properties['node_id'], cmap)
      bgl.depth_first_search(graph, root_vertex = root, visitor = visitor, color_map = None)
+     #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)
+   """
+   print "Trying to find solution for: %s -> %s" % (startIndex, endIndex)
+   startVertex = index[startIndex]
+   endVertex = index[endIndex]
+   def doCompute():
+     cmap = graph.vertex_property_map('color')
+     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)
+     print '-' * 42
+     print "solution(s):"
+     print_path_solutions(graph, visitor.paths)
+   if ENABLE_PROFILING:
+     global paths
+     paths = []
+     p = Profile()
+     p.runcall(doCompute)
+     p.print_stats()
+   else:
+     paths = doCompute()
    # STOP HERE
    sys.exit(0)

 Legend:



Removed from v.1.1
 


changed lines


 
Added in v.1.6
 Legend:



Removed from v.1.1
 


changed lines


 
Added in v.1.6
-Removed from v.1.1
+Added in v.1.6

MailToCvsAdmin">MailToCvsAdmin	ViewVC Help
Powered by ViewVC 1.1.26