/[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.1 by joko, Fri Feb 8 09:05:02 2008 UTC revision 1.2 by joko, Thu Feb 21 01:54:28 2008 UTC
# Line 23  Line 23 
23  #  #
24  # BGL-Python Homepage: http://osl.iu.edu/~dgregor/bgl-python/  # BGL-Python Homepage: http://osl.iu.edu/~dgregor/bgl-python/
25  #  #
26  # Documentation:  # Documentation (Boost):
27  #  - http://osl.iu.edu/~dgregor/bgl-python/reference/boost.graph.html  #  - http://www.boost.org/libs/graph/doc/graph_theory_review.html
28  #  - http://www.boost.org/libs/graph/doc/depth_first_search.html  #  - http://www.boost.org/libs/graph/doc/depth_first_search.html
29    #  - http://www.boost.org/boost/graph/depth_first_search.hpp
30    #  - http://www.boost.org/libs/graph/doc/DFSVisitor.html
31    #  - http://www.boost.org/libs/graph/example/dfs-example.cpp
32    #
33    # Documentation (BGL-Python):
34    #  - http://osl.iu.edu/~dgregor/bgl-python/reference/boost.graph.html
35  #  #
36  # Subversion-Repository: https://svn.osl.iu.edu/svn/projects_viz/bgl-python/  # Subversion-Repository: https://svn.osl.iu.edu/svn/projects_viz/bgl-python/
37    
# Line 45  class tree_edges_dfs_visitor(bgl.dfs_vis Line 51  class tree_edges_dfs_visitor(bgl.dfs_vis
51    def __init__(self, name_map):    def __init__(self, name_map):
52      #bgl.dfs_visitor.__init__(self)      #bgl.dfs_visitor.__init__(self)
53      self.name_map = name_map      self.name_map = name_map
54        
55        # for recognizing path switches
56      self.state = True      self.state = True
57        
58        # for tracking paths
59        self.paths = []
60        self.current_path = []
61    
62    def tree_edge(self, e, g):    def tree_edge(self, e, g):
63      (u, v) = (g.source(e), g.target(e))      (u, v) = (g.source(e), g.target(e))
# Line 54  class tree_edges_dfs_visitor(bgl.dfs_vis Line 66  class tree_edges_dfs_visitor(bgl.dfs_vis
66      print " -> ",      print " -> ",
67      print self.name_map[v]      print self.name_map[v]
68      self.state = True      self.state = True
69        self.current_path.append(e)
70        #return False
71    
72    def start_vertex(self, v, g):    def start_vertex(self, v, g):
73        #self._seperator()
74        pass
75      #print 'sssss'      #print 'sssss'
     self._seperator()  
76    
77    def initialize_vertex(self, v, g):    def initialize_vertex(self, v, g):
78      #print '>>>'      #print '>>>'
79      self._seperator()      self._seperator('initialize_vertex')
80    
81    def finish_vertex(self, v, g):    def finish_vertex(self, v, g):
82      #print '<<<'      #print '<<<'
83      self._seperator()      if self.current_path:
84          self.paths.append(self.current_path)
85        self.current_path = []
86        self._seperator('finish_vertex')
87    
88    def _seperator(self):    def _seperator(self, label = 'unknown'):
89      if self.state:      if self.state:
90        print '-' * 21        print '-' * 21, label
91        self.state = False        self.state = False
92    
93    
94  def build_fixed_graph():  def build_fixed_graph():
95      
96    graph = bgl.Graph()    graph = bgl.Graph()
97      index = {}
98    
99      # doesn't this work? see http://www.nabble.com/-Graph--Getting-PageRank-to-work-in-BGL-Python-td14207115.html
100    #graph.add_vertex_property_map(name='my_name', type='float')    #graph.add_vertex_property_map(name='my_name', type='float')
101    
102    # 'write_graphviz' requires property 'node_id' on vertices    # 'write_graphviz' requires property 'node_id' on vertices
# Line 85  def build_fixed_graph(): Line 107  def build_fixed_graph():
107    
108    v1 = graph.add_vertex()    v1 = graph.add_vertex()
109    vmap[v1] = '1'    vmap[v1] = '1'
110      index['1'] = v1
111    
112    v2 = graph.add_vertex()    v2 = graph.add_vertex()
113    vmap[v2] = '2'    vmap[v2] = '2'
114      index['2'] = v2
115    
116    v3 = graph.add_vertex()    v3 = graph.add_vertex()
117    vmap[v3] = '3'    vmap[v3] = '3'
118      index['3'] = v3
119    
120    v4 = graph.add_vertex()    v4 = graph.add_vertex()
121    vmap[v4] = '4'    vmap[v4] = '4'
122      index['4'] = v4
123    
124    e1 = graph.add_edge(v1, v2)    e1 = graph.add_edge(v1, v2)
125    e2 = graph.add_edge(v1, v3)    e2 = graph.add_edge(v1, v3)
# Line 111  def build_fixed_graph(): Line 137  def build_fixed_graph():
137    
138    graph.write_graphviz('friends.dot')    graph.write_graphviz('friends.dot')
139        
140    return graph    return (graph, index)
141    
142    
143    
144    def find_path_solutions(source, target, graph, paths):
145      
146      print
147      print "=" * 42
148      print "find_path_solutions"
149      print "=" * 42
150    
151      #print visitor.paths
152      #(u, v) = (g.source(e), g.target(e))
153      for path in paths:
154        startVertex = graph.source(path[0])
155        endVertex = graph.target(path[-1])
156        if source == startVertex and target == endVertex:
157          print "found"
158    
159    
160  def main():  def main():
161        
162    # Load a graph from the GraphViz file 'mst.dot'    # Load a graph from the GraphViz file 'mst.dot'
163    #graph = bgl.Graph.read_graphviz('mst.dot')    #graph = bgl.Graph.read_graphviz('mst.dot')
164    graph = build_fixed_graph()    (graph, index) = build_fixed_graph()
165    
166    # Compute all paths rooted from each vertex    # Compute all paths rooted from each vertex
167    #mst_edges = bgl.kruskal_minimum_spanning_tree(graph, weight)    #mst_edges = bgl.kruskal_minimum_spanning_tree(graph, weight)
# Line 130  def main(): Line 172  def main():
172      print 'Paths originating from node %s' % graph.vertex_properties['node_id'][root]      print 'Paths originating from node %s' % graph.vertex_properties['node_id'][root]
173      visitor = tree_edges_dfs_visitor(graph.vertex_properties['node_id'])      visitor = tree_edges_dfs_visitor(graph.vertex_properties['node_id'])
174      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)
175          
176        find_path_solutions(index['4'], index['2'], graph, visitor.paths)
177        
178    # STOP HERE    # STOP HERE
179    sys.exit(0)    sys.exit(0)
Legend:
Removed from v.1.1  
changed lines
  Added in v.1.2
MailToCvsAdmin">MailToCvsAdmin
 ViewVC Help
Powered by ViewVC 1.1.26 RSS 2.0 feed