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

26 Oct 2004

      Hi folks,

I've searched the archives and boost.org trying to find some help, but I
still can't get my head around how the property maps are supposed to
work. I'm pretty new to Boost, so I'm maybe not too familiar with the
underlying concepts, etc, so forgive me if my question seems a little
too basic! My problem is this:

   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.

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 >
                                         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 
    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 - is the size_t the best type to store a reference
to a vector in?

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

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

Thanks for any advice!

Ken

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

Ken Yasumoto-Nicolson