how to find BFS in weighted graph in networkx

[sampath methuku]

i am doing a project on graph using networkx. i want to find a
tree from a graph such that from a give source nodes(root) ,
shortest path form root to all other nodes is included in the tree .
( ex: similar to BFS in unweighted graphs).


I want result in the form of graph G.

sample pseudo code:

H=nx.parallelBFS(G,v); where H is also a graph

[Christian Guckelsberger]

This sounds like a SSSP (Single source shortest path) problem for
weighted graphs. Take Dijkstra's algorithm in case you got no negative
edge weights or Bellman-Ford's algorithm otherwise. It's both included
in networkx, just look for the keywords.

Cheers,
Chris

[sampath methuku]

Withs SSSP(Single source shortest path)  it is giving path   not the edge weights. actually   i need  the subgraph of given graph with centered at vertex v  and contains all nodes( also edges connecting these nodes) which can be reached form that vertex v with distance   d  .

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

[Ben Edwards]

single_source_dijkstra_path has a cutoff keyword. You might to something like this:

import networkx as nx

d = 3

v = 4

G = nx.barabasi_albert_graph(100,3)

sssp = nx.single_source_dijkstra_path(G, source=v, cutoff=3,weight='weight')

neigh_d = nx.utils.flatten(sssp.values())

G_subgraph = nx.subgraph(G,neigh_d)

This should compute the subgraph of all the nodes distance d=3 from node v=4, with the weight key on the edges being 'weight'. This might be memory inefficient. You could probably hand code the bfs to get better memory performance. 

The documentation might be out of date I think, at least in my version, I'll see about updating it.

Ben

To post to this group, send email to networkx...@googlegroups.com.
To unsubscribe from this group, send email to networkx-discu...@googlegroups.com.