scripts/sixdegrees/boostgraph.py

#!/usr/bin/env python

# $Id: sixtest.py,v 1.5 2008/02/06 22:59:39 joko Exp $

# (c) 2008 Andreas Motl <andreas.motl@ilo.de>

# This program is free software: you can redistribute it and/or modify
# it under the terms of the GNU Affero General Public License as published by
# the Free Software Foundation, either version 3 of the License, or
# (at your option) any later version.
# 
# This program is distributed in the hope that it will be useful,
# but WITHOUT ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
# GNU Affero General Public License for more details.
# 
# You should have received a copy of the GNU Affero General Public License
# along with this program.  If not, see <http://www.gnu.org/licenses/>.


# Uses BGL-Python (depth_first_search)
#
# BGL-Python Homepage: http://osl.iu.edu/~dgregor/bgl-python/
#
# Documentation:
#  - http://osl.iu.edu/~dgregor/bgl-python/reference/boost.graph.html
#  - http://www.boost.org/libs/graph/doc/depth_first_search.html
#
# Subversion-Repository: https://svn.osl.iu.edu/svn/projects_viz/bgl-python/


import sys, os

sys.path.append('bgl_python')
os.environ['PATH'] += ';' + './bgl_python'

import boost.graph as bgl


# from http://www.boost.org/libs/graph/doc/DFSVisitor.html
class tree_edges_dfs_visitor(bgl.dfs_visitor):
  
  def __init__(self, name_map):
    #bgl.dfs_visitor.__init__(self)
    self.name_map = name_map
    self.state = True

  def tree_edge(self, e, g):
    (u, v) = (g.source(e), g.target(e))
    print "Tree edge ",
    print self.name_map[u],
    print " -> ",
    print self.name_map[v]
    self.state = True

  def start_vertex(self, v, g):
    #print 'sssss'
    self._seperator()

  def initialize_vertex(self, v, g):
    #print '>>>'
    self._seperator()

  def finish_vertex(self, v, g):
    #print '<<<'
    self._seperator()

  def _seperator(self):
    if self.state:
      print '-' * 21
      self.state = False

def build_fixed_graph():
  graph = bgl.Graph()

  #graph.add_vertex_property_map(name='my_name', type='float')

  # 'write_graphviz' requires property 'node_id' on vertices
  # see http://lists.boost.org/boost-users/2006/06/19877.php
  vmap = graph.vertex_property_map('string')
  graph.vertex_properties['node_id'] = vmap


  v1 = graph.add_vertex()
  vmap[v1] = '1'

  v2 = graph.add_vertex()
  vmap[v2] = '2'

  v3 = graph.add_vertex()
  vmap[v3] = '3'

  v4 = graph.add_vertex()
  vmap[v4] = '4'

  e1 = graph.add_edge(v1, v2)
  e2 = graph.add_edge(v1, v3)
  e3 = graph.add_edge(v3, v4)

  """
  for vertex in graph.vertices:
    #print vertex.id, vertex
    print vmap[vertex], vertex
    #print vertex.__getattribute__('id')
    #print vertex['id']
    #print vertex.get('id')
    #print 
  """

  graph.write_graphviz('friends.dot')
  
  return graph


def main():
  
  # Load a graph from the GraphViz file 'mst.dot'
  #graph = bgl.Graph.read_graphviz('mst.dot')
  graph = build_fixed_graph()

  # Compute all paths rooted from each vertex
  #mst_edges = bgl.kruskal_minimum_spanning_tree(graph, weight)
  #bgl.depth_first_search(graph, root_vertex = None, visitor = None, color_map = None)
  for root in graph.vertices:
    print
    print '=' * 42
    print 'Paths originating from node %s' % graph.vertex_properties['node_id'][root]
    visitor = tree_edges_dfs_visitor(graph.vertex_properties['node_id'])
    bgl.depth_first_search(graph, root_vertex = root, visitor = visitor, color_map = None)
  
  
  # STOP HERE
  sys.exit(0)


  # Compute the weight of the minimum spanning tree 
  #print 'MST weight =',sum([weight[e] for e in mst_edges])

  # Put the weights into the label. Make MST edges solid while all other
  # edges remain dashed.
  label = graph.edge_property_map('string')
  style = graph.edge_property_map('string')
  for e in graph.edges:
      label[e] = str(weight[e])
      if e in mst_edges:
          style[e] = 'solid'
      else:
          style[e] = 'dashed'

  # Associate the label and style property maps with the graph for output
  graph.edge_properties['label'] = label
  graph.edge_properties['style'] = style

  # Write out the graph in GraphViz DOT format
  graph.write_graphviz('friends_path_2to3.dot')


if __name__ == '__main__':
  main()
1	joko	1.1	#!/usr/bin/env python
2
3			# $Id: sixtest.py,v 1.5 2008/02/06 22:59:39 joko Exp $
4
5			# (c) 2008 Andreas Motl <andreas.motl@ilo.de>
6
7			# This program is free software: you can redistribute it and/or modify
8			# it under the terms of the GNU Affero General Public License as published by
9			# the Free Software Foundation, either version 3 of the License, or
10			# (at your option) any later version.
11			#
12			# This program is distributed in the hope that it will be useful,
13			# but WITHOUT ANY WARRANTY; without even the implied warranty of
14			# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15			# GNU Affero General Public License for more details.
16			#
17			# You should have received a copy of the GNU Affero General Public License
18			# along with this program. If not, see <http://www.gnu.org/licenses/>.
19
20
21
22			# Uses BGL-Python (depth_first_search)
23			#
24			# BGL-Python Homepage: http://osl.iu.edu/~dgregor/bgl-python/
25			#
26			# Documentation:
27			# - http://osl.iu.edu/~dgregor/bgl-python/reference/boost.graph.html
28			# - http://www.boost.org/libs/graph/doc/depth_first_search.html
29			#
30			# Subversion-Repository: https://svn.osl.iu.edu/svn/projects_viz/bgl-python/
31
32
33			import sys, os
34
35			sys.path.append('bgl_python')
36			os.environ['PATH'] += ';' + './bgl_python'
37
38			import boost.graph as bgl
39
40
41
42			# from http://www.boost.org/libs/graph/doc/DFSVisitor.html
43			class tree_edges_dfs_visitor(bgl.dfs_visitor):
44
45			def __init__(self, name_map):
46			#bgl.dfs_visitor.__init__(self)
47			self.name_map = name_map
48			self.state = True
49
50			def tree_edge(self, e, g):
51			(u, v) = (g.source(e), g.target(e))
52			print "Tree edge ",
53			print self.name_map[u],
54			print " -> ",
55			print self.name_map[v]
56			self.state = True
57
58			def start_vertex(self, v, g):
59			#print 'sssss'
60			self._seperator()
61
62			def initialize_vertex(self, v, g):
63			#print '>>>'
64			self._seperator()
65
66			def finish_vertex(self, v, g):
67			#print '<<<'
68			self._seperator()
69
70			def _seperator(self):
71			if self.state:
72			print '-' * 21
73			self.state = False
74
75			def build_fixed_graph():
76			graph = bgl.Graph()
77
78			#graph.add_vertex_property_map(name='my_name', type='float')
79
80			# 'write_graphviz' requires property 'node_id' on vertices
81			# see http://lists.boost.org/boost-users/2006/06/19877.php
82			vmap = graph.vertex_property_map('string')
83			graph.vertex_properties['node_id'] = vmap
84
85
86			v1 = graph.add_vertex()
87			vmap[v1] = '1'
88
89			v2 = graph.add_vertex()
90			vmap[v2] = '2'
91
92			v3 = graph.add_vertex()
93			vmap[v3] = '3'
94
95			v4 = graph.add_vertex()
96			vmap[v4] = '4'
97
98			e1 = graph.add_edge(v1, v2)
99			e2 = graph.add_edge(v1, v3)
100			e3 = graph.add_edge(v3, v4)
101
102			"""
103			for vertex in graph.vertices:
104			#print vertex.id, vertex
105			print vmap[vertex], vertex
106			#print vertex.__getattribute__('id')
107			#print vertex['id']
108			#print vertex.get('id')
109			#print
110			"""
111
112			graph.write_graphviz('friends.dot')
113
114			return graph
115
116
117
118			def main():
119
120			# Load a graph from the GraphViz file 'mst.dot'
121			#graph = bgl.Graph.read_graphviz('mst.dot')
122			graph = build_fixed_graph()
123
124			# Compute all paths rooted from each vertex
125			#mst_edges = bgl.kruskal_minimum_spanning_tree(graph, weight)
126			#bgl.depth_first_search(graph, root_vertex = None, visitor = None, color_map = None)
127			for root in graph.vertices:
128			print
129			print '=' * 42
130			print 'Paths originating from node %s' % graph.vertex_properties['node_id'][root]
131			visitor = tree_edges_dfs_visitor(graph.vertex_properties['node_id'])
132			bgl.depth_first_search(graph, root_vertex = root, visitor = visitor, color_map = None)
133
134
135			# STOP HERE
136			sys.exit(0)
137
138
139
140
141
142			# Compute the weight of the minimum spanning tree
143			#print 'MST weight =',sum([weight[e] for e in mst_edges])
144
145			# Put the weights into the label. Make MST edges solid while all other
146			# edges remain dashed.
147			label = graph.edge_property_map('string')
148			style = graph.edge_property_map('string')
149			for e in graph.edges:
150			label[e] = str(weight[e])
151			if e in mst_edges:
152			style[e] = 'solid'
153			else:
154			style[e] = 'dashed'
155
156			# Associate the label and style property maps with the graph for output
157			graph.edge_properties['label'] = label
158			graph.edge_properties['style'] = style
159
160			# Write out the graph in GraphViz DOT format
161			graph.write_graphviz('friends_path_2to3.dot')
162
163
164			if __name__ == '__main__':
165			main()
MailToCvsAdmin">MailToCvsAdmin	ViewVC Help
Powered by ViewVC 1.1.26