How to identify whether there exists a path between two nodes in an undirected graph

path_exists.py

"""
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