Hello, Thanks for the reply!

Yes, that should work. Rather than using vertices(graph).first + vi_index, use vertex(vi_index, graph);

I thought about that, but vertex(vi_index, graph) returns vertex_descriptor, not vertex_iterator. Actually that works, but I think it does so only because they have incidentally happened to be the related types :).

I believe the order is guaranteed to be the same between those, and it is in practice. You might also want to have the loop be over the vertex numbers:

for (vertices_size_type i = 0; i < num_vertices(graph); /*Incremented in loop*/) { vertex_descriptor v = vertex(i, graph); if (condition(v, graph) { remove_vertex(v, graph); } else { ++i; } }

Yes, that would be much clearer, thanks! ----------- Sergey Mitsyn.

On 31.05.2012 22:09, Jeremiah Willcock wrote:

On Thu, 31 May 2012, Sergey Mitsyn wrote:

...

Hello,

Thanks for the reply!

...

Yes, that should work. Rather than using vertices(graph).first + vi_index, use vertex(vi_index, graph);

I thought about that, but vertex(vi_index, graph) returns vertex_descriptor, not vertex_iterator. Actually that works, but I think it does so only because they have incidentally happened to be the related types :).

Do you need the iterators themselves, and not just the descriptors?

Clarification: descriptors are enough if I stick to the for loop code you provided. ------------ Sergey Mitsyn.

On Wed, 26 Sep 2012, Ed Linde wrote:

Hi Jeremiah,

I am facing a similar problem where I have to iterate through the vertices of a graph and conditionally remove a lot of vertices. With the idea you mention of keeping a VecS adjacency_list graph + some external vertex property map indexed by vertex ID. And then iterating with a for loop over "vertex IDs" instead of using the iterators, wouldn't the *remove_vertex* anyway make the descriptors on the remaining vertices of the graph invalid?

Yes, it would invalidate them.

So in the end when I want to output the remaining graph, I might have problems when I iterate through the vertices. So is there an additional step of updating these external vertex property maps every time you delete a vertex using remove_vertex? Also do you think its a good idea to process the vertices in a descending order? But I think the removal will mess up all the vertex descriptors anyway, so I cannot save the output right? Just a bit confused I guess. I also do shortest path calculations on the graph while removing vertices, so I cannot just have a flag set that can allow SP algorithms to skip these vertices ( I think). So if you have any good work arounds let me know. :)

Only vertex descriptors greater than or equal to the one being removed will be invalidated, so going in descending order will work, but you might want to use filtered_graph instead. For that, you can have a property map that represents whether a vertex is in or out of your smaller graph, then run shortest paths on that. The filtered_graph does not change vertex numbers when you mask out a vertex, so your property maps won't need to be updated. -- Jeremiah Willcock

On Wed, 26 Sep 2012, Ed Linde wrote:

Thanks Jeremiah. I will look into the filtered graph. I didn't know that it would work with shortest path algorithms in such a way that if you masked a vertex, it would not be considered in the SP calculations anymore.

That is how it is supposed to work for all algorithms, not just shortest path ones.

Another thing I just realised was that I might have to loop through these vertex IDs in decreasing order of a scoring function, rather than just in decreasing order of vertex IDs. So in that case a filtered graph is my only option yeah?

I think it would be the easiest option. -- Jeremiah Willcock

Hi,I have not yet heard of a solution, when I am having to iterate through the graph and then work on the filtered graph in every subsequent iteration after I have cleared the vertex. The examples only show how to apply the filter ONCE at the end. If I keep calling filtered_graph am I then making a lot of instances and hence it would keep having to make new copies of my graph?Thanks,Ed -- View this message in context: http://boost.2283326.n4.nabble.com/BGL-vecS-for-vertex-container-and-vertex-... Sent from the Boost - Users mailing list archive at Nabble.com.

Hi Jeremiah, Thanks for the quick responses. But since I am still a BGL newbie. I don't get what the predefined types are that I can use for my property map. What you seem to be suggesting sounds like a binary bitmap, which I have to check to set the filter or not for a vertex? So in the definition below for example, what would I replace "edge_weight_t" with? typedef property_map::type EdgeWeightMap; (Example at http://www.boost.org/doc/libs/1_51_0/libs/graph/example/filtered_graph.cpp ) Could you maybe show me a quick example of just the property map ? Thanks, Ed -- View this message in context: http://boost.2283326.n4.nabble.com/BGL-vecS-for-vertex-container-and-vertex-... Sent from the Boost - Users mailing list archive at Nabble.com.

To add to my previous concern. I seem to have two options 1. Use vertices as a LIST instead of VECTOR. And then basically go through the list to remove the vertices one by one in each iteration. Will be slow in the beginning but as vertices keep coming out and the size gets smaller. It will get faster. OR 2. Use vertices as VECTOR. And then apply filter. But this might apply the filter for every single vertex ALL the time in each loop. Which might not perform so well. But it references the original graph, and hence may not need to make another copy. What is the better option? Please advice. Ed -- View this message in context: http://boost.2283326.n4.nabble.com/BGL-vecS-for-vertex-container-and-vertex-... Sent from the Boost - Users mailing list archive at Nabble.com.