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


  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.


Need Your Help

Linux - system call not using all available CPU resources

linux ubuntu cpu-usage ubuntu-13.04

I'm performing mv dir1 dir2/ and dir1 has hundreds of thousands of files, so it's taking a while.

Best way to manage instance of a model

php model-view-controller oop

I'm working on a website and I used CodeIgniter as my framework, but I'm getting increasingly frustrated with the way they abuse OOP. I'm not a fan of OOP but when I use it I prefer a decent

About UNIX Resources Network

Original, collect and organize Developers related documents, information and materials, contains jQuery, Html, CSS, MySQL, .NET, ASP.NET, SQL, objective-c, iPhone, Ruby on Rails, C, SQL Server, Ruby, Arrays, Regex, ASP.NET MVC, WPF, XML, Ajax, DataBase, and so on.