Skip to content

Instantly share code, notes, and snippets.

@ericmjl

ericmjl/path_exists.py

Last active Aug 29, 2015
Embed
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"
implementation.
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():
paths.append(set([node]))
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)
paths.pop(paths.index(path1))
paths.pop(paths.index(path2))
paths.append(new_path)
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
break
return boolean
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment