Calculating all paths between any two nodes in a graph

[sourcecode language="python"]
/usr/bin/python
import networkx as nx
from collections import deque
import matplotlib.pyplot as plt
g=nx.MultiGraph()
g.add_edge(1,2)
g.add_edge(1,3)
g.add_edge(1,5)
g.add_edge(2,1)
g.add_edge(2,3)
g.add_edge(2,4)
g.add_edge(3,4)
g.add_edge(4,3)
g.add_edge(5,6)
g.add_edge(5,4)
g.add_edge(6,3)
g.add_edge(8,9)

path_queue=deque()
def BFS(graph,start,end,q):
temp_path = [start]
q.append(temp_path)
while len(q)>0:
tmp_path = q.popleft()
last_node = tmp_path[len(tmp_path)-1]
#print “Checking the path:\t\t”,tmp_path
if last_node == end:
print “VALID_PATH : “,tmp_path
for link_node in graph[last_node]:
if link_node not in tmp_path:
new_path = []
new_path = tmp_path + [link_node]
q.append(new_path)

BFS(g,1,4,path_queue)
nx.draw(g)
plt.show()
[/sourcecode]

Tagged with:
Posted in Uncategorized

Leave a Reply

Your email address will not be published. Required fields are marked *

*

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>