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

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

Parent Directory Parent Directory | Revision Log Revision Log | View Patch Patch

revision 1.3 by joko, Thu Feb 21 04:46:47 2008 UTC revision 1.4 by joko, Thu Feb 21 11:29:07 2008 UTC
# Line 63  import boost.graph as bgl Line 63  import boost.graph as bgl
63  class tree_edges_dfs_visitor(bgl.dfs_visitor):  class tree_edges_dfs_visitor(bgl.dfs_visitor):
64  #class tree_edges_bfs_visitor(bgl.bfs_visitor):  #class tree_edges_bfs_visitor(bgl.bfs_visitor):
65        
66    def __init__(self, maxdepth, name_map, color_map):    def __init__(self, startVertex, endVertex, maxdepth, color_map):
67            
68      print dir(self)      #print dir(self)
69            
70      #bgl.dfs_visitor.__init__(self)      #bgl.dfs_visitor.__init__(self)
71      self.name_map = name_map      #self.name_map = name_map
72        
73        self.startVertex = startVertex
74        self.endVertex = endVertex
75            
76      # for recognizing path switches      # for recognizing path switches
77      self.state = True      self.state = True
# Line 87  class tree_edges_dfs_visitor(bgl.dfs_vis Line 90  class tree_edges_dfs_visitor(bgl.dfs_vis
90      self.level = 0      self.level = 0
91            
92    
93      #def back_edge(self, e, g):
94      #  self.tree_edge(e, g, 'back_edge')
95    
96      #def forward_or_cross_edge(self, e, g):
97      #  self.tree_edge(e, g, 'forward_or_cross_edge')
98    
99      #def tree_edge(self, e, g):
100      #  self.tree_edge(e, g, 'examine_edge')
101    
102    def examine_edge(self, e, g):    def examine_edge(self, e, g):
103      self.tree_edge2(e, g, 'examine_edge')      self._touch_edge(e, g, 'examine_edge')
104    
105    def tree_edge2(self, e, g, label='tree_edge'):    def _touch_edge(self, e, g, label=''):
106            
107      (u, v) = (g.source(e), g.target(e))      (u, v) = (g.source(e), g.target(e))
108            
# Line 106  class tree_edges_dfs_visitor(bgl.dfs_vis Line 118  class tree_edges_dfs_visitor(bgl.dfs_vis
118          end_vertex = g.target(child_edge)          end_vertex = g.target(child_edge)
119          #self.color_map[end_vertex] = bgl.Color(bgl.Color.gray)          #self.color_map[end_vertex] = bgl.Color(bgl.Color.gray)
120      """      """
121              
122        name_map = g.vertex_properties['node_id']
123            
124      if label:      if label:
125        print "%s:" % label,        print "%s:" % label,
126      print "Tree edge ",      print "edge ",
127      print self.name_map[u],      print name_map[u],
128      print " -> ",      print " -> ",
129      print self.name_map[v]      print name_map[v]
130      sys.stdout.flush()      
131      self.state = True      #self.state = True
132      self.current_path.append(e)      
133      #return False      if u == self.startVertex:
134          print "starting"
135          self.current_path = []
136    
137        # skip circular references
138        if v != self.startVertex:
139          self.current_path.append(e)
140    
141        if v == self.endVertex and self.current_path:
142          print "found:"
143          print self.current_path
144          self.paths.append(self.current_path)
145          self.current_path = []
146        
147    
148      """
149    def start_vertex(self, v, g):    def start_vertex(self, v, g):
150      self._seperator('start_vertex')      self._seperator('start_vertex')
151      #pass      #pass
152      #print 'sssss'      #print 'sssss'
153    
   
154    def discover_vertex(self, v, g):    def discover_vertex(self, v, g):
155      #print '>>>'      #print '>>>'
156      self._seperator('discover_vertex')      self._seperator('discover_vertex')
# Line 144  class tree_edges_dfs_visitor(bgl.dfs_vis Line 170  class tree_edges_dfs_visitor(bgl.dfs_vis
170      self.current_path = []      self.current_path = []
171      self.depth = 0      self.depth = 0
172      self._seperator('finish_vertex')      self._seperator('finish_vertex')
173      """
174    
175    def _seperator(self, label = 'unknown'):    def _seperator(self, label = 'unknown'):
176      if 1 or self.state:      if 1 or self.state:
# Line 261  def dump_track(graph, track): Line 288  def dump_track(graph, track):
288        
289    print ' -> '.join(track_ids)    print ' -> '.join(track_ids)
290    
291    def dump_edges(g, edges):
292      name_map = g.vertex_properties['node_id']
293      for e in edges:
294        (u, v) = (g.source(e), g.target(e))
295        print "edge ",
296        print name_map[u],
297        print " -> ",
298        print name_map[v]
299    
300  def find_path_solutions(source, target, graph, paths):  def find_path_solutions(source, target, graph, paths):
301        
302    print    print
# Line 304  def main(): Line 340  def main():
340    #mst_edges = bgl.kruskal_minimum_spanning_tree(graph, weight)    #mst_edges = bgl.kruskal_minimum_spanning_tree(graph, weight)
341    #bgl.depth_first_search(graph, root_vertex = None, visitor = None, color_map = None)    #bgl.depth_first_search(graph, root_vertex = None, visitor = None, color_map = None)
342        
343      """
344    for root in graph.vertices:    for root in graph.vertices:
345      print      print
346      print '=' * 42      print '=' * 42
# Line 316  def main(): Line 353  def main():
353      #bgl.breadth_first_search(graph, root_vertex = root, visitor = visitor, color_map = None)      #bgl.breadth_first_search(graph, root_vertex = root, visitor = visitor, color_map = None)
354      #find_path_solutions(index['1'], index['4'], graph, visitor.paths)      #find_path_solutions(index['1'], index['4'], graph, visitor.paths)
355    #sys.exit(0)    #sys.exit(0)
356      """
357    
358    startIndex = random.choice(index.keys())    startIndex = random.choice(index.keys())
359    endIndex = random.choice(index.keys())    endIndex = random.choice(index.keys())
# Line 329  def main(): Line 367  def main():
367    
368    def doCompute():    def doCompute():
369      cmap = graph.vertex_property_map('color')      cmap = graph.vertex_property_map('color')
370      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)
371      bgl.depth_first_search(graph, root_vertex = startVertex, visitor = visitor, color_map = None)      bgl.depth_first_search(graph, root_vertex = startVertex, visitor = visitor, color_map = None)
372      #bgl.depth_first_visit(graph, root_vertex = startVertex, visitor = visitor, color_map = cmap)      #bgl.depth_first_visit(graph, root_vertex = startVertex, visitor = visitor, color_map = cmap)
373      find_path_solutions(startVertex, endVertex, graph, visitor.paths)      #find_path_solutions(startVertex, endVertex, graph, visitor.paths)
374        for path in visitor.paths:
375          print '-' * 21
376          dump_edges(graph, path)
377    
378    if ENABLE_PROFILING:    if ENABLE_PROFILING:
379      global paths      global paths
Legend:
Removed from v.1.3  
changed lines
  Added in v.1.4
MailToCvsAdmin">MailToCvsAdmin
 ViewVC Help
Powered by ViewVC 1.1.26 RSS 2.0 feed