Boost logo

Boost Users :

Subject: Re: [Boost-users] DAG Graph Search
From: Jeremiah Willcock (jewillco_at_[hidden])
Date: 2009-10-08 12:31:51


On Thu, 8 Oct 2009, Dan Bailey wrote:

> Hi,
>
> I'm looking to do a downstream search over a DAG graph where I never advance
> past a node until all of the nodes linking to it have been seen.
>
> Clearly a breadth first search won't work, but using a topological sort, I
> can get a list of all the nodes in the correct order. However I only wish to
> search over the nodes downstream from any particular node (until I reach the
> leaf nodes), which doesn't work as this is the entire network even if it
> contains various sub-graphs.
>
> Is there a better algorithm or approach I can use to do this?
>
> Here's a simple example:
>
> a -> b
> b -> c
> c -> d
> a -> c
>
> I wouldn't ever want to look at c before b, but if I started at b for
> example, I would only want to see downstream of this.

Could you please try:

depth_first_visit(
   g,
   your_start_vertex,
   boost::topo_sort_visitor<YourOutputIterator>(your_output_iterator),
   color);

(with color as a color map for your graph set to all white)? That should
match what topological sort does but starting at a single vertex rather
than all roots.

-- Jeremiah Willcock


Boost-users list run by williamkempf at hotmail.com, kalb at libertysoft.com, bjorn.karlsson at readsoft.com, gregod at cs.rpi.edu, wekempf at cox.net