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

typographiaAsked:
Who is Participating?
I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

RCorfmanCommented:
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.
0
typographiaAuthor Commented:

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...
0
RCorfmanCommented:
This is going to depend on the database type if I can help or not. I could help with Oracle.
0
Cloud Class® Course: CompTIA Healthcare IT Tech

This course will help prep you to earn the CompTIA Healthcare IT Technician certification showing that you have the knowledge and skills needed to succeed in installing, managing, and troubleshooting IT systems in medical and clinical settings.

typographiaAuthor Commented:

I'm using MySQL...

But perhaps it is possible to utilize the oracle code to MySQL...
0
RCorfmanCommented:
From a coldfusion perspective, the answer is to use a stored database procedure to get the answer from the database. The actual mySQL code that it would take to do this is something best asked of the mySQL experts... the algorithm to do it is probably a good question for the programming experts.  If you have the points, you are truly going to be best off asking the programming experts for an algorithm, then the mySQL folks for a method of implementing the algorithm.

I could work up a set of searches in Oracle that would do this, but I doubt it would be the 'best' algorithm as my expertise is in database access and Cold fusion code, not in Search algorighms...  Since this really could be a pretty intensive task, finding the best way to go about it is going to be important.

I will stress again that you really do not want to be doing multiple select statements from Coldfusion to the database server to identify the answer in this case because it is going to be a complex set of searches in most cases. Often without finding an answer.
0

Experts Exchange Solution brought to you by

Your issues matter to us.

Facing a tech roadblock? Get the help and guidance you need from experienced professionals who care. Ask your question anytime, anywhere, with no hassle.

Start your 7-day free trial
typographiaAuthor Commented:
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.

0
RCorfmanCommented:
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.
0
It's more than this solution.Get answers and train to solve all your tech problems - anytime, anywhere.Try it for free Edge Out The Competitionfor your dream job with proven skills and certifications.Get started today Stand Outas the employee with proven skills.Start learning today for free Move Your Career Forwardwith certification training in the latest technologies.Start your trial today
Web Servers

From novice to tech pro — start learning today.

Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.