About property maps and the Boost Graph module
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
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
> 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?
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
Hi. I recognized a strange (wrong?) behaviour of gcc-3.4.1 (and gcc-3.3.3). When adding const to a type T and this type T is a reference, the result is just T again (with reference, but witout const)! Then I tested, if boost handles this case correctly, and it didn't. The type of add_const< int & >::result is int & and not as expected const int &. Next I was looking into the boost-Implementation of add_const and found something like (hidden in a makro): template< class T > struct add_const { typedef const T result; // same result with: // typedef T const result; }; The only way I could get the correct behaviour was to add specializations for ALL combinations: template< class T > struct add_const< T & > { typedef const T & result; }; template< class T > struct add_const< const T & > { typedef const T & result; }; template< class T > struct add_const< T * > { typedef const T * result; }; ... My questions to you: Can anybody verify this behaviour? Is this behaviour intended? If yes, WHY? thx a lot Alexander P.S: It was quite difficult to check, which result-type the add_const really created. First I used typeid( ... ).name(). But then I recognized that int, int &, const int & produce ALL THE SAME name?!? Therefore I used an abstract function with the unknown type. In a derived class I overloaded all possible solutions and printed the CORRECT type... Any suggestions here?
Alexander Neubeck wrote:
Hi.
I recognized a strange (wrong?) behaviour of gcc-3.4.1 (and gcc-3.3.3). When adding const to a type T and this type T is a reference, the result is just T again (with reference, but witout const)! Then I tested, if boost handles this case correctly, and it didn't. The type of add_const< int & >::result is int & and not as expected const int &.
Your expectation was wrong. A "const" reference to int is not the same as a reference to a const int. [...]
My questions to you: Can anybody verify this behaviour? Is this behaviour intended? If yes, WHY?
Because that's how top-level const works. int * const != int const *, and int & const != int const &.
P.S: It was quite difficult to check, which result-type the add_const really created. First I used typeid( ... ).name(). But then I recognized that int, int &, const int & produce ALL THE SAME name?!?
Yes, that's how typeid works.
participants (4)
-
Alexander Neubeck -
Ken Yasumoto-Nicolson -
Peter Dimov -
Vladimir Prus