scripts/sixdegrees/boostgraph.py

#!/usr/bin/env python

# $Id: boostgraph.py,v 1.1 2008/02/08 09:05:02 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 (Boost):
#  - http://www.boost.org/libs/graph/doc/graph_theory_review.html
#  - http://www.boost.org/libs/graph/doc/depth_first_search.html
#  - http://www.boost.org/boost/graph/depth_first_search.hpp
#  - http://www.boost.org/libs/graph/doc/DFSVisitor.html
#  - http://www.boost.org/libs/graph/example/dfs-example.cpp
#
# Documentation (BGL-Python):
#  - http://osl.iu.edu/~dgregor/bgl-python/reference/boost.graph.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
    
    # for recognizing path switches
    self.state = True
    
    # for tracking paths
    self.paths = []
    self.current_path = []

  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
    self.current_path.append(e)
    #return False

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

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

  def finish_vertex(self, v, g):
    #print '<<<'
    if self.current_path:
      self.paths.append(self.current_path)
    self.current_path = []
    self._seperator('finish_vertex')

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


def build_fixed_graph():
  
  graph = bgl.Graph()
  index = {}

  # doesn't this work? see http://www.nabble.com/-Graph--Getting-PageRank-to-work-in-BGL-Python-td14207115.html
  #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'
  index['1'] = v1

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

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

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

  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, index)


def find_path_solutions(source, target, graph, paths):
  
  print
  print "=" * 42
  print "find_path_solutions"
  print "=" * 42

  #print visitor.paths
  #(u, v) = (g.source(e), g.target(e))
  for path in paths:
    startVertex = graph.source(path[0])
    endVertex = graph.target(path[-1])
    if source == startVertex and target == endVertex:
      print "found"


def main():
  
  # Load a graph from the GraphViz file 'mst.dot'
  #graph = bgl.Graph.read_graphviz('mst.dot')
  (graph, index) = 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)
    
    find_path_solutions(index['4'], index['2'], graph, visitor.paths)
  
  # 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	joko	1.2	# $Id: boostgraph.py,v 1.1 2008/02/08 09:05:02 joko Exp $
4	joko	1.1
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	joko	1.2	# Documentation (Boost):
27			# - http://www.boost.org/libs/graph/doc/graph_theory_review.html
28			# - 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	joko	1.1	# - 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/
37
38
39			import sys, os
40
41			sys.path.append('bgl_python')
42			os.environ['PATH'] += ';' + './bgl_python'
43
44			import boost.graph as bgl
45
46
47
48			# from http://www.boost.org/libs/graph/doc/DFSVisitor.html
49			class tree_edges_dfs_visitor(bgl.dfs_visitor):
50
51			def __init__(self, name_map):
52			#bgl.dfs_visitor.__init__(self)
53			self.name_map = name_map
54	joko	1.2
55			# for recognizing path switches
56	joko	1.1	self.state = True
57	joko	1.2
58			# for tracking paths
59			self.paths = []
60			self.current_path = []
61	joko	1.1
62			def tree_edge(self, e, g):
63			(u, v) = (g.source(e), g.target(e))
64			print "Tree edge ",
65			print self.name_map[u],
66			print " -> ",
67			print self.name_map[v]
68			self.state = True
69	joko	1.2	self.current_path.append(e)
70			#return False
71	joko	1.1
72			def start_vertex(self, v, g):
73	joko	1.2	#self._seperator()
74			pass
75	joko	1.1	#print 'sssss'
76
77			def initialize_vertex(self, v, g):
78			#print '>>>'
79	joko	1.2	self._seperator('initialize_vertex')
80	joko	1.1
81			def finish_vertex(self, v, g):
82			#print '<<<'
83	joko	1.2	if self.current_path:
84			self.paths.append(self.current_path)
85			self.current_path = []
86			self._seperator('finish_vertex')
87	joko	1.1
88	joko	1.2	def _seperator(self, label = 'unknown'):
89	joko	1.1	if self.state:
90	joko	1.2	print '-' * 21, label
91	joko	1.1	self.state = False
92
93	joko	1.2
94	joko	1.1	def build_fixed_graph():
95	joko	1.2
96	joko	1.1	graph = bgl.Graph()
97	joko	1.2	index = {}
98	joko	1.1
99	joko	1.2	# doesn't this work? see http://www.nabble.com/-Graph--Getting-PageRank-to-work-in-BGL-Python-td14207115.html
100	joko	1.1	#graph.add_vertex_property_map(name='my_name', type='float')
101
102			# 'write_graphviz' requires property 'node_id' on vertices
103			# see http://lists.boost.org/boost-users/2006/06/19877.php
104			vmap = graph.vertex_property_map('string')
105			graph.vertex_properties['node_id'] = vmap
106
107
108			v1 = graph.add_vertex()
109			vmap[v1] = '1'
110	joko	1.2	index['1'] = v1
111	joko	1.1
112			v2 = graph.add_vertex()
113			vmap[v2] = '2'
114	joko	1.2	index['2'] = v2
115	joko	1.1
116			v3 = graph.add_vertex()
117			vmap[v3] = '3'
118	joko	1.2	index['3'] = v3
119	joko	1.1
120			v4 = graph.add_vertex()
121			vmap[v4] = '4'
122	joko	1.2	index['4'] = v4
123	joko	1.1
124			e1 = graph.add_edge(v1, v2)
125			e2 = graph.add_edge(v1, v3)
126			e3 = graph.add_edge(v3, v4)
127
128			"""
129			for vertex in graph.vertices:
130			#print vertex.id, vertex
131			print vmap[vertex], vertex
132			#print vertex.__getattribute__('id')
133			#print vertex['id']
134			#print vertex.get('id')
135			#print
136			"""
137
138			graph.write_graphviz('friends.dot')
139
140	joko	1.2	return (graph, index)
141	joko	1.1
142
143
144	joko	1.2	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	joko	1.1	def main():
161
162			# Load a graph from the GraphViz file 'mst.dot'
163			#graph = bgl.Graph.read_graphviz('mst.dot')
164	joko	1.2	(graph, index) = build_fixed_graph()
165	joko	1.1
166			# Compute all paths rooted from each vertex
167			#mst_edges = bgl.kruskal_minimum_spanning_tree(graph, weight)
168			#bgl.depth_first_search(graph, root_vertex = None, visitor = None, color_map = None)
169			for root in graph.vertices:
170			print
171			print '=' * 42
172			print 'Paths originating from node %s' % graph.vertex_properties['node_id'][root]
173			visitor = tree_edges_dfs_visitor(graph.vertex_properties['node_id'])
174			bgl.depth_first_search(graph, root_vertex = root, visitor = visitor, color_map = None)
175	joko	1.2
176			find_path_solutions(index['4'], index['2'], graph, visitor.paths)
177	joko	1.1
178			# STOP HERE
179			sys.exit(0)
180
181
182
183
184
185			# Compute the weight of the minimum spanning tree
186			#print 'MST weight =',sum([weight[e] for e in mst_edges])
187
188			# Put the weights into the label. Make MST edges solid while all other
189			# edges remain dashed.
190			label = graph.edge_property_map('string')
191			style = graph.edge_property_map('string')
192			for e in graph.edges:
193			label[e] = str(weight[e])
194			if e in mst_edges:
195			style[e] = 'solid'
196			else:
197			style[e] = 'dashed'
198
199			# Associate the label and style property maps with the graph for output
200			graph.edge_properties['label'] = label
201			graph.edge_properties['style'] = style
202
203			# Write out the graph in GraphViz DOT format
204			graph.write_graphviz('friends_path_2to3.dot')
205
206
207			if __name__ == '__main__':
208			main()
MailToCvsAdmin">MailToCvsAdmin	ViewVC Help
Powered by ViewVC 1.1.26