[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [igraph] Nodes at a given distance
From: |
Tamas Nepusz |
Subject: |
Re: [igraph] Nodes at a given distance |
Date: |
Wed, 30 Jul 2008 11:54:14 +0200 |
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
- Re: [igraph] Nodes at a given distance, (continued)
- Re: [igraph] Nodes at a given distance, Gabor Csardi, 2008/07/25
- Re: [igraph] Nodes at a given distance, Marco, 2008/07/25
- Re: [igraph] Nodes at a given distance, Marco, 2008/07/25
- Re: [igraph] Nodes at a given distance, Gabor Csardi, 2008/07/25
- Re: [igraph] Nodes at a given distance, Marco, 2008/07/25
- Re: [igraph] Nodes at a given distance, Gabor Csardi, 2008/07/25
- Re: [igraph] Nodes at a given distance, Marco, 2008/07/25
- Re: [igraph] Nodes at a given distance, Gabor Csardi, 2008/07/25
- Re: [igraph] Nodes at a given distance, Tamas Nepusz, 2008/07/27
- Re: [igraph] Nodes at a given distance, Marco, 2008/07/30
- Re: [igraph] Nodes at a given distance,
Tamas Nepusz <=
- Re: [igraph] Nodes at a given distance, Marco, 2008/07/30
- Re: [igraph] Nodes at a given distance, Tamas Nepusz, 2008/07/30