/[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.6 by joko, Tue Feb 26 10:11:13 2008 UTC
# Line 38  Line 38 
38    
39    
40  RANDOM_MAX_NODES = 10  RANDOM_MAX_NODES = 10
41  RANDOM_MAX_CHILDREN_PER_NODE = 500  RANDOM_MAX_CHILDREN_PER_NODE = 10
42  MAX_SEARCH_DEPTH = 50  MAX_SEARCH_DEPTH = 50
43    
44    
45    DEBUG = True
46    DEBUG = False
47    
48  ENABLE_PROFILING = False  ENABLE_PROFILING = False
49    
50  if ENABLE_PROFILING:  if ENABLE_PROFILING:
# Line 60  import boost.graph as bgl Line 63  import boost.graph as bgl
63    
64    
65  # from http://www.boost.org/libs/graph/doc/DFSVisitor.html  # from http://www.boost.org/libs/graph/doc/DFSVisitor.html
66  class tree_edges_dfs_visitor(bgl.dfs_visitor):  #class tree_edges_dfs_visitor(bgl.dfs_visitor):
67    class dfs_visitor_debug(bgl.dfs_visitor):
68  #class tree_edges_bfs_visitor(bgl.bfs_visitor):  #class tree_edges_bfs_visitor(bgl.bfs_visitor):
69        
70    def __init__(self, maxdepth, name_map, color_map):    def __init__(self, startVertex, endVertex, maxdepth, color_map):
71            
72      print dir(self)      print dir(self)
73            
74      #bgl.dfs_visitor.__init__(self)      #bgl.dfs_visitor.__init__(self)
75      self.name_map = name_map      #self.name_map = name_map
76        
77        self.startVertex = startVertex
78        self.endVertex = endVertex
79            
80      # for recognizing path switches      # for recognizing path switches
81      self.state = True      self.state = True
# Line 87  class tree_edges_dfs_visitor(bgl.dfs_vis Line 94  class tree_edges_dfs_visitor(bgl.dfs_vis
94      self.level = 0      self.level = 0
95            
96    
97      def back_edge(self, e, g):
98        self._touch_edge(e, g, 'back_edge')
99    
100      def forward_or_cross_edge(self, e, g):
101        self._touch_edge(e, g, 'forward_or_cross_edge')
102    
103      def tree_edge(self, e, g):
104        self._touch_edge(e, g, 'tree_edge')
105    
106    def examine_edge(self, e, g):    def examine_edge(self, e, g):
107      self.tree_edge2(e, g, 'examine_edge')      self._touch_edge(e, g, 'examine_edge')
108    
109    def tree_edge2(self, e, g, label='tree_edge'):    def _touch_edge(self, e, g, label=''):
110            
111      (u, v) = (g.source(e), g.target(e))      (u, v) = (g.source(e), g.target(e))
112            
# Line 106  class tree_edges_dfs_visitor(bgl.dfs_vis Line 122  class tree_edges_dfs_visitor(bgl.dfs_vis
122          end_vertex = g.target(child_edge)          end_vertex = g.target(child_edge)
123          #self.color_map[end_vertex] = bgl.Color(bgl.Color.gray)          #self.color_map[end_vertex] = bgl.Color(bgl.Color.gray)
124      """      """
125              
126        name_map = g.vertex_properties['node_id']
127            
128      if label:      if label:
129        print "%s:" % label,        print "%s:\t" % label,
130      print "Tree edge ",      #print "edge ",
131      print self.name_map[u],      print name_map[u],
132      print " -> ",      print " -> ",
133      print self.name_map[v]      print name_map[v]
134      sys.stdout.flush()      
135      self.state = True      #self.state = True
136      self.current_path.append(e)      
137      #return False      if u == self.startVertex:
138          print "starting"
139          self.current_path = []
140    
141        # skip circular references
142        if v != self.startVertex:
143          self.current_path.append(e)
144    
145        if v == self.endVertex and self.current_path:
146          print "found:"
147          print self.current_path
148          self.paths.append(self.current_path)
149          self.current_path = []
150    
151    
152      def _touch_vertex(self, v, g, label=''):
153        name_map = g.vertex_properties['node_id']
154        id = name_map[v]
155        print '%s:\t%s' % (label, id)
156    
157    
158    def start_vertex(self, v, g):    def start_vertex(self, v, g):
159        self._touch_vertex(v, g, 'start_vertex')
160    
161      def discover_vertex(self, v, g):
162        self._touch_vertex(v, g, 'discover_vertex')
163    
164      def initialize_vertex(self, v, g):
165        self._touch_vertex(v, g, 'initialize_vertex')
166    
167      def examine_vertex(self, v, g):
168        self._touch_vertex(v, g, 'examine_vertex')
169    
170      def finish_vertex(self, v, g):
171        self._touch_vertex(v, g, 'finish_vertex')
172    
173    
174      """
175      def start_vertex(self, v, g):
176      self._seperator('start_vertex')      self._seperator('start_vertex')
177      #pass      #pass
178      #print 'sssss'      #print 'sssss'
179    
   
180    def discover_vertex(self, v, g):    def discover_vertex(self, v, g):
181      #print '>>>'      #print '>>>'
182      self._seperator('discover_vertex')      self._seperator('discover_vertex')
# Line 144  class tree_edges_dfs_visitor(bgl.dfs_vis Line 196  class tree_edges_dfs_visitor(bgl.dfs_vis
196      self.current_path = []      self.current_path = []
197      self.depth = 0      self.depth = 0
198      self._seperator('finish_vertex')      self._seperator('finish_vertex')
199      """
200    
201    def _seperator(self, label = 'unknown'):    def _seperator(self, label = 'unknown'):
202      if 1 or self.state:      if 1 or self.state:
# Line 151  class tree_edges_dfs_visitor(bgl.dfs_vis Line 204  class tree_edges_dfs_visitor(bgl.dfs_vis
204        self.state = False        self.state = False
205    
206    
207    class tree_edges_dfs_visitor(bgl.dfs_visitor):
208    
209      def __init__(self, startVertex, endVertex, maxdepth, color_map):
210        
211        #print dir(self)
212        
213        #bgl.dfs_visitor.__init__(self)
214        #self.name_map = name_map
215        
216        self.startVertex = startVertex
217        self.endVertex = endVertex
218        
219        # for recognizing path switches
220        self.state = True
221        
222        # for tracking paths
223        self.paths = []
224        self.current_path = []
225        
226        # for limiting search depth
227        """
228        self.color_map = color_map
229        self.maxdepth = maxdepth
230        self.depth = 0
231        """
232        
233        self.level = 0
234    
235      def tree_edge(self, e, g):
236        self._touch_edge(e, g, 'tree_edge')
237    
238      def forward_or_cross_edge(self, e, g):
239        #self._touch_edge(e, g, 'forward_or_cross_edge')
240        self.find_new_variations_from_source(e, g)
241        self.find_new_variations_to_target(e, g)
242    
243      
244      def find_new_variations_from_source(self, e, g):
245        # find additional solutions as parts of already established ones (e.g. shortcuts)
246        localEndVertex = g.target(e)
247        path_additional = []
248        for path in self.paths:
249          found = False
250          for edge in path:
251            if found:
252              path_additional.append(edge)
253            else:
254              if g.source(edge) == localEndVertex:
255                #print "found2"
256                found = True
257                path_additional.append(e)
258                path_additional.append(edge)
259        
260        #print "find_new_variations_from_source:", path_additional
261        if path_additional:
262          self.paths.append(path_additional)
263    
264      def find_new_variations_to_target(self, e, g):
265        # find additional solutions as parts of already established ones (e.g. shortcuts)
266        localStartVertex = g.source(e)
267        localEndVertex = g.target(e)
268        
269        #return
270        
271        #if not (self.endVertex == localEndVertex and self.startVertex != localStartVertex):
272        if not (self.endVertex == localEndVertex):
273          return
274        
275        # find "direct" solution (start- and end-vertices are directly connected)
276        if self.startVertex == localStartVertex:
277          self.paths.append([e])
278          return
279        
280        #print "check"
281        path_additional = []
282        for path_iter in self.paths:
283          found = False
284          path = list(path_iter)
285          path.reverse()
286          for edge in path:
287            if found:
288              path_additional.insert(0, edge)
289            else:
290              if g.target(edge) == localStartVertex:
291                #print "found2"
292                found = True
293                path_additional.append(e)
294                path_additional.insert(0, edge)
295        
296        #print "find_new_variations_to_target:", path_additional
297        if path_additional:
298          self.paths.append(path_additional)
299    
300      def _touch_edge(self, e, g, label=''):
301        
302        (u, v) = (g.source(e), g.target(e))
303        
304        # increase current search depth (level)
305        """
306        self.depth += 1
307        
308        # check if maximum depth reached
309        if self.depth == self.maxdepth:
310          # color all succeeding vertices to black (mark as "already visited")
311          # BUG!!! marks too many nodes
312          for child_edge in g.out_edges(v):
313            end_vertex = g.target(child_edge)
314            #self.color_map[end_vertex] = bgl.Color(bgl.Color.gray)
315        """
316        
317        name_map = g.vertex_properties['node_id']
318        
319        if DEBUG:
320          if label:
321            print "%s:\t" % label,
322          #print "edge ",
323          print name_map[u],
324          print " -> ",
325          print name_map[v]
326        
327        #self.state = True
328        
329        if u == self.startVertex:
330          #print "starting"
331          self.current_path = []
332    
333        # skip circular references
334        if v != self.startVertex:
335          self.current_path.append(e)
336    
337        # finish current path if target found
338        if v == self.endVertex and self.current_path:
339          #print "found:"
340          #print self.current_path
341          self.paths.append(self.current_path)
342          self.current_path = []
343    
344    
345  def build_fixed_graph():  def build_fixed_graph():
346        
347    graph = bgl.Graph()    graph = bgl.Graph()
# Line 186  def build_fixed_graph(): Line 377  def build_fixed_graph():
377    e3 = graph.add_edge(v3, v4)    e3 = graph.add_edge(v3, v4)
378        
379    e4 = graph.add_edge(v1, v4)    e4 = graph.add_edge(v1, v4)
380    #e5 = graph.add_edge(v3, v2)    e5 = graph.add_edge(v2, v3)
381    #e6 = graph.add_edge(v2, v4)    e6 = graph.add_edge(v2, v4)
382    
383    """    """
384    for vertex in graph.vertices:    for vertex in graph.vertices:
# Line 261  def dump_track(graph, track): Line 452  def dump_track(graph, track):
452        
453    print ' -> '.join(track_ids)    print ' -> '.join(track_ids)
454    
455    def dump_edges(g, edges):
456      name_map = g.vertex_properties['node_id']
457      for e in edges:
458        (u, v) = (g.source(e), g.target(e))
459        print "edge ",
460        print name_map[u],
461        print " -> ",
462        print name_map[v]
463    
464  def find_path_solutions(source, target, graph, paths):  def find_path_solutions(source, target, graph, paths):
465        
466    print    print
# Line 289  def dump_graph(graph): Line 489  def dump_graph(graph):
489      startIndex = graph.vertex_properties['node_id'][u]      startIndex = graph.vertex_properties['node_id'][u]
490      endIndex = graph.vertex_properties['node_id'][v]      endIndex = graph.vertex_properties['node_id'][v]
491      print "%s -> %s" % (startIndex, endIndex)      print "%s -> %s" % (startIndex, endIndex)
492        
493    def dump_edges_vertices(graph, edge_list):
494      startVertex = graph.source(edge_list[0])
495      
496      track = []
497      track.append(startVertex)
498    
499      for edge in edge_list:
500        endVertex = graph.target(edge)
501        track.append(endVertex)
502      dump_track(graph, track)
503    
504    def print_path_solutions(graph, paths):
505      for path in paths:
506        if DEBUG:
507          print '-' * 21
508          dump_edges(graph, path)
509        dump_edges_vertices(graph, path)
510    
511    
512    
513  def main():  def main():
514        
515    # Load a graph from the GraphViz file 'mst.dot'    # Load a graph from the GraphViz file 'mst.dot'
516    #graph = bgl.Graph.read_graphviz('mst.dot')    #graph = bgl.Graph.read_graphviz('mst.dot')
517      
518      # 1. fixed graph with fixed required solution
519    (graph, index) = build_fixed_graph()    (graph, index) = build_fixed_graph()
520      startIndex = '1'
521      endIndex = '4'
522      
523      # 2. random graph with according solution
524    #(graph, index) = build_random_graph()    #(graph, index) = build_random_graph()
525      #startIndex = random.choice(index.keys())
526      #endIndex = random.choice(index.keys())
527    
528    #dump_graph(graph)    print '-' * 42
529      print "complete graph:"
530      dump_graph(graph)
531      print '-' * 42
532    
533    # Compute all paths rooted from each vertex    # Compute all paths rooted from each vertex
534    #mst_edges = bgl.kruskal_minimum_spanning_tree(graph, weight)    #mst_edges = bgl.kruskal_minimum_spanning_tree(graph, weight)
535    #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)
536        
537      """
538    for root in graph.vertices:    for root in graph.vertices:
539      print      print
540      print '=' * 42      print '=' * 42
# Line 316  def main(): Line 547  def main():
547      #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)
548      #find_path_solutions(index['1'], index['4'], graph, visitor.paths)      #find_path_solutions(index['1'], index['4'], graph, visitor.paths)
549    #sys.exit(0)    #sys.exit(0)
550      """
   startIndex = random.choice(index.keys())  
   endIndex = random.choice(index.keys())  
   startIndex = '1'  
   endIndex = '4'  
551    
552    print "Trying to find solution for: %s -> %s" % (startIndex, endIndex)    print "Trying to find solution for: %s -> %s" % (startIndex, endIndex)
553    
# Line 329  def main(): Line 556  def main():
556    
557    def doCompute():    def doCompute():
558      cmap = graph.vertex_property_map('color')      cmap = graph.vertex_property_map('color')
559      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)
560      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)
561      #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)
562      find_path_solutions(startVertex, endVertex, graph, visitor.paths)      #find_path_solutions(startVertex, endVertex, graph, visitor.paths)
563        print '-' * 42
564        print "solution(s):"
565        print_path_solutions(graph, visitor.paths)
566    
567    if ENABLE_PROFILING:    if ENABLE_PROFILING:
568      global paths      global paths
Legend:
Removed from v.1.3  
changed lines
  Added in v.1.6
MailToCvsAdmin">MailToCvsAdmin
 ViewVC Help
Powered by ViewVC 1.1.26 RSS 2.0 feed