weird in deleting vertices and edges

graph-tool
1

Hi all,

I found something weird in deleting vertices and edges of a graph. Say I
simply create a graph like:

    g = Graph(directed=False)
    g.add_vertex(7)
    g.add_edge(g.vertex(0), g.vertex(1))
    g.add_edge(g.vertex(1), g.vertex(2))
    g.add_edge(g.vertex(2), g.vertex(3))
    g.add_edge(g.vertex(3), g.vertex(4))
    g.add_edge(g.vertex(2), g.vertex(5))
    g.add_edge(g.vertex(5), g.vertex(6))

   del_list = [g.vertex(1), g.vertex(3)]

   for v in reversed(sorted(del_list)):
        print 'deleting vertex', int(v)
    ## for ve in v.out_edges():
    ## print 'deleting edges', ve.source(), ve.target()
    ## g.remove_edge(ve)
        g.remove_vertex(v, fast=True)

The above code will delete vertex 3 first, then vertex 1 as expected.
However, in order to keep correct topology, we should delete some related
edges first, like the three commented lines (start with "##").

But if you uncomment the three lines, weird thing happens: the program
will delete vertex 1 first, then vertex 3.

Of course I can sort the vertex index instead of vertex descriptor to avoid
the problem. But I am wondering where is wrong. Could anyone explain this?

attachment.html (1.54 KB)

2

I don't observe anything weird. Here I see the following with the lines
uncommented:

    deleting vertex 3
    deleting edges 3 2
    deleting edges 3 4
    deleting vertex 1
    deleting edges 1 0
    deleting edges 1 2

First vertex 3, then 1.

However there is indeed a problem with your code. In the documentation:

    https://graph-tool.skewed.de/static/doc/quickstart.html#iterating-over-the-neighbourhood-of-a-vertex

there is this following warning:

    You should never remove vertex or edge descriptors when iterating
    over them, since this invalidates the iterators. If you plan to
    remove vertices or edges during iteration, you must first store them
    somewhere (such as in a list) and remove them only after no iterator
    is being used. Removal during iteration will cause bad things to
    happen.

This is what you are trying to do if you uncomment the lines, and it
might cause problems. Don't do that; store the edges in a list first.

Best,
Tiago

3

Thank you very much for the immediate reply ! I had read that warning, but
forgot it at all when coding. I think I will never forget it from now on.

2015-04-20 23:36 GMT+08:00 Tiago de Paula Peixoto <tiago(a)skewed.de>:

attachment.html (3.91 KB)

4

Sorry to bother again. I am not sure how python build-in methods "sorted"
and "reversed" work on vertex descriptor list. The following code snippet
output:

vertex 3
vertex 5
vertex 1

code snippet:

    del_list = [g.vertex(1), g.vertex(5), g.vertex(3)]
    for v in reversed(sorted(del_list)):
        print 'vertex', int(v)

Is it correct? I am using debian wheezy, and install graph-tool by adding

"deb http://downloads.skewed.de/apt/wheezy wheezy main " in my source
list. Although I know there only lists "jessie" and "sid",

I still got graph-tool successfully installed and everything seems work well.

2015-04-20 23:36 GMT+08:00 Tiago de Paula Peixoto <tiago(a)skewed.de>:

attachment.html (4.62 KB)

5

Be careful, if you use "wheezy" you will install a _very old_ version of
graph-tool! Newer versions do not compile in wheezy, so you must use
jessie or sid!

What you are seeing is probably a bug from a long time ago that already
got fixed...

Best,
Tiago

6

OK. Got it. Thank you !

2015-04-21 21:44 GMT+08:00 Tiago de Paula Peixoto <tiago(a)skewed.de>:

attachment.html (2.25 KB)