breadth first neighbors to a specific depth

[Benjamin Golder]

Hi,

I don't know much graph theory, so if there is a better place to answer this question, feel free to redirect me.

I'm trying to create a function that uses breadth first iteration to return the neighbors of a node, but which organizes the results according to depth.

In other words, I would like the algorithm to do take a given node, get it's neighbors, mark the depth as 1, get the neighbors of all those neighbors, then mark the depth as 2, etc.

Here is my current naive and incorrect code:

from collections import deque

def breadthFirstToDepth(graph, node, depth):

    q = deque()

    q.append(node)

    touched = [node]

    while len(q) > 0 and depth > 0:

        current = q.popleft()

        depth -= 1

        for n in graph[current]:

            if n not in touched:

                touched.append(n)

                q.append(n)

Thanks for any possible help!

-Ben

[Aric Hagberg]

You can get that data from a shortest path calculation (which uses BFS).
e.g.

In [1]: import networkx as nx

In [2]: G=nx.Graph()

In [3]: G.add_edge('a','b')

In [4]: G.add_edge('b','c')

In [5]: G.add_edge('b','d')

In [6]: nx.single_source_shortest_path_length(G,'a')
Out[6]: {'a': 0, 'b': 1, 'c': 2, 'd': 2}

You can read the source at
http://networkx.lanl.gov/_modules/networkx/algorithms/shortest_paths/unweighted.html#single_source_shortest_path_length

Aric

[Benjamin Golder]

Thanks Aric!

2012/7/7 Aric Hagberg <aric.h...@gmail.com>

Aric

--
You received this message because you are subscribed to the Google Groups "networkx-discuss" group.
To post to this group, send email to networkx...@googlegroups.com.
To unsubscribe from this group, send email to networkx-discu...@googlegroups.com.
For more options, visit this group at http://groups.google.com/group/networkx-discuss?hl=en.