# Degrees of separation

**URL:** <https://www.ruby-forum.com/t/degrees-of-separation/134130>\
**Category:** Rails\
**Created:** [April 8, 2008, 5:28am UTC](https://www.ruby-forum.com/t/degrees-of-separation/134130 "2008-04-08T05:28:19Z")\
**Posts on this page:** 5\
**Page:** 1

<div class="post-metadata">

**Author:** ![arshak](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/a/85e7bf/32.png) [@arshak](https://www.ruby-forum.com/u/arshak)\
**Post date:** [April 8, 2008, 5:28am UTC](https://www.ruby-forum.com/t/degrees-of-separation/134130/1 "2008-04-08T05:28:19Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![arshak](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/a/85e7bf/32.png) [@arshak](https://www.ruby-forum.com/u/arshak)\
**Post date:** [April 8, 2008, 8:07am UTC](https://www.ruby-forum.com/t/degrees-of-separation/134130/2 "2008-04-08T08:07:13Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![arshak](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/a/85e7bf/32.png) [@arshak](https://www.ruby-forum.com/u/arshak)\
**Post date:** [April 8, 2008, 8:08am UTC](https://www.ruby-forum.com/t/degrees-of-separation/134130/3 "2008-04-08T08:08:59Z")

</div>

Oops. The link to the article:

[http://www.python.org/doc/essays/graphs.html](http://www.python.org/doc/essays/graphs.html)

---

<div class="post-metadata">

**Author:** ![arshak](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/a/85e7bf/32.png) [@arshak](https://www.ruby-forum.com/u/arshak)\
**Post date:** [April 9, 2008, 6:32am UTC](https://www.ruby-forum.com/t/degrees-of-separation/134130/4 "2008-04-09T06:32:49Z")

</div>

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

Thank you

Arshak

Steve R. 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:
> 
> [Parked at Loopia](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

---

<div class="post-metadata">

**Author:** ![arshak](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/a/85e7bf/32.png) [@arshak](https://www.ruby-forum.com/u/arshak)\
**Post date:** [April 8, 2008, 7:37pm UTC](https://www.ruby-forum.com/t/degrees-of-separation/134130/5 "2008-04-08T19:37:26Z")

</div>

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](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