[Okta Webinar] Learn how to a build a cloud-first strategyRegister Now

x
?
Solved

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

Posted on 2006-04-07
7
Medium Priority
?
260 Views
Last Modified: 2013-12-24
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

0
Comment
Question by:typographia
  • 4
  • 3
7 Comments
 
LVL 16

Expert Comment

by:RCorfman
ID: 16462898
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
 

Author Comment

by:typographia
ID: 16464933

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
 
LVL 16

Expert Comment

by:RCorfman
ID: 16465272
This is going to depend on the database type if I can help or not. I could help with Oracle.
0
Free Tool: Path Explorer

An intuitive utility to help find the CSS path to UI elements on a webpage. These paths are used frequently in a variety of front-end development and QA automation tasks.

One of a set of tools we're offering as a way of saying thank you for being a part of the community.

 

Author Comment

by:typographia
ID: 16468457

I'm using MySQL...

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

Accepted Solution

by:
RCorfman earned 2000 total points
ID: 16468532
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
 

Author Comment

by:typographia
ID: 16469094
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
 
LVL 16

Expert Comment

by:RCorfman
ID: 16473480
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

Featured Post

Free Tool: IP Lookup

Get more info about an IP address or domain name, such as organization, abuse contacts and geolocation.

One of a set of tools we are providing to everyone as a way of saying thank you for being a part of the community.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Have you ever sent email via ColdFusion and thought of tracking this mail to capture the exact date and time when the message was opened ?  If yes, then this article is for you ! First we need a table user_email with columns user_id , email , sub…
Meet the world's only “Transparent Cloud™” from Superb Internet Corporation. Now, you can experience firsthand a cloud platform that consistently outperforms Amazon Web Services (AWS), IBM’s Softlayer, and Microsoft’s Azure when it comes to CPU and …
Screencast - Getting to Know the Pipeline
As many of you are aware about Scanpst.exe utility which is owned by Microsoft itself to repair inaccessible or damaged PST files, but the question is do you really think Scanpst.exe is capable to repair all sorts of PST related corruption issues?
Suggested Courses

834 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question