# Networkx graph: finding if path exists between any node in a given set of nodes and another set of nodes

I have a large undirected graph with hundreds of thousands of nodes and tens of thousands of edges. I have two separate problems:

1) For a set of nodes N = (node[1], node[2], node[3], node[4], node[5]) and, say, M = (node[1001], node[1002], node[1003], node[1004], node[1005]) does there exist a path between any node in N and any node in M?

I know there exists the nx.path.bidirectional_dijkstra() function but to use that I'd have to test all combinations N*M which is redundant (because many nodes would be queried multiple times), and since in practice the length of N/M may be in the thousands, this isn't practical.

2) A slightly separate problem, but is there a way to get a list of all paths from N to M?

I have a rough idea of how to "roll my own" solution to this, but I imagine it'd be many times slower than if someone has already done this, but not having a background in graph theory I don't even know what I need to search for! Thanks.

## Answers

Something like this should work:

def is_there_a_path(_from, _to): visited = set() # remember what you visited while _from: from_node = _from.pop(0) # get a new unvisited node if from_node in _to: # went the path return True # you need to implement get_nodes_referenced_by(node) for neighbor_node in get_nodes_referenced_by(from_node): # iterate over all the nodes the from_node points to if neighbor_node not in visited: # expand only unvisited nodes to avoid circles visited.add(neighbor_node) _from.append(neighbor_node) return False

You can build this out of the function from 1. by appending the path instead of neighbor_node but it takes much more time and circles may occur. Use yield instead of return to get an endless stream of paths then when doing for path in is_there_a_path(_from, _to):

This one is the algorithm from above that goes through the object graph in ruby and finds a path from self to another object, returning the path:

class Object # # breadth first search for references from the given object to self # def reference_path_to(to_object, length, trace = false) paths = [[to_object]] traversed = IdentitySet.new traversed.add(to_object) start_size = 1 if trace while not paths.empty? and paths.first.size <= length references = paths[0][0].find_references_in_memory # if we print here a SecurityError mey occur references.each{ |reference| return [reference] + paths[0] if reference.equal?(self) unless traversed.include?(reference) or paths.any?{ |path| reference.equal?(path)} paths.push([reference] + paths[0]) traversed.add(reference) end } if trace and start_size != paths[0].size puts "reference_path_length: #{paths[0].size}" start_size = paths[0].size end paths.delete_at(0) end return nil end end # from https://github.com/knub/maglevrecord/blob/60082fd8c16fa7974166b96e5243fc0a176d172e/lib/maglev_record/tools/object_reference.rb

The Python algorithm should do about the same as the ruby algorithm I think.