degrees of separation

rubyonrails-talk
#1

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.

#2

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

#3

Oops. The link to the article:

http://www.python.org/doc/essays/graphs.html

#4

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

#5

Steve, you're a gentleman and a scholar! Very interesting indeed!

Thank you

Arshak

Steve Ross wrote: