--- nfo/python/scripts/sixdegrees/boostgraph.py 2008/02/22 13:34:26 1.5 +++ 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.5 2008/02/22 13:34:26 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,7 +63,8 @@ # 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, startVertex, endVertex, maxdepth, color_map): @@ -200,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() @@ -236,7 +378,7 @@ e4 = graph.add_edge(v1, v4) e5 = graph.add_edge(v2, v3) - #e6 = graph.add_edge(v2, v4) + e6 = graph.add_edge(v2, v4) """ for vertex in graph.vertices: @@ -347,16 +489,46 @@ 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) @@ -377,11 +549,6 @@ #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] @@ -393,9 +560,9 @@ 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) + print '-' * 42 + print "solution(s):" + print_path_solutions(graph, visitor.paths) if ENABLE_PROFILING: global paths