[BGL] re-indexing of vertices /or edges
Hi, Can I disable re-indexing of vertices after one of them is removed? In one of the old thread: http://thread.gmane.org/gmane.comp.lib.boost.user/10551/focus=10552 Doug said: " Vertex and edge indices are a weak point in the BGL. It seems like they should be automatically updated, but that can't be done efficiently. We have a partial solution (a graph type that is reasonably good all-around and does automatic (re-)indexing), but it's not ready for release yet." I am using release 1.33.1. Is this re-indexing released?(I assume so, from my simple trial) But, is there any way of enabling /and disabling re-indexing? Interestingly, my application needs re-indexing disabled, even though some vertices or edges are removed. Thanks, Shufei
On Apr 4, 2007, at 3:35 PM, Shufei Fan wrote:
In one of the old thread: http://thread.gmane.org/gmane.comp.lib.boost.user/10551/focus=10552
Doug said: " Vertex and edge indices are a weak point in the BGL. It seems like they should be automatically updated, but that can't be done efficiently. We have a partial solution (a graph type that is reasonably good all-around and does automatic (re-)indexing), but it's not ready for release yet."
I am using release 1.33.1. Is this re-indexing released?(I assume so, from my simple trial)
There is no automatic re-indexing in the BGL. It's a feature that we'd like to have, but probably it would be in the context of a new graph type. Cheers, Doug
Doug Gregor <dgregor <at> cs.indiana.edu> writes:
There is no automatic re-indexing in the BGL. It's a feature that we'd like to have, but probably it would be in the context of a new graph type.
Cheers, Doug
Thanks! but, in my trial, based on the 'quick_tour.cpp' example, when I added a few lines at the end of main(): /////////////////////////////////////////////////////////////////////////// //the following is a test of re-indexing, after removing certain node... std::cout << "try delete node No.2, output is: " << std::endl; typedef graph_traits<Graph>::vertex_descriptor Vertex; typedef graph_traits<Graph>::vertex_iterator VertexIter; Vertex ver; VertexIter ver_iter; ver_iter = vertices(g).first; std::advance(ver_iter, 2);//advance iterator 2 positions. clear_vertex(*ver_iter, g); remove_vertex(*ver_iter, g); std::for_each(vertices(g).first, vertices(g).second, exercise_vertex<Graph>(g)); boost::write_graphviz(std::cout, g, make_label_writer(vertex_id),//name make_label_writer(trans_delay), make_graph_attributes_writer(graph_attr, vertex_attr, edge_attr)); /////////////////////////////////////////////////////////////////////////// It's output is: vertices(g) = A B C D E edges(g) = (A,B) (A,D) (C,A) (D,C) (C,E) (B,D) (D,E) vertex: 0 out-edges: (0,1) (0,3) in-edges: (2,0) adjacent vertices: 1 3 vertex: 1 out-edges: (1,3) in-edges: (0,1) adjacent vertices: 3 vertex: 2 out-edges: (2,0) (2,4) in-edges: (3,2) adjacent vertices: 0 4 vertex: 3 out-edges: (3,2) (3,4) in-edges: (0,3) (1,3) adjacent vertices: 2 4 vertex: 4 out-edges: in-edges: (2,4) (3,4) adjacent vertices: digraph G { graph [ rankdir="LR", ratio="fill", size="3,3"]; node [ shape="circle"]; 0[label="0"]; 1[label="1"]; 2[label="2"]; 3[label="3"]; 4[label="4"]; 0->1 [label="1.2"]; 0->3 [label="4.5"]; 2->0 [label="2.6"]; 3->2 [label="0.4"]; 2->4 [label="5.2"]; 1->3 [label="1.8"]; 3->4 [label="3.3"]; } try delete node No.2, output is: vertex: 0 out-edges: (0,1) (0,2) in-edges: adjacent vertices: 1 2 vertex: 1 out-edges: (1,2) in-edges: (0,1) adjacent vertices: 2 vertex: 2 out-edges: (2,3) in-edges: (0,2) (1,2) adjacent vertices: 3 vertex: 3 out-edges: in-edges: (2,3) adjacent vertices: digraph G { graph [ rankdir="LR", ratio="fill", size="3,3"]; node [ shape="circle"]; 0[label="0"]; 1[label="1"]; 2[label="2"]; 3[label="3"]; 0->1 [label="1.2"]; 0->2 [label="4.5"]; 1->2 [label="1.8"]; 2->3 [label="3.3"]; } Am I wrong with displaying the vertex index(which seems to re-adjusted automatically by itself)? Thanks Shufei
On Apr 4, 2007, at 5:08 PM, Shufei Fan wrote:
Thanks! but, in my trial, based on the 'quick_tour.cpp' example, when I added a few lines at the end of main():
Oh, I see what's going on. When you're using an adjacency list, and the VertexListS parameter is "vecS", the vertex descriptors themselves are the index values. So, it's actually impossible to avoid re-indexing when a vertex is deleted. If you need faster deletions or want to avoid re-indexing, you should set VertexListS to something else (e.g., listS). Cheers, Doug
Hi Shufei, How about not removing the vertex. This will avoid re-indexing. Instead, you can "clear" the vertex of all in and out edges. Another alternative is to add your own internal property map with your own indices. Then it will be totally up to you to set the indices and change or not change them. And to clarify wrt to Doug's reply, the adjacency_list class does indeed re-index when the VertexList is vecS, which is the default case. Doug's old email was probably about VertexList=listS. Cheers, Jeremy On 4/4/07, Shufei Fan <fansf@hotmail.com> wrote:
Hi,
Can I disable re-indexing of vertices after one of them is removed?
In one of the old thread: http://thread.gmane.org/gmane.comp.lib.boost.user/10551/focus=10552
Doug said: " Vertex and edge indices are a weak point in the BGL. It seems like they should be automatically updated, but that can't be done efficiently. We have a partial solution (a graph type that is reasonably good all-around and does automatic (re-)indexing), but it's not ready for release yet."
I am using release 1.33.1. Is this re-indexing released?(I assume so, from my simple trial)
But, is there any way of enabling /and disabling re-indexing? Interestingly, my application needs re-indexing disabled, even though some vertices or edges are removed.
Thanks,
Shufei
_______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
Jeremy Siek <jeremy.siek <at> gmail.com> writes:
Hi Shufei,How about not removing the vertex. This will avoid re- indexing.Instead, you can "clear" the vertex of all in and out edges.Another alternative is to add your own internal property map with your own indices. Then it will be totally up to you to setthe indices and change or not change them.And to clarify wrt to Doug's reply, the adjacency_list class does indeedre-index when the VertexList is vecS, which is the default case. Doug's old email was probably about VertexList=listS.Cheers,Jeremy
It seems using 'listS' as VertexList suits my needs and runs faster on deletions! Thanks for clarify and suggestions, Jeremy and Doug! Shufei
participants (3)
-
Doug Gregor -
Jeremy Siek -
Shufei Fan