How to find ancestor nodes in a graph, thanks
Hi folks, I want to find all the nodes that can reach a specific node 'target_n'. Let's say, an example graph looks like this: G= (V, E), where V={A, B, C, target_1, target_2, D, E, F}, and E= { (A-->B), (B-->target_1), (C-->target_2), (A-->target_2), (D-->E), (E-->F), (F-->D), } In this example, I want to find out(say print them out) 'A', 'B', 'C'. Now, I have a graph representation like the following one . ------------------------------ typedef adjacency_list<vecS, vecS, bidirectionalS, VertexNameProperty > Graph; Graph travel; --------------------------------- And I have already read in the above information to the Graph travel. One way I am thinking of to achieve the above goal is: reverse the direction of edges in G, i.e., getting a G', first; and then do BFS from target_n nodes. My question is: (1) is there an easy (some API, sorry I am not familar with the library) way to reverse edge direction? (2) is there an easy way to add a 'printf()' during BFS? Thanks, Sean _________________________________________________________________ FREE pop-up blocking with the new MSN Toolbar get it now! http://toolbar.msn.click-url.com/go/onm00200415ave/direct/01/
On Jul 4, 2006, at 7:49 PM, sean yang wrote:
My question is: (1) is there an easy (some API, sorry I am not familar with the library) way to reverse edge direction?
Yes, the "reverse_graph" adaptor reverses the edge direction.
(2) is there an easy way to add a 'printf()' during BFS?
You can write your own BFS visitor, which has an "examine_vertex" method that printf()'s the current vertex as it is processed. The whole thing will look something like this: struct print_visitor : boost::bfs_visitor<> { template<typename Graph, typename Vertex> void examine_vertex(Vertex u, const Graph& g) { printf(...); } }; breadth_first_search(boost::make_reverse_graph(travel), target_2, boost::visitor(print_visitor())); Doug
participants (2)
-
Douglas Gregor
-
sean yang