Re: [igraph] Nodes at a given distance

[Marco]

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