[Boost-users] Re: About property maps and the Boost Graph module

From: Vladimir Prus (ghost_at_[hidden])
Date: 2004-10-26 01:54:17

Ken Yasumoto-Nicolson wrote:

>    Given a directed graph with a single start and end point, I want for
> each node (vertex) to build a list of all the other nodes that can be
> reached from the current node.

I think that's called transitive closure and BGL already has an algorithm
for computing it.

> The algorithm is simple, I think: do a depth_first_search() and
> implement my code on dfs_visitor::finish_vector(). This skeleton I have
> done. However, the bit I can't get my head around is how to use property
> maps to collect the info. The key parts of my best effort so far are:
> 
> struct statement_list_t
> {
>     typedef boost::vertex_property_tag kind;
> };
> typedef boost::property< statement_list_t, std::set<size_t> >
>                                          StatementListProperty;
> typedef boost::adjacency_list< boost::vecS,
>                                boost::vecS,
>                                boost::bidirectionalS,
>                                StatementListProperty,
>                                boost::no_property > ADJ_GRAPH;
> 
> struct connection_detector : public boost::dfs_visitor<>
> {
> public:
>     connection_detector()  {}
> 
>     template <class Vertex, class Graph>
>     void finish_vertex(Vertex u, const Graph& g) {
>         /* for each child in out_edges( u, g )
>               current node set = union_of( current, child ) */
>     }
> }
> 
> However, my questions are:
> 
> 1. std::set<size_t> - is the size_t the best type to store a reference
> to a vector in?

You might use graph_traits<......>::vertex_descriptor but that won't bring
you anything really. Also note that using set will be pretty inefficient.
The transitive_closure implementation uses so called "chains" to optimise
the memory requirements. 

> 2. In finish_vertex<> (or other places) how do I address the
> StatementListProperty value for a given vertex?

   get(statement_list_t(), graph)[vertex] = whatever;

(I think)

> 3. How would I use an Exterior Property Map instead?

   vector_property_map< set<int> > reachable;
   size_t vertex = ......;
   reachable[vertex] = whatever;

HTH,
Volodya