--- nfo/python/scripts/sixdegrees/boostgraph.py 2008/02/21 01:54:28 1.2 +++ nfo/python/scripts/sixdegrees/boostgraph.py 2008/02/21 04:46:47 1.3 @@ -1,8 +1,9 @@ #!/usr/bin/env python -# $Id: boostgraph.py,v 1.2 2008/02/21 01:54:28 joko Exp $ +# $Id: boostgraph.py,v 1.3 2008/02/21 04:46:47 joko Exp $ # (c) 2008 Andreas Motl +# (c) 2008 Sebastian Utz # 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 @@ -36,7 +37,20 @@ # 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' @@ -47,8 +61,12 @@ # 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, name_map): + def __init__(self, maxdepth, name_map, color_map): + + print dir(self) + #bgl.dfs_visitor.__init__(self) self.name_map = name_map @@ -58,35 +76,77 @@ # 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_edge(self, e, g): + 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() - pass + 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 self.state: + if 1 or self.state: print '-' * 21, label self.state = False @@ -124,6 +184,10 @@ 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: @@ -140,6 +204,62 @@ 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): @@ -152,28 +272,77 @@ #(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" - + + 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] - visitor = tree_edges_dfs_visitor(graph.vertex_properties['node_id']) + #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) - - find_path_solutions(index['4'], index['2'], graph, visitor.paths) + #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)