/[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.5 by joko, Fri Feb 22 13:34:26 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._touch_edge(e, g, 'back_edge')
95    
96      def forward_or_cross_edge(self, e, g):
97        self._touch_edge(e, g, 'forward_or_cross_edge')
98    
99      def tree_edge(self, e, g):
100        self._touch_edge(e, g, 'tree_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:\t" % 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      def _touch_vertex(self, v, g, label=''):
149        name_map = g.vertex_properties['node_id']
150        id = name_map[v]
151        print '%s:\t%s' % (label, id)
152    
153    
154      def start_vertex(self, v, g):
155        self._touch_vertex(v, g, 'start_vertex')
156    
157      def discover_vertex(self, v, g):
158        self._touch_vertex(v, g, 'discover_vertex')
159    
160      def initialize_vertex(self, v, g):
161        self._touch_vertex(v, g, 'initialize_vertex')
162    
163      def examine_vertex(self, v, g):
164        self._touch_vertex(v, g, 'examine_vertex')
165    
166      def finish_vertex(self, v, g):
167        self._touch_vertex(v, g, 'finish_vertex')
168    
169    
170      """
171    def start_vertex(self, v, g):    def start_vertex(self, v, g):
172      self._seperator('start_vertex')      self._seperator('start_vertex')
173      #pass      #pass
174      #print 'sssss'      #print 'sssss'
175    
   
176    def discover_vertex(self, v, g):    def discover_vertex(self, v, g):
177      #print '>>>'      #print '>>>'
178      self._seperator('discover_vertex')      self._seperator('discover_vertex')
# Line 144  class tree_edges_dfs_visitor(bgl.dfs_vis Line 192  class tree_edges_dfs_visitor(bgl.dfs_vis
192      self.current_path = []      self.current_path = []
193      self.depth = 0      self.depth = 0
194      self._seperator('finish_vertex')      self._seperator('finish_vertex')
195      """
196    
197    def _seperator(self, label = 'unknown'):    def _seperator(self, label = 'unknown'):
198      if 1 or self.state:      if 1 or self.state:
# Line 186  def build_fixed_graph(): Line 235  def build_fixed_graph():
235    e3 = graph.add_edge(v3, v4)    e3 = graph.add_edge(v3, v4)
236        
237    e4 = graph.add_edge(v1, v4)    e4 = graph.add_edge(v1, v4)
238    #e5 = graph.add_edge(v3, v2)    e5 = graph.add_edge(v2, v3)
239    #e6 = graph.add_edge(v2, v4)    #e6 = graph.add_edge(v2, v4)
240    
241    """    """
# Line 261  def dump_track(graph, track): Line 310  def dump_track(graph, track):
310        
311    print ' -> '.join(track_ids)    print ' -> '.join(track_ids)
312    
313    def dump_edges(g, edges):
314      name_map = g.vertex_properties['node_id']
315      for e in edges:
316        (u, v) = (g.source(e), g.target(e))
317        print "edge ",
318        print name_map[u],
319        print " -> ",
320        print name_map[v]
321    
322  def find_path_solutions(source, target, graph, paths):  def find_path_solutions(source, target, graph, paths):
323        
324    print    print
# Line 304  def main(): Line 362  def main():
362    #mst_edges = bgl.kruskal_minimum_spanning_tree(graph, weight)    #mst_edges = bgl.kruskal_minimum_spanning_tree(graph, weight)
363    #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)
364        
365      """
366    for root in graph.vertices:    for root in graph.vertices:
367      print      print
368      print '=' * 42      print '=' * 42
# Line 316  def main(): Line 375  def main():
375      #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)
376      #find_path_solutions(index['1'], index['4'], graph, visitor.paths)      #find_path_solutions(index['1'], index['4'], graph, visitor.paths)
377    #sys.exit(0)    #sys.exit(0)
378      """
379    
380    startIndex = random.choice(index.keys())    startIndex = random.choice(index.keys())
381    endIndex = random.choice(index.keys())    endIndex = random.choice(index.keys())
# Line 329  def main(): Line 389  def main():
389    
390    def doCompute():    def doCompute():
391      cmap = graph.vertex_property_map('color')      cmap = graph.vertex_property_map('color')
392      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)
393      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)
394      #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)
395      find_path_solutions(startVertex, endVertex, graph, visitor.paths)      #find_path_solutions(startVertex, endVertex, graph, visitor.paths)
396        for path in visitor.paths:
397          print '-' * 21
398          dump_edges(graph, path)
399    
400    if ENABLE_PROFILING:    if ENABLE_PROFILING:
401      global paths      global paths
Legend:
Removed from v.1.3  
changed lines
  Added in v.1.5
MailToCvsAdmin">MailToCvsAdmin
 ViewVC Help
Powered by ViewVC 1.1.26 RSS 2.0 feed