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	#!/usr/bin/env python
2
3	# $Id: boostgraph.py,v 1.1 2008/02/08 09:05:02 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 (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	# - 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
55	# for recognizing path switches
56	self.state = True
57
58	# for tracking paths
59	self.paths = []
60	self.current_path = []
61
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	self.current_path.append(e)
70	#return False
71
72	def start_vertex(self, v, g):
73	#self._seperator()
74	pass
75	#print 'sssss'
76
77	def initialize_vertex(self, v, g):
78	#print '>>>'
79	self._seperator('initialize_vertex')
80
81	def finish_vertex(self, v, g):
82	#print '<<<'
83	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, label = 'unknown'):
89	if self.state:
90	print '-' * 21, label
91	self.state = False
92
93
94	def build_fixed_graph():
95
96	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')
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	index['1'] = v1
111
112	v2 = graph.add_vertex()
113	vmap[v2] = '2'
114	index['2'] = v2
115
116	v3 = graph.add_vertex()
117	vmap[v3] = '3'
118	index['3'] = v3
119
120	v4 = graph.add_vertex()
121	vmap[v4] = '4'
122	index['4'] = v4
123
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	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():
161
162	# Load a graph from the GraphViz file 'mst.dot'
163	#graph = bgl.Graph.read_graphviz('mst.dot')
164	(graph, index) = build_fixed_graph()
165
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
176	find_path_solutions(index['4'], index['2'], graph, visitor.paths)
177
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