Re: [igraph] Nodes at a given distance

[Tamas Nepusz]

Dear Marco,

I just spotted a bug yesterday in the BFS iterator code which causes 
segfaults when the Python garbage collector activates itself while there is 
a BFS iterator among the objects tracked by the garbage collector itself. As 
a temporary solution, try disabling the garbage collector temporarily using:

import gc
gc.disable()
# do your BFS-related stuff here
gc.enable()

I'm not sure it will work, but it's worth a try.

Alternatively, I can send you a patch if you are willing to recompile the 
Python interface (the patch changes just two or three lines in 
bfsiterobject.c). This patch will be included in the soon-to-be-released 
igraph 0.5.1 (as soon as I get back from holiday), so if you can simply wait 
a week or two, maybe that's the easiest.

-- 
T.

On Wed, 30 Jul 2008 11:47:32 +0200, Marco wrote
> On Sun, Jul 27, 2008 at 2:09 PM, Tamas Nepusz <address@hidden> wrote:
> > Another possibility is to use a breadth first search iterator over the
> > vertices, starting from your source vertex:
> >
> > g=Graph.GRG(100, 0.2)
> > source_vertex=0
> > distance=2
> > for vertex, d, parent in g.bfsiter(source_vertex, advanced=True):
> >  if d == distance:
> >    # If the current vertex is at the desired distance, print its index
> >    print vertex.index
> >  elif d > distance:
> >    # The current vertex is farther than the desired distance. Since this 
is
> >    # a BFS iterator, no vertex with the desired distance will come up in 
the
> >    # sequence, so we can safely cancel the iteration
> >    break
> 
> Hi,
> 
> Thanks for the idea! Doing  "for path in
> graph.get_all_shortest_paths(v.index):" on large graphs is quite 
> hard, it takes a lot of time. I have tried to implement the bfsiter 
> in my program, and it didn't work. So i wrote a simple example to 
> check if everything was okay. Here's the outcome.
> 
> I am using this code:
> 
> import igraph
> 
> graph=igraph.Graph.Erdos_Renyi(10,3/9.)
> for v in graph.vs():
>     for vertex, d, parent in graph.bfsiter(v.index, advanced=True):
>         if d==4:
>             print v.index,  '->' , vertex.index,  'distance' , d
> 
> and i obtain different answers:
> .. sometimes i get a SegFault.
> 
> .. other times i get:
> 1 -> 3 distance 4
> 1 -> 6 distance 4
> 1 -> 7 distance 4
> 2 -> 9 distance 4
> 3 -> 1 distance 4
> python: vector.pmt:448: igraph_vector_size: Assertion `v->stor_begin
> != ((void *)0)' failed.
> Aborted
> 
> Seems to me like it's working for some nodes, but then something 
> makes him die badly.
> 
> If modify the code as:
> 
> import igraph
> 
> graph=igraph.Graph.Erdos_Renyi(10,3/9.)
> for v in graph.vs():
>     for vertex, d, parent in graph.bfsiter(v.index, advanced=True):
>         if d==4:
>             print v.index, '->',vertex.index, 'distance', d
>         else:
>             break
> 
> I simply get SegFault all the times.
> 
> Any ideas?
> 
> thanks,
> 
> marco
> 
> -- 
> č il gioco della vita,
> la dobbiamo preparare
> che non ci sfugga dalle dita
> come la sabbia in riva al mare.
> 
> Lucio Dalla
> 
> _______________________________________________
> igraph-help mailing list
> address@hidden
> http://lists.nongnu.org/mailman/listinfo/igraph-help


--
Tamas