[graph-tool] wrong label_largest_component

Tiago de Paula Peixoto tiago at skewed.de
Thu Mar 13 16:00:05 CET 2014


On 03/13/2014 11:45 AM, Николай Кинаш wrote:
>
> Hello.
>
> import sys, os
> from pylab import *
> from numpy.random import *
> from graph_tool.all import *
> g = Graph(directed=False);
>
> N = 10;
> v = g.add_vertex();
> vlist = [v];
> for i in range(1, N):
>         v = g.add_vertex()
>         c = randint(0, len(vlist))
>         target = vlist[c]
>         g.add_edge(v, target)
>         vlist.append(v)
>         if randint(0, 2) == 1:
>                 rem = randint(0, len(vlist))
>                 g.remove_vertex( vlist[rem] );
>
> graph_tool.stats.remove_self_loops(g);
> pos = sfdp_layout(g, cooling_step=0.99);
> graph_draw(g, pos, output_size=(1000, 1000),vertex_size=10, edge_pen_width=2.2, output="graph" + str(i) + ".png")
> l = graph_tool.topology.label_largest_component(g);
> print(l.a);
> u = graph_tool.topology.GraphView(g, vfilt=l);
> print(u.num_vertices());
>
>
> =============out=======
> python test_graph.py
> [0 1 1 0 0]
> 2
>
> but in image i see 4 vertex in largest connected component.
>
> I try it over and over, and always see that 1 or 2 vertex missed.

This is actually a bug in vertex removal which happens in some corner
cases. I've fixed this now in git. Thanks for pointing this out!

I'll make a bugfix release soon. As a temporary workaround you can make
g.set_fast_edge_removal(True) before removing vertices from the graph.

Best,
Tiago

-- 
Tiago de Paula Peixoto <tiago at skewed.de>

-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 901 bytes
Desc: OpenPGP digital signature
URL: <https://lists.skewed.de/pipermail/graph-tool/attachments/20140313/6ea4e7de/attachment.asc>


More information about the graph-tool mailing list