/[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.2 by joko, Thu Feb 21 01:54:28 2008 UTC revision 1.3 by joko, Thu Feb 21 04:46:47 2008 UTC
# Line 3  Line 3 
3  # $Id$  # $Id$
4    
5  # (c) 2008 Andreas Motl <andreas.motl@ilo.de>  # (c) 2008 Andreas Motl <andreas.motl@ilo.de>
6    # (c) 2008 Sebastian Utz <su@rotamente.com>
7    
8  # This program is free software: you can redistribute it and/or modify  # This program is free software: you can redistribute it and/or modify
9  # it under the terms of the GNU Affero General Public License as published by  # it under the terms of the GNU Affero General Public License as published by
# Line 36  Line 37 
37  # Subversion-Repository: https://svn.osl.iu.edu/svn/projects_viz/bgl-python/  # Subversion-Repository: https://svn.osl.iu.edu/svn/projects_viz/bgl-python/
38    
39    
40    RANDOM_MAX_NODES = 10
41    RANDOM_MAX_CHILDREN_PER_NODE = 500
42    MAX_SEARCH_DEPTH = 50
43    
44    
45    ENABLE_PROFILING = False
46    
47    if ENABLE_PROFILING:
48      import profile
49      from profile import Profile
50    
51    
52  import sys, os  import sys, os
53    import random
54    
55  sys.path.append('bgl_python')  sys.path.append('bgl_python')
56  os.environ['PATH'] += ';' + './bgl_python'  os.environ['PATH'] += ';' + './bgl_python'
# Line 47  import boost.graph as bgl Line 61  import boost.graph as bgl
61    
62  # from http://www.boost.org/libs/graph/doc/DFSVisitor.html  # from http://www.boost.org/libs/graph/doc/DFSVisitor.html
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):
65        
66    def __init__(self, name_map):    def __init__(self, maxdepth, name_map, color_map):
67        
68        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            
# Line 58  class tree_edges_dfs_visitor(bgl.dfs_vis Line 76  class tree_edges_dfs_visitor(bgl.dfs_vis
76      # for tracking paths      # for tracking paths
77      self.paths = []      self.paths = []
78      self.current_path = []      self.current_path = []
79        
80        # for limiting search depth
81        """
82        self.color_map = color_map
83        self.maxdepth = maxdepth
84        self.depth = 0
85        """
86        
87        self.level = 0
88        
89    
90      def examine_edge(self, e, g):
91        self.tree_edge2(e, g, 'examine_edge')
92    
93    def tree_edge(self, e, g):    def tree_edge2(self, e, g, label='tree_edge'):
94        
95      (u, v) = (g.source(e), g.target(e))      (u, v) = (g.source(e), g.target(e))
96        
97        # increase current search depth (level)
98        """
99        self.depth += 1
100        
101        # check if maximum depth reached
102        if self.depth == self.maxdepth:
103          # color all succeeding vertices to black (mark as "already visited")
104          # BUG!!! marks too many nodes
105          for child_edge in g.out_edges(v):
106            end_vertex = g.target(child_edge)
107            #self.color_map[end_vertex] = bgl.Color(bgl.Color.gray)
108        """
109          
110        
111        if label:
112          print "%s:" % label,
113      print "Tree edge ",      print "Tree edge ",
114      print self.name_map[u],      print self.name_map[u],
115      print " -> ",      print " -> ",
116      print self.name_map[v]      print self.name_map[v]
117        sys.stdout.flush()
118      self.state = True      self.state = True
119      self.current_path.append(e)      self.current_path.append(e)
120      #return False      #return False
121    
122    def start_vertex(self, v, g):    def start_vertex(self, v, g):
123      #self._seperator()      self._seperator('start_vertex')
124      pass      #pass
125      #print 'sssss'      #print 'sssss'
126    
127    
128      def discover_vertex(self, v, g):
129        #print '>>>'
130        self._seperator('discover_vertex')
131        #pass
132    
133    def initialize_vertex(self, v, g):    def initialize_vertex(self, v, g):
134      #print '>>>'      #print '>>>'
135      self._seperator('initialize_vertex')      self._seperator('initialize_vertex')
136    
137      def examine_vertex(self, v, g):
138        self._seperator('examine_vertex')
139    
140    def finish_vertex(self, v, g):    def finish_vertex(self, v, g):
141      #print '<<<'      #print '<<<'
142      if self.current_path:      if self.current_path:
143        self.paths.append(self.current_path)        self.paths.append(self.current_path)
144      self.current_path = []      self.current_path = []
145        self.depth = 0
146      self._seperator('finish_vertex')      self._seperator('finish_vertex')
147    
148    def _seperator(self, label = 'unknown'):    def _seperator(self, label = 'unknown'):
149      if self.state:      if 1 or self.state:
150        print '-' * 21, label        print '-' * 21, label
151        self.state = False        self.state = False
152    
# Line 124  def build_fixed_graph(): Line 184  def build_fixed_graph():
184    e1 = graph.add_edge(v1, v2)    e1 = graph.add_edge(v1, v2)
185    e2 = graph.add_edge(v1, v3)    e2 = graph.add_edge(v1, v3)
186    e3 = graph.add_edge(v3, v4)    e3 = graph.add_edge(v3, v4)
187      
188      e4 = graph.add_edge(v1, v4)
189      #e5 = graph.add_edge(v3, v2)
190      #e6 = graph.add_edge(v2, v4)
191    
192    """    """
193    for vertex in graph.vertices:    for vertex in graph.vertices:
# Line 140  def build_fixed_graph(): Line 204  def build_fixed_graph():
204    return (graph, index)    return (graph, index)
205    
206    
207    def build_random_graph():
208    
209      graph = bgl.Graph()
210      index = {}
211    
212      vmap = graph.vertex_property_map('string')
213      graph.vertex_properties['node_id'] = vmap
214    
215      count = 0
216      for parent_id in range(1, RANDOM_MAX_NODES + 1):
217        count += 1
218        if count % 100 == 0:
219          sys.stderr.write('.')
220          
221        parent_id_str = str(parent_id)
222        v1New = False
223        if not index.has_key(parent_id_str):
224          #print "adding v1:", parent_id_str
225          myVertex1 = graph.add_vertex()
226          vmap[myVertex1] = parent_id_str
227          index[parent_id_str] = myVertex1
228          v1New = True
229    
230      
231      count = 0
232      #for j in range(1, random.randint(1, RANDOM_MAX_CHILDREN_PER_NODE)):
233      for j in range(1, RANDOM_MAX_CHILDREN_PER_NODE):
234    
235        count += 1
236        if count % 100 == 0:
237          sys.stderr.write('.')
238    
239        parent_id_str = random.choice(index.keys())
240        
241        child_id_str = parent_id_str
242        while child_id_str == parent_id_str:
243          child_id_str = random.choice(index.keys())
244          #print child_id_str
245          
246          myVertex1 = index[parent_id_str]
247          myVertex2 = index[child_id_str]
248          
249          graph.add_edge(myVertex1, myVertex2)
250            
251      sys.stderr.write("\n")
252    
253      return (graph, index)
254    
255    
256    def dump_track(graph, track):
257      track_ids = []
258      for node in track:
259        node_id = graph.vertex_properties['node_id'][node]
260        track_ids.append(node_id)
261      
262      print ' -> '.join(track_ids)
263    
264  def find_path_solutions(source, target, graph, paths):  def find_path_solutions(source, target, graph, paths):
265        
# Line 152  def find_path_solutions(source, target, Line 272  def find_path_solutions(source, target,
272    #(u, v) = (g.source(e), g.target(e))    #(u, v) = (g.source(e), g.target(e))
273    for path in paths:    for path in paths:
274      startVertex = graph.source(path[0])      startVertex = graph.source(path[0])
275      endVertex = graph.target(path[-1])      
276      if source == startVertex and target == endVertex:      track = []
277        print "found"      track.append(startVertex)
278        
279        for edge in path:
280          endVertex = graph.target(edge)
281          track.append(endVertex)
282          if source == startVertex and target == endVertex:
283            #print "found:", track
284            dump_track(graph, track)
285    
286    def dump_graph(graph):
287      for edge in graph.edges:
288        (u, v) = (graph.source(edge), graph.target(edge))
289        startIndex = graph.vertex_properties['node_id'][u]
290        endIndex = graph.vertex_properties['node_id'][v]
291        print "%s -> %s" % (startIndex, endIndex)
292        
293    
294  def main():  def main():
295        
296    # Load a graph from the GraphViz file 'mst.dot'    # Load a graph from the GraphViz file 'mst.dot'
297    #graph = bgl.Graph.read_graphviz('mst.dot')    #graph = bgl.Graph.read_graphviz('mst.dot')
298    (graph, index) = build_fixed_graph()    (graph, index) = build_fixed_graph()
299      #(graph, index) = build_random_graph()
300    
301      #dump_graph(graph)
302    
303    # Compute all paths rooted from each vertex    # Compute all paths rooted from each vertex
304    #mst_edges = bgl.kruskal_minimum_spanning_tree(graph, weight)    #mst_edges = bgl.kruskal_minimum_spanning_tree(graph, weight)
305    #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)
306      
307    for root in graph.vertices:    for root in graph.vertices:
308      print      print
309      print '=' * 42      print '=' * 42
310      print 'Paths originating from node %s' % graph.vertex_properties['node_id'][root]      print 'Paths originating from node %s' % graph.vertex_properties['node_id'][root]
311      visitor = tree_edges_dfs_visitor(graph.vertex_properties['node_id'])      #cmap = graph.vertex_property_map('color')
312        cmap = None
313        visitor = tree_edges_dfs_visitor(3, graph.vertex_properties['node_id'], cmap)
314        #visitor = tree_edges_bfs_visitor(3, graph.vertex_properties['node_id'], cmap)
315      bgl.depth_first_search(graph, root_vertex = root, visitor = visitor, color_map = None)      bgl.depth_first_search(graph, root_vertex = root, visitor = visitor, color_map = None)
316            #bgl.breadth_first_search(graph, root_vertex = root, visitor = visitor, color_map = None)
317      find_path_solutions(index['4'], index['2'], graph, visitor.paths)      #find_path_solutions(index['1'], index['4'], graph, visitor.paths)
318      #sys.exit(0)
319    
320      startIndex = random.choice(index.keys())
321      endIndex = random.choice(index.keys())
322      startIndex = '1'
323      endIndex = '4'
324    
325      print "Trying to find solution for: %s -> %s" % (startIndex, endIndex)
326    
327      startVertex = index[startIndex]
328      endVertex = index[endIndex]
329    
330      def doCompute():
331        cmap = graph.vertex_property_map('color')
332        visitor = tree_edges_dfs_visitor(MAX_SEARCH_DEPTH, graph.vertex_properties['node_id'], cmap)
333        bgl.depth_first_search(graph, root_vertex = startVertex, visitor = visitor, color_map = None)
334        #bgl.depth_first_visit(graph, root_vertex = startVertex, visitor = visitor, color_map = cmap)
335        find_path_solutions(startVertex, endVertex, graph, visitor.paths)
336    
337      if ENABLE_PROFILING:
338        global paths
339        paths = []
340        p = Profile()
341        p.runcall(doCompute)
342        p.print_stats()
343      else:
344        paths = doCompute()
345    
346        
347    # STOP HERE    # STOP HERE
348    sys.exit(0)    sys.exit(0)
Legend:
Removed from v.1.2  
changed lines
  Added in v.1.3
MailToCvsAdmin">MailToCvsAdmin
 ViewVC Help
Powered by ViewVC 1.1.26 RSS 2.0 feed