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