Forum: Ruby recurring search too complex for me

Announcement (2017-05-07): is now read-only since I unfortunately do not have the time to support and maintain the forum any more. Please see and for other Rails- und Ruby-related community platforms.
6b2144362fffd4f71cca755d4045846f?d=identicon&s=25 Josselin (Guest)
on 2007-07-11 15:24
(Received via mailing list)
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

D0338c0de4cb3c5c17300396159933d1?d=identicon&s=25 Axel Etzold (Guest)
on 2007-07-11 16:36
(Received via mailing list)
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:

Best regards,

This topic is locked and can not be replied to.