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

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

Parent Directory | Revision Log | View Patch Patch

-revision 1.5 by joko,
Fri Feb 22 13:34:26 2008 UTC
+revision 1.6 by joko,
Tue Feb 26 10:11:13 2008 UTC
 Line 38
  RANDOM_MAX_NODES = 10
- RANDOM_MAX_CHILDREN_PER_NODE = 500
+ RANDOM_MAX_CHILDREN_PER_NODE = 10
  MAX_SEARCH_DEPTH = 50
+ DEBUG = True
+ DEBUG = False
  ENABLE_PROFILING = False
  if ENABLE_PROFILING:
-Line 60 
 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, startVertex, endVertex, maxdepth, color_map):
-Line 200 
 class tree_edges_dfs_visitor(bgl.dfs_vis
+Line 204 
 class tree_edges_dfs_visitor(bgl.dfs_vis
        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()
-Line 236 
 def build_fixed_graph():
+Line 378 
 def build_fixed_graph():
    e4 = graph.add_edge(v1, v4)
    e5 = graph.add_edge(v2, v3)
-   #e6 = graph.add_edge(v2, v4)
+   e6 = graph.add_edge(v2, v4)
    """
    for vertex in graph.vertices:
-Line 347 
 def dump_graph(graph):
+Line 489 
 def dump_graph(graph):
      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)
  def main():
    # Load a graph from the GraphViz file 'mst.dot'
    #graph = bgl.Graph.read_graphviz('mst.dot')
+   # 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())
-   #dump_graph(graph)
+   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)
-Line 377 
 def main():
+Line 549 
 def main():
    #sys.exit(0)
    """
-   startIndex = random.choice(index.keys())
-   endIndex = random.choice(index.keys())
-   startIndex = '1'
-   endIndex = '4'
    print "Trying to find solution for: %s -> %s" % (startIndex, endIndex)
    startVertex = index[startIndex]
-Line 393 
 def main():
+Line 560 
 def main():
      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)
-     for path in visitor.paths:
+     print '-' * 42
-       print '-' * 21
+     print "solution(s):"
-       dump_edges(graph, path)
+     print_path_solutions(graph, visitor.paths)
    if ENABLE_PROFILING:
      global paths

 Legend:



Removed from v.1.5
 


changed lines


 
Added in v.1.6
 Legend:



Removed from v.1.5
 


changed lines


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

MailToCvsAdmin">MailToCvsAdmin	ViewVC Help
Powered by ViewVC 1.1.26