asked on

Shortest path from user to user (like Friendster / Six degrees of separation)

Hi,

we are currently developing a friendship community for our party network. We have a connection-table which stores all accepted friendships.

It looks like:

fromid toid (inviting person; accepting person)
1 -> 2
1 -> 3
2 -> 5
3 -> 4
5 -> 2
5 -> 4
6 -> 5
6 -> 4

When user 1 visits the nickpage of user 6 we'd like to show ONE shortest path from 1 to 6

e.g. username 1 --- username 2 --- username 5 --- username 6

If there is more than 1 possibility the user should have an additional function to see the alternatives:

e.g. username 1 --- username 2 --- username 5 --- username 6
or username 1 --- username 3 --- username 4 --- username 6

Thanks in advance,

Rene

RCorfman

Since this is going to be a database intensive task no matter which way you slice it, you should really look to create a stored database procedure to solve it. Then you would call the procedure using <CFSTOREDPROC> Using that tag, you can call your database procedure that solves this, and display the results on the web-page.

Anytime you get into a database intensive task, you want to minimize the trips between the database and the web-server. <CFSTOREDPROC> will do this for you.

typographia

ASKER

Thanks for your comment.

But does anyone have an idea, how to get the right output from the database?

I have no idea how to solve this problem...

RCorfman

This is going to depend on the database type if I can help or not. I could help with Oracle.

typographia

ASKER

I'm using MySQL...

But perhaps it is possible to utilize the oracle code to MySQL...

ASKER CERTIFIED SOLUTION

RCorfman

membership

This solution is only available to members.

To access this solution, you must be a member of Experts Exchange.

Start Free Trial

typographia

ASKER

GOT IT!

I found an answer in Google News:
http://groups.google.de/group/comp.lang.php/browse_thread/thread/98636f64a49d4438/4532f072fc8476d8?lnk=st&q=friendster+mysql&rnum=3&hl=de#4532f072fc8476d8

It's the best (and fastest way) to repeat querying the database till the first recordcount is greater "0":

First:
<cfquery name="query1" datasource="...">
select * from connections where fromid='#from#' and toid='#to#'
</cfquery>

Second:
<cfquery name="query2" datasource="...">
SELECT
k1.fromid AS fromid,
k2.fromid AS through,
k2.toid AS toid
FROM connections AS k1 LEFT JOIN connections AS k2 ON k1.toid=k2.fromid
WHERE k1.fromid='#from#' and k2.toid='#to#'
</cfquery>

Third:
<cfquery name="query3" datasource="...">
SELECT
k1.fromid AS fromid,
k2.fromid AS through1,
k3.fromid AS through2,
k3.toid AS toid
FROM (connections AS k1 LEFT JOIN connections AS k2 ON k1.toid=k2.fromid)
LEFT JOIN connections AS k3 ON k2.toid=k3.fromid
WHERE k1.fromid='#from#' and k3.toid='#to#'
</cfquery>

Last:
<cfquery name="query4" datasource="...">
SELECT
k1.fromid AS fromid,
k2.fromid AS through1,
k3.fromid AS through2,
k4.fromid AS through3,
k4.toid AS toid
FROM ((connections AS k1 LEFT JOIN connections AS k2 ON k1.toid=k2.fromid)
LEFT JOIN connections AS k3 ON k2.toid=k3.fromid)
LEFT JOIN connections AS k4 ON k3.toid=k4.fromid
WHERE k1.fromid='#from#' and k4.toid='#to#'
ORDER BY through1,through2,through3
</cfquery>

Tested with a MySQL Table containing 280.000 records and 100.000 different userids.

RCorfman

You should look at packaging this functionality up in mysql (I assume it supports packaged procedures), then calling it from coldfusion. This will minimise the multiple calls. I am glad you found a good solution.