[Boost-users] [BGL] vecS for vertex container and vertex index adjustments

[Sergey Mitsyn]

Hi all,

I know that while using vecS for vertices one has no vertex iterator
stability upon removing vertices. But I have a question if there exists
something like vertex _index_ stability. The documentation says that
indices for vertices are automatically adjusted so that they are still
in contiguous range, but it is not specified how it is done. Is it okay
to assume that if a vertex with an index I is removed, then vertices
with indices < I have their indices unchanged, while vertices with
indices > I have their indices decreased by one?

The actual problem is removing all vertices meeting some condition. Is
the following code ok?

// traverse all vertices and remove those for which predicate
// condition_to_remove_vertex returns true.

// graph is adjacency_list<.., vecS, ...>

vertex_iterator vi = vertices(graph).first, vi_end = vertices(graph).second;

while (vi != vi_end)
{
if (condition_to_remove_vertex(vi, graph))
{
vertices_size_type end_index = vertex_index[*vi_end]
, vi_index = vertex_index[*vi];

remove_vertex_f(*vi, graph);
// vi and vi_end are invalid

--end_index;

vi = vertices(graph).first + vi_index;
vi_end = vertices(graph).first + end_index;
// now vi and vi_end are valid again
}
else
++vi;
}



This way seems to be more effective than to start iteration again every
time a vertex is removed.

------------
Sergey Mitsyn.


_______________________________________________
Boost-users mailing list
Boost...@lists.boost.org
http://lists.boost.org/mailman/listinfo.cgi/boost-users

[Jeremiah Willcock]

On Thu, 31 May 2012, Sergey Mitsyn wrote:

> Hi all,
>
> I know that while using vecS for vertices one has no vertex iterator
> stability upon removing vertices. But I have a question if there exists
> something like vertex _index_ stability. The documentation says that indices
> for vertices are automatically adjusted so that they are still in contiguous
> range, but it is not specified how it is done. Is it okay to assume that if a
> vertex with an index I is removed, then vertices with indices < I have their
> indices unchanged, while vertices with indices > I have their indices
> decreased by one?

Yes, that is how it works internally, but that is not documented behavior;
it probably should be, however. It also does not apply to vertex
iterators; those can change to completely unrelated values on any vertex
insertion/deletion.

> The actual problem is removing all vertices meeting some condition. Is the
> following code ok?
>
> // traverse all vertices and remove those for which predicate
> // condition_to_remove_vertex returns true.
>
> // graph is adjacency_list<.., vecS, ...>
>
> vertex_iterator vi = vertices(graph).first, vi_end = vertices(graph).second;
>
> while (vi != vi_end)
> {
> if (condition_to_remove_vertex(vi, graph))
> {
> vertices_size_type end_index = vertex_index[*vi_end]
> , vi_index = vertex_index[*vi];
>
> remove_vertex_f(*vi, graph);
> // vi and vi_end are invalid
>
> --end_index;
>
> vi = vertices(graph).first + vi_index;
> vi_end = vertices(graph).first + end_index;
> // now vi and vi_end are valid again
> }
> else
> ++vi;
> }
>
>
>
> This way seems to be more effective than to start iteration again every time
> a vertex is removed.

Yes, that should work. Rather than using vertices(graph).first + vi_index,
use vertex(vi_index, graph); 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;
}
}

Depending on what you are doing, you might also want to consider using
filtered_graph with a bitmap representing which vertices are deleted.
That will keep everything valid (even for vecS), including external
property maps based on the vertex index numbers.

-- Jeremiah Willcock

[Sergey Mitsyn]

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.

[Jeremiah Willcock]

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?

-- Jeremiah Willcock

[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.

[Ed Linde]

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?

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. :)

Cheers,
Ed



--
View this message in context: http://boost.2283326.n4.nabble.com/BGL-vecS-for-vertex-container-and-vertex-index-adjustments-tp4630730p4636256.html
Sent from the Boost - Users mailing list archive at Nabble.com.

[Jeremiah Willcock]

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

[Ed Linde]

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.

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?

Thanks,
Ed





--
View this message in context: http://boost.2283326.n4.nabble.com/BGL-vecS-for-vertex-container-and-vertex-index-adjustments-tp4630730p4636276.html

Sent from the Boost - Users mailing list archive at Nabble.com.

[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

[Ed Linde]

Hi Jeremiah,
I looked at the filter graph example in the boost examples for the positive
edge weights.
But it seems to me like the filter gets applied once at the end, so is there
a way in which
I can apply the filter for every vertex in a for loop when a condition is
met? Idea being that
I want to keep reducing the graph and using the new filtered version in the
subsequent
iterations and processing. Could you please show me an example or construct
a simple one
for me if its possible?

Thanks,
Ed



--
View this message in context: http://boost.2283326.n4.nabble.com/BGL-vecS-for-vertex-container-and-vertex-index-adjustments-tp4630730p4636316.html

Sent from the Boost - Users mailing list archive at Nabble.com.

[Ed Linde]

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: Re: [BGL] vecS for vertex container and vertex index adjustments

[Jeremiah Willcock]

On Tue, 2 Oct 2012, Ed Linde wrote:

> 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

You would use a filtered_graph that is attached to a property map of
Boolean values, then change that property map in-place. The
filtered_graph will see those changes immediately.

-- Jeremiah Willcock

[Ed Linde]

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-index-adjustments-tp4630730p4636464.html

Sent from the Boost - Users mailing list archive at Nabble.com.

[Ed Linde]

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<Graph, edge_weight_t>::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-index-adjustments-tp4630730p4636465.html

Sent from the Boost - Users mailing list archive at Nabble.com.

[Jeremiah Willcock]

On Tue, 2 Oct 2012, Ed Linde wrote:

> 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<Graph, edge_weight_t>::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 ?

One example of something similar is at libs/graph/example/astar_maze.cpp
in the Boost source tree. There, vertices are removed when they are in an
unordered_set. You might want to use a one_bit_color_map instead for
performance; look at property_map_filter at the bottom of
<boost/graph/filtered_graph.hpp> for how to use a property map for that.

-- Jeremiah Willcock