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. Useyield
instead ofreturn
to get an endless stream of paths then when doingfor 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.