[Boost-users] Computing a path while traversing a graph with a search algorithm

From: Roger Leigh (rleigh_at_[hidden])
Date: 2006-12-10 12:50:28

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.