I was wondering if anyone knows a good way to model a LinkedIn style "degrees of separation" between users (and their friends). Ideally I''d like to find the shortest path between people and also be able to display alternate paths. I suspect acts_as_tree is involved but haven''t thought much further. Thanks in advance. -- Posted via http://www.ruby-forum.com/. --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Ruby on Rails: Talk" group. To post to this group, send email to rubyonrails-talk-/JYPxA39Uh5TLH3MbocFFw@public.gmane.org To unsubscribe from this group, send email to rubyonrails-talk-unsubscribe-/JYPxA39Uh5TLH3MbocFFw@public.gmane.org For more options, visit this group at http://groups.google.com/group/rubyonrails-talk?hl=en -~----------~----~----~----~------~----~------~--~---
Hi Arshak-- This looks more like a graph than a tree problem to me. Most trees model a structure where there is exactly one path between any given pair of points (A, B). A graph takes into account the fact that there can be many such paths (which is why it''s used to model networks). Theory aside, if the nodes in your graph are in your database, it may become cumbersome to make this kind of computation more than "friend of a friend" deep. If you''re willing to limit it, then it''s just a self-referential join. Here''s a nice article on graphs in Python. It could be mapped to Ruby quite easily, but the challenge is neatly mapping it over an RDBMS. --steve On Apr 7, 2008, at 8:28 PM, Arshak Navruzyan wrote:> > I was wondering if anyone knows a good way to model a LinkedIn style > "degrees of separation" between users (and their friends). Ideally > I''d > like to find the shortest path between people and also be able to > display alternate paths. > > I suspect acts_as_tree is involved but haven''t thought much further. > > Thanks in advance. > -- > Posted via http://www.ruby-forum.com/. > > >--~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Ruby on Rails: Talk" group. To post to this group, send email to rubyonrails-talk-/JYPxA39Uh5TLH3MbocFFw@public.gmane.org To unsubscribe from this group, send email to rubyonrails-talk-unsubscribe-/JYPxA39Uh5TLH3MbocFFw@public.gmane.org For more options, visit this group at http://groups.google.com/group/rubyonrails-talk?hl=en -~----------~----~----~----~------~----~------~--~---
Oops. The link to the article: http://www.python.org/doc/essays/graphs.html On Apr 7, 2008, at 11:05 PM, s.ross wrote:> Hi Arshak-- > > This looks more like a graph than a tree problem to me. Most trees > model a structure where there is exactly one path between any given > pair of points (A, B). A graph takes into account the fact that > there can be many such paths (which is why it''s used to model > networks). Theory aside, if the nodes in your graph are in your > database, it may become cumbersome to make this kind of computation > more than "friend of a friend" deep. If you''re willing to limit it, > then it''s just a self-referential join. > > Here''s a nice article on graphs in Python. It could be mapped to > Ruby quite easily, but the challenge is neatly mapping it over an > RDBMS. > > --steve > > > On Apr 7, 2008, at 8:28 PM, Arshak Navruzyan wrote: > >> >> I was wondering if anyone knows a good way to model a LinkedIn style >> "degrees of separation" between users (and their friends). Ideally >> I''d >> like to find the shortest path between people and also be able to >> display alternate paths. >> >> I suspect acts_as_tree is involved but haven''t thought much further. >> >> Thanks in advance. >> -- >> Posted via http://www.ruby-forum.com/. >> >> >> >--~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Ruby on Rails: Talk" group. To post to this group, send email to rubyonrails-talk-/JYPxA39Uh5TLH3MbocFFw@public.gmane.org To unsubscribe from this group, send email to rubyonrails-talk-unsubscribe-/JYPxA39Uh5TLH3MbocFFw@public.gmane.org For more options, visit this group at http://groups.google.com/group/rubyonrails-talk?hl=en -~----------~----~----~----~------~----~------~--~---
Following up on my previous response to this, I ported the Python implementation to Ruby (for grins) and you can look it over at: http://pastie.caboo.se/177334 It could use some refactoring, and to be useful it needs abstraction of the data structure such that it refers to the database instead of a hash. It does, indeed, find the shortest path between two nodes (member), and all paths between two nodes. Hope this is interesting. Steve On Apr 7, 2008, at 8:28 PM, Arshak Navruzyan wrote:> > I was wondering if anyone knows a good way to model a LinkedIn style > "degrees of separation" between users (and their friends). Ideally > I''d > like to find the shortest path between people and also be able to > display alternate paths. > > I suspect acts_as_tree is involved but haven''t thought much further. > > Thanks in advance. > -- > Posted via http://www.ruby-forum.com/. > > >--~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Ruby on Rails: Talk" group. To post to this group, send email to rubyonrails-talk-/JYPxA39Uh5TLH3MbocFFw@public.gmane.org To unsubscribe from this group, send email to rubyonrails-talk-unsubscribe-/JYPxA39Uh5TLH3MbocFFw@public.gmane.org For more options, visit this group at http://groups.google.com/group/rubyonrails-talk?hl=en -~----------~----~----~----~------~----~------~--~---
Steve, you''re a gentleman and a scholar! Very interesting indeed! Thank you Arshak Steve Ross wrote:> Following up on my previous response to this, I ported the Python > implementation to Ruby (for grins) and you can look it over at: > > http://pastie.caboo.se/177334 > > It could use some refactoring, and to be useful it needs abstraction > of the data structure such that it refers to the database instead of a > hash. It does, indeed, find the shortest path between two nodes > (member), and all paths between two nodes. > > Hope this is interesting. > > Steve-- Posted via http://www.ruby-forum.com/. --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Ruby on Rails: Talk" group. To post to this group, send email to rubyonrails-talk-/JYPxA39Uh5TLH3MbocFFw@public.gmane.org To unsubscribe from this group, send email to rubyonrails-talk-unsubscribe-/JYPxA39Uh5TLH3MbocFFw@public.gmane.org For more options, visit this group at http://groups.google.com/group/rubyonrails-talk?hl=en -~----------~----~----~----~------~----~------~--~---