From: Pete Donnell (p.donnell_at_[hidden])
Date: 2005-03-29 09:23:10
Hi,
I hope you will forgive me for asking a rather simple question. I have
been having a lot of trouble writing a visitor for use in depth first
search.
The algorithm I'm attempting to write is supposed to count the number of
different paths between two vertices on a directed graph. The graph may
or may not contain cycles, and of course walks that contain cycles are
not counted as paths. The way I've approached the problem is to induce a
subgraph on the source and sink vertices, by copying the graph and then
removing any vertices that do not lie on a path between the source and
sink. My plan then is to do a depth first search on the induced
subgraph, using a custom visitor that counts the number of forward or
cross edges, which I think will be a count of the number of paths
between the source and sink. To be honest, I haven't thought too hard
about whether this is algorithmically correct, as the main problem is
with the visitor. If I figure out to write custom visitors then it
shouldn't be too hard to write other algorithms.
As things stand, the function to induce a subgraph is working fine
(although I am not using the Boost subgraph, mainly because it isn't
documented in the book and so I didn't become aware of its existence
until after I'd written the code). Incidentally, this function is useful
in itself, which is why I have used it. I'm aware that it's not a very
efficient way of solving the problem. The code I've written for the
visitor to call on the path counting algorithm currently goes like this
(I have slightly modified it a lot of times to try and get it to work):
template<typename OutputIterator> class EnumeratorVisitor : public
boost::dfs_visitor<OutputIterator>
{
private :
long unsigned int pathCount;
public :
EnumeratorVisitor() : boost::default_dfs_visitor(), pathCount(1) {}
EnumeratorVisitor(OutputIterator out) :
boost::dfs_visitor<OutputIterator> (out), pathCount (1) {}
long unsigned int getPathCount() const
{
return pathCount;
}
template <typename Graph, typename Edge>
void forward_or_cross_edge(const Edge& e, const Graph& g)
{
++pathCount;
}
};
The code where I use it looks like this:
template<typename Graph>
long unsigned int enumeratePaths(const Graph& graph,
const typename
boost::graph_traits<Graph>::vertex_descriptor& startNode,[BGL] problem with
const typename
boost::graph_traits<Graph>::vertex_descriptor& endNode)
{
typedef typename boost::graph_traits<Graph>::edge_descriptor Edge;
std::vector<Edge> forwardOrCrossEdges; // vector used to store
the forward or cross edges
Graph* tempGraph = generateSubGraph(graph, startNode, endNode); //
this function induces a subgraph as previously mentioned
typedef boost::color_traits<boost::default_color_type> Colour;
std::vector<boost::default_color_type>
colourMap(boost::num_vertices(*tempGraph), Colour::white());
EnumeratorVisitor<typename std::back_insert_iterator<typename
std::vector<Edge> > > edgeInserter(std::back_inserter(forwardOrCrossEdges));
depth_first_visit(graph, startNode, edgeInserter,
boost::make_iterator_property_map(colourMap.begin(),
boost::get(boost::vertex_index, *tempGraph)) );
return edgeInserter.getPathCount();
}
I'm sure there are obvious errors in there to those who know what
they're doing, but I've been looking at this problem for over a month
now without success, so it's got to that stage where I don't really know
what's going on anymore. I've hunted through the book, online code and
so on, but I can't figure it out. It gives about three pages of template
errors at the moment! There have been other minor variants, but all of
them have given errors of some kind.
If anyone can point out what I'm doing wrong, I'd greatly appreciate it.
If more information is needed, I'll happily provide it. By the way, I'm
sure that this problem of path counting has been approached before, it
anyone has any insights to offer, I'd also appreciate that!
Many thanks for your time,
Pete