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>
# (c) 2008 Sebastian Utz <su@rotamente.com>

# 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/


RANDOM_MAX_NODES = 10
RANDOM_MAX_CHILDREN_PER_NODE = 500
MAX_SEARCH_DEPTH = 50


ENABLE_PROFILING = False

if ENABLE_PROFILING:
  import profile
  from profile import Profile


import sys, os
import random

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):
#class tree_edges_bfs_visitor(bgl.bfs_visitor):
  
  def __init__(self, maxdepth, name_map, color_map):
    
    print dir(self)
    
    #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 = []
    
    # for limiting search depth
    """
    self.color_map = color_map
    self.maxdepth = maxdepth
    self.depth = 0
    """
    
    self.level = 0
    

  def examine_edge(self, e, g):
    self.tree_edge2(e, g, 'examine_edge')

  def tree_edge2(self, e, g, label='tree_edge'):
    
    (u, v) = (g.source(e), g.target(e))
    
    # increase current search depth (level)
    """
    self.depth += 1
    
    # check if maximum depth reached
    if self.depth == self.maxdepth:
      # color all succeeding vertices to black (mark as "already visited")
      # BUG!!! marks too many nodes
      for child_edge in g.out_edges(v):
        end_vertex = g.target(child_edge)
        #self.color_map[end_vertex] = bgl.Color(bgl.Color.gray)
    """
      
    
    if label:
      print "%s:" % label,
    print "Tree edge ",
    print self.name_map[u],
    print " -> ",
    print self.name_map[v]
    sys.stdout.flush()
    self.state = True
    self.current_path.append(e)
    #return False

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


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

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

  def examine_vertex(self, v, g):
    self._seperator('examine_vertex')

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

  def _seperator(self, label = 'unknown'):
    if 1 or 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)
  
  e4 = graph.add_edge(v1, v4)
  #e5 = graph.add_edge(v3, v2)
  #e6 = graph.add_edge(v2, 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 build_random_graph():

  graph = bgl.Graph()
  index = {}

  vmap = graph.vertex_property_map('string')
  graph.vertex_properties['node_id'] = vmap

  count = 0
  for parent_id in range(1, RANDOM_MAX_NODES + 1):
    count += 1
    if count % 100 == 0:
      sys.stderr.write('.')
      
    parent_id_str = str(parent_id)
    v1New = False
    if not index.has_key(parent_id_str):
      #print "adding v1:", parent_id_str
      myVertex1 = graph.add_vertex()
      vmap[myVertex1] = parent_id_str
      index[parent_id_str] = myVertex1
      v1New = True

  
  count = 0
  #for j in range(1, random.randint(1, RANDOM_MAX_CHILDREN_PER_NODE)):
  for j in range(1, RANDOM_MAX_CHILDREN_PER_NODE):

    count += 1
    if count % 100 == 0:
      sys.stderr.write('.')

    parent_id_str = random.choice(index.keys())
    
    child_id_str = parent_id_str
    while child_id_str == parent_id_str:
      child_id_str = random.choice(index.keys())
      #print child_id_str
      
      myVertex1 = index[parent_id_str]
      myVertex2 = index[child_id_str]
      
      graph.add_edge(myVertex1, myVertex2)
        
  sys.stderr.write("\n")

  return (graph, index)


def dump_track(graph, track):
  track_ids = []
  for node in track:
    node_id = graph.vertex_properties['node_id'][node]
    track_ids.append(node_id)
  
  print ' -> '.join(track_ids)

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])
    
    track = []
    track.append(startVertex)
    
    for edge in path:
      endVertex = graph.target(edge)
      track.append(endVertex)
      if source == startVertex and target == endVertex:
        #print "found:", track
        dump_track(graph, track)

def dump_graph(graph):
  for edge in graph.edges:
    (u, v) = (graph.source(edge), graph.target(edge))
    startIndex = graph.vertex_properties['node_id'][u]
    endIndex = graph.vertex_properties['node_id'][v]
    print "%s -> %s" % (startIndex, endIndex)
    

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

  #dump_graph(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]
    #cmap = graph.vertex_property_map('color')
    cmap = None
    visitor = tree_edges_dfs_visitor(3, graph.vertex_properties['node_id'], cmap)
    #visitor = tree_edges_bfs_visitor(3, graph.vertex_properties['node_id'], cmap)
    bgl.depth_first_search(graph, root_vertex = root, visitor = visitor, color_map = None)
    #bgl.breadth_first_search(graph, root_vertex = root, visitor = visitor, color_map = None)
    #find_path_solutions(index['1'], index['4'], graph, visitor.paths)
  #sys.exit(0)

  startIndex = random.choice(index.keys())
  endIndex = random.choice(index.keys())
  startIndex = '1'
  endIndex = '4'

  print "Trying to find solution for: %s -> %s" % (startIndex, endIndex)

  startVertex = index[startIndex]
  endVertex = index[endIndex]

  def doCompute():
    cmap = graph.vertex_property_map('color')
    visitor = tree_edges_dfs_visitor(MAX_SEARCH_DEPTH, graph.vertex_properties['node_id'], cmap)
    bgl.depth_first_search(graph, root_vertex = startVertex, visitor = visitor, color_map = None)
    #bgl.depth_first_visit(graph, root_vertex = startVertex, visitor = visitor, color_map = cmap)
    find_path_solutions(startVertex, endVertex, graph, visitor.paths)

  if ENABLE_PROFILING:
    global paths
    paths = []
    p = Profile()
    p.runcall(doCompute)
    p.print_stats()
  else:
    paths = doCompute()

  
  # 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	joko	1.3	# (c) 2008 Sebastian Utz <su@rotamente.com>
7	joko	1.1
8			# 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
10			# the Free Software Foundation, either version 3 of the License, or
11			# (at your option) any later version.
12			#
13			# This program is distributed in the hope that it will be useful,
14			# but WITHOUT ANY WARRANTY; without even the implied warranty of
15			# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16			# GNU Affero General Public License for more details.
17			#
18			# You should have received a copy of the GNU Affero General Public License
19			# along with this program. If not, see <http://www.gnu.org/licenses/>.
20
21
22
23			# Uses BGL-Python (depth_first_search)
24			#
25			# BGL-Python Homepage: http://osl.iu.edu/~dgregor/bgl-python/
26			#
27	joko	1.2	# Documentation (Boost):
28			# - http://www.boost.org/libs/graph/doc/graph_theory_review.html
29			# - http://www.boost.org/libs/graph/doc/depth_first_search.html
30			# - http://www.boost.org/boost/graph/depth_first_search.hpp
31			# - http://www.boost.org/libs/graph/doc/DFSVisitor.html
32			# - http://www.boost.org/libs/graph/example/dfs-example.cpp
33			#
34			# Documentation (BGL-Python):
35	joko	1.1	# - http://osl.iu.edu/~dgregor/bgl-python/reference/boost.graph.html
36			#
37			# Subversion-Repository: https://svn.osl.iu.edu/svn/projects_viz/bgl-python/
38
39
40	joko	1.3	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	joko	1.1	import sys, os
53	joko	1.3	import random
54	joko	1.1
55			sys.path.append('bgl_python')
56			os.environ['PATH'] += ';' + './bgl_python'
57
58			import boost.graph as bgl
59
60
61
62			# from http://www.boost.org/libs/graph/doc/DFSVisitor.html
63			class tree_edges_dfs_visitor(bgl.dfs_visitor):
64	joko	1.3	#class tree_edges_bfs_visitor(bgl.bfs_visitor):
65	joko	1.1
66	joko	1.3	def __init__(self, maxdepth, name_map, color_map):
67
68			print dir(self)
69
70	joko	1.1	#bgl.dfs_visitor.__init__(self)
71			self.name_map = name_map
72	joko	1.2
73			# for recognizing path switches
74	joko	1.1	self.state = True
75	joko	1.2
76			# for tracking paths
77			self.paths = []
78			self.current_path = []
79	joko	1.3
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	joko	1.1
93	joko	1.3	def tree_edge2(self, e, g, label='tree_edge'):
94
95	joko	1.1	(u, v) = (g.source(e), g.target(e))
96	joko	1.3
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	joko	1.1	print "Tree edge ",
114			print self.name_map[u],
115			print " -> ",
116			print self.name_map[v]
117	joko	1.3	sys.stdout.flush()
118	joko	1.1	self.state = True
119	joko	1.2	self.current_path.append(e)
120			#return False
121	joko	1.1
122			def start_vertex(self, v, g):
123	joko	1.3	self._seperator('start_vertex')
124			#pass
125	joko	1.1	#print 'sssss'
126
127	joko	1.3
128			def discover_vertex(self, v, g):
129			#print '>>>'
130			self._seperator('discover_vertex')
131			#pass
132
133	joko	1.1	def initialize_vertex(self, v, g):
134			#print '>>>'
135	joko	1.2	self._seperator('initialize_vertex')
136	joko	1.1
137	joko	1.3	def examine_vertex(self, v, g):
138			self._seperator('examine_vertex')
139
140	joko	1.1	def finish_vertex(self, v, g):
141			#print '<<<'
142	joko	1.2	if self.current_path:
143			self.paths.append(self.current_path)
144			self.current_path = []
145	joko	1.3	self.depth = 0
146	joko	1.2	self._seperator('finish_vertex')
147	joko	1.1
148	joko	1.2	def _seperator(self, label = 'unknown'):
149	joko	1.3	if 1 or self.state:
150	joko	1.2	print '-' * 21, label
151	joko	1.1	self.state = False
152
153	joko	1.2
154	joko	1.1	def build_fixed_graph():
155	joko	1.2
156	joko	1.1	graph = bgl.Graph()
157	joko	1.2	index = {}
158	joko	1.1
159	joko	1.2	# doesn't this work? see http://www.nabble.com/-Graph--Getting-PageRank-to-work-in-BGL-Python-td14207115.html
160	joko	1.1	#graph.add_vertex_property_map(name='my_name', type='float')
161
162			# 'write_graphviz' requires property 'node_id' on vertices
163			# see http://lists.boost.org/boost-users/2006/06/19877.php
164			vmap = graph.vertex_property_map('string')
165			graph.vertex_properties['node_id'] = vmap
166
167
168			v1 = graph.add_vertex()
169			vmap[v1] = '1'
170	joko	1.2	index['1'] = v1
171	joko	1.1
172			v2 = graph.add_vertex()
173			vmap[v2] = '2'
174	joko	1.2	index['2'] = v2
175	joko	1.1
176			v3 = graph.add_vertex()
177			vmap[v3] = '3'
178	joko	1.2	index['3'] = v3
179	joko	1.1
180			v4 = graph.add_vertex()
181			vmap[v4] = '4'
182	joko	1.2	index['4'] = v4
183	joko	1.1
184			e1 = graph.add_edge(v1, v2)
185			e2 = graph.add_edge(v1, v3)
186			e3 = graph.add_edge(v3, v4)
187	joko	1.3
188			e4 = graph.add_edge(v1, v4)
189			#e5 = graph.add_edge(v3, v2)
190			#e6 = graph.add_edge(v2, v4)
191	joko	1.1
192			"""
193			for vertex in graph.vertices:
194			#print vertex.id, vertex
195			print vmap[vertex], vertex
196			#print vertex.__getattribute__('id')
197			#print vertex['id']
198			#print vertex.get('id')
199			#print
200			"""
201
202			graph.write_graphviz('friends.dot')
203
204	joko	1.2	return (graph, index)
205	joko	1.1
206
207	joko	1.3	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	joko	1.1
264	joko	1.2	def find_path_solutions(source, target, graph, paths):
265
266			print
267			print "=" * 42
268			print "find_path_solutions"
269			print "=" * 42
270
271			#print visitor.paths
272			#(u, v) = (g.source(e), g.target(e))
273			for path in paths:
274			startVertex = graph.source(path[0])
275	joko	1.3
276			track = []
277			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	joko	1.2
294	joko	1.1	def main():
295
296			# Load a graph from the GraphViz file 'mst.dot'
297			#graph = bgl.Graph.read_graphviz('mst.dot')
298	joko	1.2	(graph, index) = build_fixed_graph()
299	joko	1.3	#(graph, index) = build_random_graph()
300
301			#dump_graph(graph)
302	joko	1.1
303			# Compute all paths rooted from each vertex
304			#mst_edges = bgl.kruskal_minimum_spanning_tree(graph, weight)
305			#bgl.depth_first_search(graph, root_vertex = None, visitor = None, color_map = None)
306	joko	1.3
307	joko	1.1	for root in graph.vertices:
308			print
309			print '=' * 42
310			print 'Paths originating from node %s' % graph.vertex_properties['node_id'][root]
311	joko	1.3	#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	joko	1.1	bgl.depth_first_search(graph, root_vertex = root, visitor = visitor, color_map = None)
316	joko	1.3	#bgl.breadth_first_search(graph, root_vertex = root, visitor = visitor, color_map = None)
317			#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	joko	1.1
347			# STOP HERE
348			sys.exit(0)
349
350
351
352
353
354			# Compute the weight of the minimum spanning tree
355			#print 'MST weight =',sum([weight[e] for e in mst_edges])
356
357			# Put the weights into the label. Make MST edges solid while all other
358			# edges remain dashed.
359			label = graph.edge_property_map('string')
360			style = graph.edge_property_map('string')
361			for e in graph.edges:
362			label[e] = str(weight[e])
363			if e in mst_edges:
364			style[e] = 'solid'
365			else:
366			style[e] = 'dashed'
367
368			# Associate the label and style property maps with the graph for output
369			graph.edge_properties['label'] = label
370			graph.edge_properties['style'] = style
371
372			# Write out the graph in GraphViz DOT format
373			graph.write_graphviz('friends_path_2to3.dot')
374
375
376			if __name__ == '__main__':
377			main()
MailToCvsAdmin">MailToCvsAdmin	ViewVC Help
Powered by ViewVC 1.1.26