Computing a path while traversing a graph with a search algorithm
Hi folks, I've written a program which makes use of the Boost Graph library to construct a graph. I've then attached properties to both the vertices and edges, giving a result like this: http://www-users.york.ac.uk/~rl522/test.pdf However, I want to now search the graph in order to do this: 1. When the edge is the last, i.e. the outdegree of the target is 0: 2. Total the edge values for all the edges followed to get here all the way back to the root, and add 19. 3. If this total is the same value as the root node value, set a particular property on each vertex those edges are connected to. I've tried a depth_first_search using a Visitor. I wanted to push each edge onto a temporary vector as I found it, and then pop it when the algorithm backtracked, but this doesn't work. The aim here was to know the path taken to get to a particular edge when that edge was found. I'm completely new to using graphs (I'm actually a Biologist), and I think I'm missing how I should really be using the depth_first_search or breadth_first_search visitors to do what I need. It also doesn't appear to like me using the visitor to alter the properties on the vertices or edges during the search. Is this allowed? I'm not altering the graph, just wanting to set a few property values (internally stored, in this case). I would be very grateful for any ideas or suggestions for approaching this problem. Many thanks, Roger Leigh PS. This is the visitor I wrote, but this appears to be completely wrong. The full source is at http://www-users.york.ac.uk/~rl522/massgraph-0.1.0.tar.gz (ms_analysis.cc|h). class peak_visitor : public boost::default_dfs_visitor { public: peak_visitor(double target_mass, ms_analysis::vertex_set& vs, std::vector<ms_analysis::edge_stack>& v): target_mass(target_mass), vs(vs), v(v), s() {} template < typename Edge, typename Graph > void tree_edge(Edge e, Graph & g) { s.push_back(e); double smass = 0.0; for (ms_analysis::edge_stack::const_iterator pos = s.begin(); pos != s.end(); ++pos) { smass += g[*pos].aa_data.get_distance(); std::cout << g[*pos].aa_data.get_distance() << '\t'; } std::cout << std::endl; smass += 19.0; std::cout << "T=" << target_mass << ", S=" << smass << std::endl; if (smass > target_mass - 0.5 && smass <= target_mass + 0.5) { for (ms_analysis::edge_stack::const_iterator pos2 = s.begin(); pos2 != s.end(); ++pos2) { ms_analysis::graph::vertex_descriptor v1, v2; v1 = source(e, g); v2 = target(e, g); // Setting properties fails to compile. //g[v1].valid = true; //g[v2].valid = true; vs.insert(v1); vs.insert(v2); } } v.push_back(s); } } template < typename Edge, typename Graph > void back_edge(Edge e, const Graph & g) { // This is *never* called. std::cout << "BACK" << std::endl; s.pop_back(); } double target_mass; ms_analysis::vertex_set vs; std::vector<ms_analysis::edge_stack>& v; ms_analysis::edge_stack s; }; -- .''`. Roger Leigh : :' : Debian GNU/Linux http://people.debian.org/~rleigh/ `. `' Printing on GNU/Linux? http://gutenprint.sourceforge.net/ `- GPG Public Key: 0x25BFB848 Please GPG sign your mail.
Hello Roger, On Sun, 2006-12-10 at 17:50 +0000, Roger Leigh wrote:
Hi folks,
I've written a program which makes use of the Boost Graph library to construct a graph. I've then attached properties to both the vertices and edges, giving a result like this:
http://www-users.york.ac.uk/~rl522/test.pdf
However, I want to now search the graph in order to do this:
1. When the edge is the last, i.e. the outdegree of the target is 0: 2. Total the edge values for all the edges followed to get here all the way back to the root, and add 19. 3. If this total is the same value as the root node value, set a particular property on each vertex those edges are connected to.
I've tried a depth_first_search using a Visitor. I wanted to push each edge onto a temporary vector as I found it, and then pop it when the algorithm backtracked, but this doesn't work.
How do you want to deal with multiple paths in the graph? That could determine what kind of search this is. For example, one could have paths A -> B -> D and A -> C -> D, where the edges along the paths have different values. Do you want the shortest path from A to D? The longest path? Do you want to check both paths separately? The other issue is cycles... how would you want to treat a cycle like A -> B -> D -> A?
The aim here was to know the path taken to get to a particular edge when that edge was found. I'm completely new to using graphs (I'm actually a Biologist), and I think I'm missing how I should really be using the depth_first_search or breadth_first_search visitors to do what I need.
Looking at your depth-first search visitor, I think the BGL terminology might be a little misleading. The "back_edge" event refers to edges that go from the currently active vertex back to a vertex that is already on a the current path. It's easy to keep a stack of *vertices* with path information, because one can push the vertex on the stack in discover_vertex and pop the vertex off the stack in finish_vertex. If there are no parallel edges in the graph (e.g., two edges from A to B), one can reconstruct the path from this information. When you traverse an edge (e.g., in the tree_edge event), the stack will contain all of the vertices in the path up to (but not including) the path of the edge. For edges, we don't have an equivalent "finish_edge" event, which would really help here. We could probably fake it: for instance, if your visitor is only interested in "tree" edges (not back, forward, or cross edges), you could push the edge onto the stack of edges in the tree_edge event, then remove it in finish_vertex, because a tree_edge call always preceeds a discover_vertex call. Still, it depends on how you want to handle cycles and alternate paths. This depth-first search formulation will basically ignore cycles and alternate paths.
It also doesn't appear to like me using the visitor to alter the properties on the vertices or edges during the search. Is this allowed? I'm not altering the graph, just wanting to set a few property values (internally stored, in this case).
Ah, right. The depth_first_search takes in a "const Graph&", and passes that "const" through to your visitor. To modify the graph, you need to "const_cast" to the reference type, like this: template < typename Edge, typename Graph > void back_edge(Edge e, const Graph & in_g) { Graph& g = const_cast<const Graph&>(in_g); // This is *never* called. std::cout << "BACK" << std::endl; s.pop_back(); } Cheers, Doug
participants (2)
-
Douglas Gregor -
Roger Leigh