[Boost-users] How to delete all vertices and edges in BGL

[Abhijit Deshmukh]

Hi,

I have a mutable property undirected graph. I want to delete all the
vertices and edges in the graph.

I tried using the for loop

for( b = *vertices( databaseGraph ).first; b!= *vertices(
databaseGraph ).second; b++ ){
clear_vertex( b, databaseGraph );
remove_vertex( b, databaseGraph );
}

This works fine for some extent, but then crashes. My guess is that
the loop crashes when it reaches a vertex whose edges have not been
deleted. But my speculation was that clear_vertex deletes all the
edges associated with a vertex and the function should not crash when
clear_vertex is called before remove_vertex.

Clearly, I am making a mistake, but am not able to point it out.

Can you let me know what is the correct way of deleting all edges and
vertices in a mutable property undirected graph.

Thanks in anticipation.

Regards,

Abhijit

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

[Douglas Gregor]

On Jul 11, 2005, at 11:39 PM, Abhijit Deshmukh wrote:

> Hi,
>
> I have a mutable property undirected graph. I want to delete all the
> vertices and edges in the graph.
>
> I tried using the for loop
>
> for( b = *vertices( databaseGraph ).first; b!= *vertices(
> databaseGraph ).second; b++ ){
> clear_vertex( b, databaseGraph );
> remove_vertex( b, databaseGraph );
> }

The major problem here is that you shouldn't be dereferencing
vertices(databaseGraph).second, because it is a past-the-end iterator.
You could rewrite the loop as:

while (vertices(databaseGraph).first != vertices(databaseGraph).second)
{
b = *vertices(databaseGraph).first;
clear_vertex(b, databaseGraph);
remove_vertex(b, databaseGraph);

}

> Can you let me know what is the correct way of deleting all edges and
> vertices in a mutable property undirected graph.

The easy way is just "databaseGraph.clear()"

Doug

[Jeremy Graham Siek]

Hi Guys,

On Jul 12, 2005, at 8:25 AM, Douglas Gregor wrote:
> The major problem here is that you shouldn't be dereferencing
> vertices(databaseGraph).second, because it is a past-the-end iterator.
> You could rewrite the loop as:
>
> while (vertices(databaseGraph).first != vertices(databaseGraph).second)
> {
> b = *vertices(databaseGraph).first;
> clear_vertex(b, databaseGraph);
> remove_vertex(b, databaseGraph);
> }

But the above loop could also have problems due to vertex iterator
invalidation
caused by remove_vertex... it depends on the graph used.

>> Can you let me know what is the correct way of deleting all edges and
>> vertices in a mutable property undirected graph.
>
> The easy way is just "databaseGraph.clear()"

Yep.

Cheers,
Jeremy
_______________________________________________
Jeremy Siek <js...@osl.iu.edu>
http://www.osl.iu.edu/~jsiek
Ph.D. Candidate, Indiana University Bloomington
C++ Booster (http://www.boost.org)
_______________________________________________

[Abhijit Deshmukh]

Hi,

The clear() function did the trick for me. I am using vecS for
OutEdgeList and VertexList.
I guess using listS would have been better in this case. The list
would not have caused the iterator problem.

Thanks for your help.

Regards,
Abhijit Deshmukh

[Doug Gregor]

On Jul 12, 2005, at 8:52 AM, Jeremy Graham Siek wrote:

> Hi Guys,
>
> On Jul 12, 2005, at 8:25 AM, Douglas Gregor wrote:
>> The major problem here is that you shouldn't be dereferencing
>> vertices(databaseGraph).second, because it is a past-the-end iterator.
>> You could rewrite the loop as:
>>
>> while (vertices(databaseGraph).first !=
>> vertices(databaseGraph).second)
>> {
>> b = *vertices(databaseGraph).first;
>> clear_vertex(b, databaseGraph);
>> remove_vertex(b, databaseGraph);
>> }
>
> But the above loop could also have problems due to vertex iterator
> invalidation
> caused by remove_vertex... it depends on the graph used.

?

We're not storing any iterators, so there's nothing to invalidate.
Granted, the loop is horribly inefficient when VertexListS=vecS, and
clear() is better, but this will work.

Doug

[Jeremy Graham Siek]

Hi Doug,

Yeah, you're right... I didn't read that loop carefully... I assumed
it was doing the usual thing.

Cheers,
Jeremy

On Jul 12, 2005, at 4:06 PM, Doug Gregor wrote:
> On Jul 12, 2005, at 8:52 AM, Jeremy Graham Siek wrote:
>> On Jul 12, 2005, at 8:25 AM, Douglas Gregor wrote:
>>> while (vertices(databaseGraph).first !=
>>> vertices(databaseGraph).second)
>>> {
>>> b = *vertices(databaseGraph).first;
>>> clear_vertex(b, databaseGraph);
>>> remove_vertex(b, databaseGraph);
>>> }
>>
>> But the above loop could also have problems due to vertex iterator
>> invalidation
>> caused by remove_vertex... it depends on the graph used.
>
> ?
>
> We're not storing any iterators, so there's nothing to invalidate.
> Granted, the loop is horribly inefficient when VertexListS=vecS, and
> clear() is better, but this will work.
>
> Doug
_______________________________________________

Jeremy Siek <js...@osl.iu.edu>
http://www.osl.iu.edu/~jsiek
Ph.D. Candidate, Indiana University Bloomington
C++ Booster (http://www.boost.org)
_______________________________________________