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

Question

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.

Answer 1

1. 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
   

2. 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.

Answer 2

1) Add one node x with an edge to every node in N and one node y with an edge to every node in M. Then check if there's an x--y path. Note - make sure x and y aren't already nodes.

G.add_edges_from([('x',node) for node in N])
G.add_edges_from([(node,'y') for node in M])
nx.has_path(N,M) #true if there was an M to N path

2)

augmented_paths = nx.all_simple_paths(G,source=x,target=y)

(this produces a generator).

for augmentedpath in nx.all_simple_paths(G, source=x, target=y):
    path = augmentedpath[1:-1] #don't want the x and y included
    print path