scripts/sixdegrees/boostgraph.py

#!/usr/bin/env python

# $Id: boostgraph.py,v 1.5 2008/02/22 13:34:26 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 = 10
MAX_SEARCH_DEPTH = 50


DEBUG = True
DEBUG = False

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 dfs_visitor_debug(bgl.dfs_visitor):
#class tree_edges_bfs_visitor(bgl.bfs_visitor):
  
  def __init__(self, startVertex, endVertex, maxdepth, color_map):
    
    print dir(self)
    
    #bgl.dfs_visitor.__init__(self)
    #self.name_map = name_map
    
    self.startVertex = startVertex
    self.endVertex = endVertex
    
    # 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 back_edge(self, e, g):
    self._touch_edge(e, g, 'back_edge')

  def forward_or_cross_edge(self, e, g):
    self._touch_edge(e, g, 'forward_or_cross_edge')

  def tree_edge(self, e, g):
    self._touch_edge(e, g, 'tree_edge')

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

  def _touch_edge(self, e, g, label=''):
    
    (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)
    """
    
    name_map = g.vertex_properties['node_id']
    
    if label:
      print "%s:\t" % label,
    #print "edge ",
    print name_map[u],
    print " -> ",
    print name_map[v]
    
    #self.state = True
    
    if u == self.startVertex:
      print "starting"
      self.current_path = []

    # skip circular references
    if v != self.startVertex:
      self.current_path.append(e)

    if v == self.endVertex and self.current_path:
      print "found:"
      print self.current_path
      self.paths.append(self.current_path)
      self.current_path = []


  def _touch_vertex(self, v, g, label=''):
    name_map = g.vertex_properties['node_id']
    id = name_map[v]
    print '%s:\t%s' % (label, id)


  def start_vertex(self, v, g):
    self._touch_vertex(v, g, 'start_vertex')

  def discover_vertex(self, v, g):
    self._touch_vertex(v, g, 'discover_vertex')

  def initialize_vertex(self, v, g):
    self._touch_vertex(v, g, 'initialize_vertex')

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

  def finish_vertex(self, v, g):
    self._touch_vertex(v, g, 'finish_vertex')


  """
  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


class tree_edges_dfs_visitor(bgl.dfs_visitor):

  def __init__(self, startVertex, endVertex, maxdepth, color_map):
    
    #print dir(self)
    
    #bgl.dfs_visitor.__init__(self)
    #self.name_map = name_map
    
    self.startVertex = startVertex
    self.endVertex = endVertex
    
    # 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 tree_edge(self, e, g):
    self._touch_edge(e, g, 'tree_edge')

  def forward_or_cross_edge(self, e, g):
    #self._touch_edge(e, g, 'forward_or_cross_edge')
    self.find_new_variations_from_source(e, g)
    self.find_new_variations_to_target(e, g)

  
  def find_new_variations_from_source(self, e, g):
    # find additional solutions as parts of already established ones (e.g. shortcuts)
    localEndVertex = g.target(e)
    path_additional = []
    for path in self.paths:
      found = False
      for edge in path:
        if found:
          path_additional.append(edge)
        else:
          if g.source(edge) == localEndVertex:
            #print "found2"
            found = True
            path_additional.append(e)
            path_additional.append(edge)
    
    #print "find_new_variations_from_source:", path_additional
    if path_additional:
      self.paths.append(path_additional)

  def find_new_variations_to_target(self, e, g):
    # find additional solutions as parts of already established ones (e.g. shortcuts)
    localStartVertex = g.source(e)
    localEndVertex = g.target(e)
    
    #return
    
    #if not (self.endVertex == localEndVertex and self.startVertex != localStartVertex):
    if not (self.endVertex == localEndVertex):
      return
    
    # find "direct" solution (start- and end-vertices are directly connected)
    if self.startVertex == localStartVertex:
      self.paths.append([e])
      return
    
    #print "check"
    path_additional = []
    for path_iter in self.paths:
      found = False
      path = list(path_iter)
      path.reverse()
      for edge in path:
        if found:
          path_additional.insert(0, edge)
        else:
          if g.target(edge) == localStartVertex:
            #print "found2"
            found = True
            path_additional.append(e)
            path_additional.insert(0, edge)
    
    #print "find_new_variations_to_target:", path_additional
    if path_additional:
      self.paths.append(path_additional)

  def _touch_edge(self, e, g, label=''):
    
    (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)
    """
    
    name_map = g.vertex_properties['node_id']
    
    if DEBUG:
      if label:
        print "%s:\t" % label,
      #print "edge ",
      print name_map[u],
      print " -> ",
      print name_map[v]
    
    #self.state = True
    
    if u == self.startVertex:
      #print "starting"
      self.current_path = []

    # skip circular references
    if v != self.startVertex:
      self.current_path.append(e)

    # finish current path if target found
    if v == self.endVertex and self.current_path:
      #print "found:"
      #print self.current_path
      self.paths.append(self.current_path)
      self.current_path = []


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(v2, v3)
  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 dump_edges(g, edges):
  name_map = g.vertex_properties['node_id']
  for e in edges:
    (u, v) = (g.source(e), g.target(e))
    print "edge ",
    print name_map[u],
    print " -> ",
    print name_map[v]

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 dump_edges_vertices(graph, edge_list):
  startVertex = graph.source(edge_list[0])
  
  track = []
  track.append(startVertex)

  for edge in edge_list:
    endVertex = graph.target(edge)
    track.append(endVertex)
  dump_track(graph, track)

def print_path_solutions(graph, paths):
  for path in paths:
    if DEBUG:
      print '-' * 21
      dump_edges(graph, path)
    dump_edges_vertices(graph, path)


def main():
  
  # Load a graph from the GraphViz file 'mst.dot'
  #graph = bgl.Graph.read_graphviz('mst.dot')
  
  # 1. fixed graph with fixed required solution
  (graph, index) = build_fixed_graph()
  startIndex = '1'
  endIndex = '4'
  
  # 2. random graph with according solution
  #(graph, index) = build_random_graph()
  #startIndex = random.choice(index.keys())
  #endIndex = random.choice(index.keys())

  print '-' * 42
  print "complete graph:"
  dump_graph(graph)
  print '-' * 42

  # 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)
  """

  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(startVertex, endVertex, MAX_SEARCH_DEPTH, 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)
    print '-' * 42
    print "solution(s):"
    print_path_solutions(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	#!/usr/bin/env python
2
3	# $Id: boostgraph.py,v 1.5 2008/02/22 13:34:26 joko Exp $
4
5	# (c) 2008 Andreas Motl <andreas.motl@ilo.de>
6	# (c) 2008 Sebastian Utz <su@rotamente.com>
7
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	# 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	# - 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	RANDOM_MAX_NODES = 10
41	RANDOM_MAX_CHILDREN_PER_NODE = 10
42	MAX_SEARCH_DEPTH = 50
43
44
45	DEBUG = True
46	DEBUG = False
47
48	ENABLE_PROFILING = False
49
50	if ENABLE_PROFILING:
51	import profile
52	from profile import Profile
53
54
55	import sys, os
56	import random
57
58	sys.path.append('bgl_python')
59	os.environ['PATH'] += ';' + './bgl_python'
60
61	import boost.graph as bgl
62
63
64
65	# from http://www.boost.org/libs/graph/doc/DFSVisitor.html
66	#class tree_edges_dfs_visitor(bgl.dfs_visitor):
67	class dfs_visitor_debug(bgl.dfs_visitor):
68	#class tree_edges_bfs_visitor(bgl.bfs_visitor):
69
70	def __init__(self, startVertex, endVertex, maxdepth, color_map):
71
72	print dir(self)
73
74	#bgl.dfs_visitor.__init__(self)
75	#self.name_map = name_map
76
77	self.startVertex = startVertex
78	self.endVertex = endVertex
79
80	# for recognizing path switches
81	self.state = True
82
83	# for tracking paths
84	self.paths = []
85	self.current_path = []
86
87	# for limiting search depth
88	"""
89	self.color_map = color_map
90	self.maxdepth = maxdepth
91	self.depth = 0
92	"""
93
94	self.level = 0
95
96
97	def back_edge(self, e, g):
98	self._touch_edge(e, g, 'back_edge')
99
100	def forward_or_cross_edge(self, e, g):
101	self._touch_edge(e, g, 'forward_or_cross_edge')
102
103	def tree_edge(self, e, g):
104	self._touch_edge(e, g, 'tree_edge')
105
106	def examine_edge(self, e, g):
107	self._touch_edge(e, g, 'examine_edge')
108
109	def _touch_edge(self, e, g, label=''):
110
111	(u, v) = (g.source(e), g.target(e))
112
113	# increase current search depth (level)
114	"""
115	self.depth += 1
116
117	# check if maximum depth reached
118	if self.depth == self.maxdepth:
119	# color all succeeding vertices to black (mark as "already visited")
120	# BUG!!! marks too many nodes
121	for child_edge in g.out_edges(v):
122	end_vertex = g.target(child_edge)
123	#self.color_map[end_vertex] = bgl.Color(bgl.Color.gray)
124	"""
125
126	name_map = g.vertex_properties['node_id']
127
128	if label:
129	print "%s:\t" % label,
130	#print "edge ",
131	print name_map[u],
132	print " -> ",
133	print name_map[v]
134
135	#self.state = True
136
137	if u == self.startVertex:
138	print "starting"
139	self.current_path = []
140
141	# skip circular references
142	if v != self.startVertex:
143	self.current_path.append(e)
144
145	if v == self.endVertex and self.current_path:
146	print "found:"
147	print self.current_path
148	self.paths.append(self.current_path)
149	self.current_path = []
150
151
152	def _touch_vertex(self, v, g, label=''):
153	name_map = g.vertex_properties['node_id']
154	id = name_map[v]
155	print '%s:\t%s' % (label, id)
156
157
158	def start_vertex(self, v, g):
159	self._touch_vertex(v, g, 'start_vertex')
160
161	def discover_vertex(self, v, g):
162	self._touch_vertex(v, g, 'discover_vertex')
163
164	def initialize_vertex(self, v, g):
165	self._touch_vertex(v, g, 'initialize_vertex')
166
167	def examine_vertex(self, v, g):
168	self._touch_vertex(v, g, 'examine_vertex')
169
170	def finish_vertex(self, v, g):
171	self._touch_vertex(v, g, 'finish_vertex')
172
173
174	"""
175	def start_vertex(self, v, g):
176	self._seperator('start_vertex')
177	#pass
178	#print 'sssss'
179
180	def discover_vertex(self, v, g):
181	#print '>>>'
182	self._seperator('discover_vertex')
183	#pass
184
185	def initialize_vertex(self, v, g):
186	#print '>>>'
187	self._seperator('initialize_vertex')
188
189	def examine_vertex(self, v, g):
190	self._seperator('examine_vertex')
191
192	def finish_vertex(self, v, g):
193	#print '<<<'
194	if self.current_path:
195	self.paths.append(self.current_path)
196	self.current_path = []
197	self.depth = 0
198	self._seperator('finish_vertex')
199	"""
200
201	def _seperator(self, label = 'unknown'):
202	if 1 or self.state:
203	print '-' * 21, label
204	self.state = False
205
206
207	class tree_edges_dfs_visitor(bgl.dfs_visitor):
208
209	def __init__(self, startVertex, endVertex, maxdepth, color_map):
210
211	#print dir(self)
212
213	#bgl.dfs_visitor.__init__(self)
214	#self.name_map = name_map
215
216	self.startVertex = startVertex
217	self.endVertex = endVertex
218
219	# for recognizing path switches
220	self.state = True
221
222	# for tracking paths
223	self.paths = []
224	self.current_path = []
225
226	# for limiting search depth
227	"""
228	self.color_map = color_map
229	self.maxdepth = maxdepth
230	self.depth = 0
231	"""
232
233	self.level = 0
234
235	def tree_edge(self, e, g):
236	self._touch_edge(e, g, 'tree_edge')
237
238	def forward_or_cross_edge(self, e, g):
239	#self._touch_edge(e, g, 'forward_or_cross_edge')
240	self.find_new_variations_from_source(e, g)
241	self.find_new_variations_to_target(e, g)
242
243
244	def find_new_variations_from_source(self, e, g):
245	# find additional solutions as parts of already established ones (e.g. shortcuts)
246	localEndVertex = g.target(e)
247	path_additional = []
248	for path in self.paths:
249	found = False
250	for edge in path:
251	if found:
252	path_additional.append(edge)
253	else:
254	if g.source(edge) == localEndVertex:
255	#print "found2"
256	found = True
257	path_additional.append(e)
258	path_additional.append(edge)
259
260	#print "find_new_variations_from_source:", path_additional
261	if path_additional:
262	self.paths.append(path_additional)
263
264	def find_new_variations_to_target(self, e, g):
265	# find additional solutions as parts of already established ones (e.g. shortcuts)
266	localStartVertex = g.source(e)
267	localEndVertex = g.target(e)
268
269	#return
270
271	#if not (self.endVertex == localEndVertex and self.startVertex != localStartVertex):
272	if not (self.endVertex == localEndVertex):
273	return
274
275	# find "direct" solution (start- and end-vertices are directly connected)
276	if self.startVertex == localStartVertex:
277	self.paths.append([e])
278	return
279
280	#print "check"
281	path_additional = []
282	for path_iter in self.paths:
283	found = False
284	path = list(path_iter)
285	path.reverse()
286	for edge in path:
287	if found:
288	path_additional.insert(0, edge)
289	else:
290	if g.target(edge) == localStartVertex:
291	#print "found2"
292	found = True
293	path_additional.append(e)
294	path_additional.insert(0, edge)
295
296	#print "find_new_variations_to_target:", path_additional
297	if path_additional:
298	self.paths.append(path_additional)
299
300	def _touch_edge(self, e, g, label=''):
301
302	(u, v) = (g.source(e), g.target(e))
303
304	# increase current search depth (level)
305	"""
306	self.depth += 1
307
308	# check if maximum depth reached
309	if self.depth == self.maxdepth:
310	# color all succeeding vertices to black (mark as "already visited")
311	# BUG!!! marks too many nodes
312	for child_edge in g.out_edges(v):
313	end_vertex = g.target(child_edge)
314	#self.color_map[end_vertex] = bgl.Color(bgl.Color.gray)
315	"""
316
317	name_map = g.vertex_properties['node_id']
318
319	if DEBUG:
320	if label:
321	print "%s:\t" % label,
322	#print "edge ",
323	print name_map[u],
324	print " -> ",
325	print name_map[v]
326
327	#self.state = True
328
329	if u == self.startVertex:
330	#print "starting"
331	self.current_path = []
332
333	# skip circular references
334	if v != self.startVertex:
335	self.current_path.append(e)
336
337	# finish current path if target found
338	if v == self.endVertex and self.current_path:
339	#print "found:"
340	#print self.current_path
341	self.paths.append(self.current_path)
342	self.current_path = []
343
344
345	def build_fixed_graph():
346
347	graph = bgl.Graph()
348	index = {}
349
350	# doesn't this work? see http://www.nabble.com/-Graph--Getting-PageRank-to-work-in-BGL-Python-td14207115.html
351	#graph.add_vertex_property_map(name='my_name', type='float')
352
353	# 'write_graphviz' requires property 'node_id' on vertices
354	# see http://lists.boost.org/boost-users/2006/06/19877.php
355	vmap = graph.vertex_property_map('string')
356	graph.vertex_properties['node_id'] = vmap
357
358
359	v1 = graph.add_vertex()
360	vmap[v1] = '1'
361	index['1'] = v1
362
363	v2 = graph.add_vertex()
364	vmap[v2] = '2'
365	index['2'] = v2
366
367	v3 = graph.add_vertex()
368	vmap[v3] = '3'
369	index['3'] = v3
370
371	v4 = graph.add_vertex()
372	vmap[v4] = '4'
373	index['4'] = v4
374
375	e1 = graph.add_edge(v1, v2)
376	e2 = graph.add_edge(v1, v3)
377	e3 = graph.add_edge(v3, v4)
378
379	e4 = graph.add_edge(v1, v4)
380	e5 = graph.add_edge(v2, v3)
381	e6 = graph.add_edge(v2, v4)
382
383	"""
384	for vertex in graph.vertices:
385	#print vertex.id, vertex
386	print vmap[vertex], vertex
387	#print vertex.__getattribute__('id')
388	#print vertex['id']
389	#print vertex.get('id')
390	#print
391	"""
392
393	graph.write_graphviz('friends.dot')
394
395	return (graph, index)
396
397
398	def build_random_graph():
399
400	graph = bgl.Graph()
401	index = {}
402
403	vmap = graph.vertex_property_map('string')
404	graph.vertex_properties['node_id'] = vmap
405
406	count = 0
407	for parent_id in range(1, RANDOM_MAX_NODES + 1):
408	count += 1
409	if count % 100 == 0:
410	sys.stderr.write('.')
411
412	parent_id_str = str(parent_id)
413	v1New = False
414	if not index.has_key(parent_id_str):
415	#print "adding v1:", parent_id_str
416	myVertex1 = graph.add_vertex()
417	vmap[myVertex1] = parent_id_str
418	index[parent_id_str] = myVertex1
419	v1New = True
420
421
422	count = 0
423	#for j in range(1, random.randint(1, RANDOM_MAX_CHILDREN_PER_NODE)):
424	for j in range(1, RANDOM_MAX_CHILDREN_PER_NODE):
425
426	count += 1
427	if count % 100 == 0:
428	sys.stderr.write('.')
429
430	parent_id_str = random.choice(index.keys())
431
432	child_id_str = parent_id_str
433	while child_id_str == parent_id_str:
434	child_id_str = random.choice(index.keys())
435	#print child_id_str
436
437	myVertex1 = index[parent_id_str]
438	myVertex2 = index[child_id_str]
439
440	graph.add_edge(myVertex1, myVertex2)
441
442	sys.stderr.write("\n")
443
444	return (graph, index)
445
446
447	def dump_track(graph, track):
448	track_ids = []
449	for node in track:
450	node_id = graph.vertex_properties['node_id'][node]
451	track_ids.append(node_id)
452
453	print ' -> '.join(track_ids)
454
455	def dump_edges(g, edges):
456	name_map = g.vertex_properties['node_id']
457	for e in edges:
458	(u, v) = (g.source(e), g.target(e))
459	print "edge ",
460	print name_map[u],
461	print " -> ",
462	print name_map[v]
463
464	def find_path_solutions(source, target, graph, paths):
465
466	print
467	print "=" * 42
468	print "find_path_solutions"
469	print "=" * 42
470
471	#print visitor.paths
472	#(u, v) = (g.source(e), g.target(e))
473	for path in paths:
474	startVertex = graph.source(path[0])
475
476	track = []
477	track.append(startVertex)
478
479	for edge in path:
480	endVertex = graph.target(edge)
481	track.append(endVertex)
482	if source == startVertex and target == endVertex:
483	#print "found:", track
484	dump_track(graph, track)
485
486	def dump_graph(graph):
487	for edge in graph.edges:
488	(u, v) = (graph.source(edge), graph.target(edge))
489	startIndex = graph.vertex_properties['node_id'][u]
490	endIndex = graph.vertex_properties['node_id'][v]
491	print "%s -> %s" % (startIndex, endIndex)
492
493	def dump_edges_vertices(graph, edge_list):
494	startVertex = graph.source(edge_list[0])
495
496	track = []
497	track.append(startVertex)
498
499	for edge in edge_list:
500	endVertex = graph.target(edge)
501	track.append(endVertex)
502	dump_track(graph, track)
503
504	def print_path_solutions(graph, paths):
505	for path in paths:
506	if DEBUG:
507	print '-' * 21
508	dump_edges(graph, path)
509	dump_edges_vertices(graph, path)
510
511
512
513	def main():
514
515	# Load a graph from the GraphViz file 'mst.dot'
516	#graph = bgl.Graph.read_graphviz('mst.dot')
517
518	# 1. fixed graph with fixed required solution
519	(graph, index) = build_fixed_graph()
520	startIndex = '1'
521	endIndex = '4'
522
523	# 2. random graph with according solution
524	#(graph, index) = build_random_graph()
525	#startIndex = random.choice(index.keys())
526	#endIndex = random.choice(index.keys())
527
528	print '-' * 42
529	print "complete graph:"
530	dump_graph(graph)
531	print '-' * 42
532
533	# Compute all paths rooted from each vertex
534	#mst_edges = bgl.kruskal_minimum_spanning_tree(graph, weight)
535	#bgl.depth_first_search(graph, root_vertex = None, visitor = None, color_map = None)
536
537	"""
538	for root in graph.vertices:
539	print
540	print '=' * 42
541	print 'Paths originating from node %s' % graph.vertex_properties['node_id'][root]
542	#cmap = graph.vertex_property_map('color')
543	cmap = None
544	visitor = tree_edges_dfs_visitor(3, graph.vertex_properties['node_id'], cmap)
545	#visitor = tree_edges_bfs_visitor(3, graph.vertex_properties['node_id'], cmap)
546	bgl.depth_first_search(graph, root_vertex = root, visitor = visitor, color_map = None)
547	#bgl.breadth_first_search(graph, root_vertex = root, visitor = visitor, color_map = None)
548	#find_path_solutions(index['1'], index['4'], graph, visitor.paths)
549	#sys.exit(0)
550	"""
551
552	print "Trying to find solution for: %s -> %s" % (startIndex, endIndex)
553
554	startVertex = index[startIndex]
555	endVertex = index[endIndex]
556
557	def doCompute():
558	cmap = graph.vertex_property_map('color')
559	visitor = tree_edges_dfs_visitor(startVertex, endVertex, MAX_SEARCH_DEPTH, cmap)
560	bgl.depth_first_search(graph, root_vertex = startVertex, visitor = visitor, color_map = None)
561	#bgl.depth_first_visit(graph, root_vertex = startVertex, visitor = visitor, color_map = cmap)
562	#find_path_solutions(startVertex, endVertex, graph, visitor.paths)
563	print '-' * 42
564	print "solution(s):"
565	print_path_solutions(graph, visitor.paths)
566
567	if ENABLE_PROFILING:
568	global paths
569	paths = []
570	p = Profile()
571	p.runcall(doCompute)
572	p.print_stats()
573	else:
574	paths = doCompute()
575
576
577	# STOP HERE
578	sys.exit(0)
579
580
581
582
583
584	# Compute the weight of the minimum spanning tree
585	#print 'MST weight =',sum([weight[e] for e in mst_edges])
586
587	# Put the weights into the label. Make MST edges solid while all other
588	# edges remain dashed.
589	label = graph.edge_property_map('string')
590	style = graph.edge_property_map('string')
591	for e in graph.edges:
592	label[e] = str(weight[e])
593	if e in mst_edges:
594	style[e] = 'solid'
595	else:
596	style[e] = 'dashed'
597
598	# Associate the label and style property maps with the graph for output
599	graph.edge_properties['label'] = label
600	graph.edge_properties['style'] = style
601
602	# Write out the graph in GraphViz DOT format
603	graph.write_graphviz('friends_path_2to3.dot')
604
605
606	if __name__ == '__main__':
607	main()
MailToCvsAdmin">MailToCvsAdmin	ViewVC Help
Powered by ViewVC 1.1.26