Recurring search too complex for me

Ruby
1

even if I am progressing, I’m still a newbie…

I need you advice on doing the follwing search

from an object <:id => 25> I would like to get the path up to another
object, ex <:id => 81>
using a :parent_collection to get up into the tree

my structure can be described accoding to this pattern

{id => 25, :parent_collection => [25,32,43,53], :data => “data25”}
{id => 26, :parent_collection => [26,11,10,9], :data => “data26”}
… and more
{id => 43, :parent_collection => [19,43,54,32], :data => “data43”}
{id => 44, :parent_collection => [5,44,8], :data => “data44”}
… and more
{id => 54, :parent_collection => [54, 81,12,18], :data => “data54”}
{id => 55, :parent_collection => [55,100,102], :data => “data55”}
… and more

result in this case is :
path = [25, 43, 54, 81]

this is trying to find a path in a tree between 2 objects… does it
exist a lib to do such searches ?

thanks for your help

joss

2

Dear Josselin,

if I understand you correctly, you are looking for
are solution to a path-finding problem in a graph -
so Dijkstra’s algorithm can do this for you.
There is a nice example of finding a shortest path between
several cities illustrating how the algorithm works here:

(unfortunately, the English wikipedia doesn’t have this
example, but from your email address I assume you read French anyway).
You can find an implementation of Dijkstra’s algorithm,
as well as many other graph algorithms, here:

http://gratr.rubyforge.org/

Best regards,

Axel