Skip to content

Instantly share code, notes, and snippets.



Last active Aug 29, 2015
What would you like to do?
How to identify whether there exists a path between two nodes in an undirected graph
Author: Eric J. Ma
Affiliation: Massachusetts Institute of Technology.
Purpose of Code:
This code was written because I did not find a sufficiently-concise way of identifying whether
two nodes were connected by some path. Bidirectional Djikstra as implemented in NetworkX returns
False is not connected, but (length, path) if connected; I wanted a pure "True/False"
This code works for all kinds of NetworkX graphs; however, it will treat them all as being
undirected graphs.
def paths(G):
This method will return a set of paths between all nodes present in the graph G
as a disjoint set data structure. This is a naive implementation that probably can
be improved.
paths = []
for node in G.nodes():
def find_set_with_node(paths, node):
This method will return the set of nodes that contains the specified element.
for path in paths:
if node in path:
return path
for edge in G.edges():
path1 = find_set_with_node(paths, edge[0])
path2 = find_set_with_node(paths, edge[1])
new_path = path1.union(path2)
def path_exists(G, node1, node2):
This method will return True if a path exists between two nodes.
boolean = False
paths = paths(G)
for path in paths:
if node1 in path and node2 in path:
return True
return boolean
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment