--- nfo/python/scripts/sixdegrees/boostgraph.py 2008/02/21 04:46:47 1.3 +++ nfo/python/scripts/sixdegrees/boostgraph.py 2008/02/26 10:11:13 1.6 @@ -1,6 +1,6 @@ #!/usr/bin/env python -# $Id: boostgraph.py,v 1.3 2008/02/21 04:46:47 joko Exp $ +# $Id: boostgraph.py,v 1.6 2008/02/26 10:11:13 joko Exp $ # (c) 2008 Andreas Motl # (c) 2008 Sebastian Utz @@ -38,10 +38,13 @@ RANDOM_MAX_NODES = 10 -RANDOM_MAX_CHILDREN_PER_NODE = 500 +RANDOM_MAX_CHILDREN_PER_NODE = 10 MAX_SEARCH_DEPTH = 50 +DEBUG = True +DEBUG = False + ENABLE_PROFILING = False if ENABLE_PROFILING: @@ -60,15 +63,19 @@ # from http://www.boost.org/libs/graph/doc/DFSVisitor.html -class tree_edges_dfs_visitor(bgl.dfs_visitor): +#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, maxdepth, name_map, color_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 @@ -87,10 +94,19 @@ 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.tree_edge2(e, g, 'examine_edge') + self._touch_edge(e, g, 'examine_edge') - def tree_edge2(self, e, g, label='tree_edge'): + def _touch_edge(self, e, g, label=''): (u, v) = (g.source(e), g.target(e)) @@ -106,25 +122,61 @@ 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 "Tree edge ", - print self.name_map[u], + print "%s:\t" % label, + #print "edge ", + print name_map[u], print " -> ", - print self.name_map[v] - sys.stdout.flush() - self.state = True - self.current_path.append(e) - #return False + 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') @@ -144,6 +196,7 @@ self.current_path = [] self.depth = 0 self._seperator('finish_vertex') + """ def _seperator(self, label = 'unknown'): if 1 or self.state: @@ -151,6 +204,144 @@ 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() @@ -186,8 +377,8 @@ e3 = graph.add_edge(v3, v4) e4 = graph.add_edge(v1, v4) - #e5 = graph.add_edge(v3, v2) - #e6 = graph.add_edge(v2, v4) + e5 = graph.add_edge(v2, v3) + e6 = graph.add_edge(v2, v4) """ for vertex in graph.vertices: @@ -261,6 +452,15 @@ 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 @@ -289,21 +489,52 @@ 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()) - #dump_graph(graph) + 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 @@ -316,11 +547,7 @@ #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) @@ -329,10 +556,13 @@ def doCompute(): cmap = graph.vertex_property_map('color') - visitor = tree_edges_dfs_visitor(MAX_SEARCH_DEPTH, graph.vertex_properties['node_id'], cmap) + 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) + #find_path_solutions(startVertex, endVertex, graph, visitor.paths) + print '-' * 42 + print "solution(s):" + print_path_solutions(graph, visitor.paths) if ENABLE_PROFILING: global paths