--- nfo/python/scripts/sixdegrees/boostgraph.py 2008/02/08 09:05:02 1.1 +++ nfo/python/scripts/sixdegrees/boostgraph.py 2008/02/21 11:29:07 1.4 @@ -1,8 +1,9 @@ #!/usr/bin/env python -# $Id: boostgraph.py,v 1.1 2008/02/08 09:05:02 joko Exp $ +# $Id: boostgraph.py,v 1.4 2008/02/21 11:29:07 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 @@ -23,14 +24,33 @@ # # BGL-Python Homepage: http://osl.iu.edu/~dgregor/bgl-python/ # -# Documentation: -# - http://osl.iu.edu/~dgregor/bgl-python/reference/boost.graph.html +# 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' @@ -41,40 +61,129 @@ # 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, startVertex, endVertex, maxdepth, color_map): + + #print dir(self) + #bgl.dfs_visitor.__init__(self) - self.name_map = name_map + #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.tree_edge(e, g, 'back_edge') + + #def forward_or_cross_edge(self, e, g): + # self.tree_edge(e, g, 'forward_or_cross_edge') + + #def tree_edge(self, e, g): + # self.tree_edge(e, g, 'examine_edge') - def tree_edge(self, e, g): + 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)) - print "Tree edge ", - print self.name_map[u], + + # 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:" % label, + print "edge ", + print name_map[u], print " -> ", - print self.name_map[v] - self.state = True + 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 start_vertex(self, v, g): + self._seperator('start_vertex') + #pass #print 'sssss' - self._seperator() + + def discover_vertex(self, v, g): + #print '>>>' + self._seperator('discover_vertex') + #pass def initialize_vertex(self, v, g): #print '>>>' - self._seperator() + self._seperator('initialize_vertex') + + def examine_vertex(self, v, g): + self._seperator('examine_vertex') def finish_vertex(self, v, g): #print '<<<' - self._seperator() + if self.current_path: + self.paths.append(self.current_path) + self.current_path = [] + self.depth = 0 + self._seperator('finish_vertex') + """ - def _seperator(self): - if self.state: - print '-' * 21 + 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 @@ -85,19 +194,27 @@ 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: @@ -111,26 +228,162 @@ graph.write_graphviz('friends.dot') - return graph + 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 main(): # Load a graph from the GraphViz file 'mst.dot' #graph = bgl.Graph.read_graphviz('mst.dot') - graph = build_fixed_graph() + (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) - + #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(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) + for path in visitor.paths: + print '-' * 21 + dump_edges(graph, path) + + if ENABLE_PROFILING: + global paths + paths = [] + p = Profile() + p.runcall(doCompute) + p.print_stats() + else: + paths = doCompute() + # STOP HERE sys.exit(0)