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