recurring search too complex for me

[Josselin]

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 arent_collection to get up into the tree

my structure can be described accoding to this pattern

{id => 25, arent_collection => [25,32,43,53], :data => "data25"}
{id => 26, arent_collection => [26,11,10,9], :data => "data26"}
..... and more
{id => 43, arent_collection => [19,43,54,32], :data => "data43"}
{id => 44, arent_collection => [5,44,8], :data => "data44"}
..... and more
{id => 54, arent_collection => [54, 81,12,18], :data => "data54"}
{id => 55, arent_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

 

[Axel Etzold]

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:

http://fr.wikipedia.org/wiki/Algorithme_de_Dijkstra

(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