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

### Linux - system call not using all available CPU resources

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

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.