[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [igraph] Nodes at a given distance
From: |
Marco |
Subject: |
Re: [igraph] Nodes at a given distance |
Date: |
Wed, 30 Jul 2008 11:47:32 +0200 |
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] 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, 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 <=
- Re: [igraph] Nodes at a given distance, Tamas Nepusz, 2008/07/30
- Re: [igraph] Nodes at a given distance, Marco, 2008/07/30
- Re: [igraph] Nodes at a given distance, Tamas Nepusz, 2008/07/30