[Graph] I could not get the reversed graph!
HI, All, I could not get a instance of reversed graph by calling make_reverse_graph(g). That is, I have following type: typedef adjacency_list< listS, listS, bidirectionalS, property<vertex_index_t, std::size_t>, no_property> G; typedef reverse_graph<G, G&> ReverseG; //Maybe something wrong here. After I call make_revserse_graph(G) as following, I could not get a instance of modified graph by accessing some fields of ReverseG. ReverseG tmp=boost::make_reverse_graph(g); //I try to get the reservsed graph here. The only field is tmp.m_g, which is G& type and the original graph, but is not the reversed graph. Thanks. Jiangfan
On Fri, 2007-07-06 at 13:17 -0500, jiangfan shi wrote:
HI, All,
I could not get a instance of reversed graph by calling make_reverse_graph(g).
That is, I have following type: typedef adjacency_list< listS, listS, bidirectionalS, property<vertex_index_t, std::size_t>, no_property> G;
typedef reverse_graph<G, G&> ReverseG; //Maybe something wrong here.
After I call make_revserse_graph(G) as following, I could not get a instance of modified graph by accessing some fields of ReverseG.
ReverseG tmp=boost::make_reverse_graph(g); //I try to get the reservsed graph here.
The only field is tmp.m_g, which is G& type and the original graph, but is not the reversed graph.
The reverse_graph class template in the BGL is a reversed *view* of the existing graph. It costs essentially nothing to build this view, but when you look at the reverse_graph of a graph you see all of its edges going backwards (the actual storage in the graph is unchanged). Because it's a view, changes to the original graph will show up immediately in the reversed graph. - Doug
Thanks, Doug,
The reverse_graph class template in the BGL is a reversed *view* of the existing graph.
So I have to build the "real" reversed graph by myself, or change the "original" graph to build up the reversed graph. The reason is that I want to use such reversed instance to get the dominator tree. Jiangfan
On Fri, 2007-07-06 at 14:32 -0500, jiangfan shi wrote:
Thanks, Doug,
The reverse_graph class template in the BGL is a reversed *view* of the existing graph.
So I have to build the "real" reversed graph by myself, or change the "original" graph to build up the reversed graph. The reason is that I want to use such reversed instance to get the dominator tree.
Most likely, you don't need to build the reversed graph. You can just run algorithms on the reversed "view" of the original graph: that's exactly what the reverse_graph adaptor is meant for. For example, you can call: lengauer_tarjan_dominator_tree(make_reverse_graph(graph), exit_node, dominators) - Doug
Thanks, Doug,
For example, you can call: lengauer_tarjan_dominator_tree(make_reverse_graph(graph), exit_node, dominators)
make_reverse_graph(graph) does not give me the G type (defined in the following code), so I could not use it in this way. This is the reason I use the following code which does not work. typedef adjacency_list< listS, listS, bidirectionalS, property<vertex_index_t, std::size_t>, no_property> G; typedef reverse_graph<G, G&> ReverseG; ReverseG g2=boost::make_reverse_graph(g); ... lengauer_tarjan_dominator_tree(g2.m_g, vertex(0, g), domTreePredMap); Jiangfan
participants (2)
-
Douglas Gregor -
jiangfan shi