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	joko	1.1	#!/usr/bin/env python
2
3	joko	1.6	# $Id: boostgraph.py,v 1.5 2008/02/22 13:34:26 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	joko	1.6	RANDOM_MAX_CHILDREN_PER_NODE = 10
42	joko	1.3	MAX_SEARCH_DEPTH = 50
43
44
45	joko	1.6	DEBUG = True
46			DEBUG = False
47
48	joko	1.3	ENABLE_PROFILING = False
49
50			if ENABLE_PROFILING:
51			import profile
52			from profile import Profile
53
54
55	joko	1.1	import sys, os
56	joko	1.3	import random
57	joko	1.1
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	joko	1.6	#class tree_edges_dfs_visitor(bgl.dfs_visitor):
67			class dfs_visitor_debug(bgl.dfs_visitor):
68	joko	1.3	#class tree_edges_bfs_visitor(bgl.bfs_visitor):
69	joko	1.1
70	joko	1.4	def __init__(self, startVertex, endVertex, maxdepth, color_map):
71	joko	1.3
72	joko	1.5	print dir(self)
73	joko	1.3
74	joko	1.1	#bgl.dfs_visitor.__init__(self)
75	joko	1.4	#self.name_map = name_map
76
77			self.startVertex = startVertex
78			self.endVertex = endVertex
79	joko	1.2
80			# for recognizing path switches
81	joko	1.1	self.state = True
82	joko	1.2
83			# for tracking paths
84			self.paths = []
85			self.current_path = []
86	joko	1.3
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	joko	1.5	def back_edge(self, e, g):
98			self._touch_edge(e, g, 'back_edge')
99	joko	1.4
100	joko	1.5	def forward_or_cross_edge(self, e, g):
101			self._touch_edge(e, g, 'forward_or_cross_edge')
102	joko	1.4
103	joko	1.5	def tree_edge(self, e, g):
104			self._touch_edge(e, g, 'tree_edge')
105	joko	1.4
106	joko	1.3	def examine_edge(self, e, g):
107	joko	1.4	self._touch_edge(e, g, 'examine_edge')
108	joko	1.1
109	joko	1.4	def _touch_edge(self, e, g, label=''):
110	joko	1.3
111	joko	1.1	(u, v) = (g.source(e), g.target(e))
112	joko	1.3
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	joko	1.4
126			name_map = g.vertex_properties['node_id']
127	joko	1.3
128			if label:
129	joko	1.5	print "%s:\t" % label,
130			#print "edge ",
131	joko	1.4	print name_map[u],
132	joko	1.1	print " -> ",
133	joko	1.4	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	joko	1.5
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	joko	1.1
174	joko	1.4	"""
175	joko	1.1	def start_vertex(self, v, g):
176	joko	1.3	self._seperator('start_vertex')
177			#pass
178	joko	1.1	#print 'sssss'
179
180	joko	1.3	def discover_vertex(self, v, g):
181			#print '>>>'
182			self._seperator('discover_vertex')
183			#pass
184
185	joko	1.1	def initialize_vertex(self, v, g):
186			#print '>>>'
187	joko	1.2	self._seperator('initialize_vertex')
188	joko	1.1
189	joko	1.3	def examine_vertex(self, v, g):
190			self._seperator('examine_vertex')
191
192	joko	1.1	def finish_vertex(self, v, g):
193			#print '<<<'
194	joko	1.2	if self.current_path:
195			self.paths.append(self.current_path)
196			self.current_path = []
197	joko	1.3	self.depth = 0
198	joko	1.2	self._seperator('finish_vertex')
199	joko	1.4	"""
200	joko	1.1
201	joko	1.2	def _seperator(self, label = 'unknown'):
202	joko	1.3	if 1 or self.state:
203	joko	1.2	print '-' * 21, label
204	joko	1.1	self.state = False
205
206	joko	1.2
207	joko	1.6	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	joko	1.1	def build_fixed_graph():
346	joko	1.2
347	joko	1.1	graph = bgl.Graph()
348	joko	1.2	index = {}
349	joko	1.1
350	joko	1.2	# doesn't this work? see http://www.nabble.com/-Graph--Getting-PageRank-to-work-in-BGL-Python-td14207115.html
351	joko	1.1	#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	joko	1.2	index['1'] = v1
362	joko	1.1
363			v2 = graph.add_vertex()
364			vmap[v2] = '2'
365	joko	1.2	index['2'] = v2
366	joko	1.1
367			v3 = graph.add_vertex()
368			vmap[v3] = '3'
369	joko	1.2	index['3'] = v3
370	joko	1.1
371			v4 = graph.add_vertex()
372			vmap[v4] = '4'
373	joko	1.2	index['4'] = v4
374	joko	1.1
375			e1 = graph.add_edge(v1, v2)
376			e2 = graph.add_edge(v1, v3)
377			e3 = graph.add_edge(v3, v4)
378	joko	1.3
379			e4 = graph.add_edge(v1, v4)
380	joko	1.5	e5 = graph.add_edge(v2, v3)
381	joko	1.6	e6 = graph.add_edge(v2, v4)
382	joko	1.1
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	joko	1.2	return (graph, index)
396	joko	1.1
397
398	joko	1.3	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	joko	1.1
455	joko	1.4	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	joko	1.2	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	joko	1.3
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	joko	1.6
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	joko	1.2
513	joko	1.1	def main():
514
515			# Load a graph from the GraphViz file 'mst.dot'
516			#graph = bgl.Graph.read_graphviz('mst.dot')
517	joko	1.6
518			# 1. fixed graph with fixed required solution
519	joko	1.2	(graph, index) = build_fixed_graph()
520	joko	1.6	startIndex = '1'
521			endIndex = '4'
522
523			# 2. random graph with according solution
524	joko	1.3	#(graph, index) = build_random_graph()
525	joko	1.6	#startIndex = random.choice(index.keys())
526			#endIndex = random.choice(index.keys())
527	joko	1.3
528	joko	1.6	print '-' * 42
529			print "complete graph:"
530			dump_graph(graph)
531			print '-' * 42
532	joko	1.1
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	joko	1.3
537	joko	1.4	"""
538	joko	1.1	for root in graph.vertices:
539			print
540			print '=' * 42
541			print 'Paths originating from node %s' % graph.vertex_properties['node_id'][root]
542	joko	1.3	#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	joko	1.1	bgl.depth_first_search(graph, root_vertex = root, visitor = visitor, color_map = None)
547	joko	1.3	#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	joko	1.4	"""
551	joko	1.3
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	joko	1.4	visitor = tree_edges_dfs_visitor(startVertex, endVertex, MAX_SEARCH_DEPTH, cmap)
560	joko	1.3	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	joko	1.4	#find_path_solutions(startVertex, endVertex, graph, visitor.paths)
563	joko	1.6	print '-' * 42
564			print "solution(s):"
565			print_path_solutions(graph, visitor.paths)
566	joko	1.3
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	joko	1.1
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