473,320 Members | 1,926 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,320 software developers and data experts.

Pathfinding in community

Hi,

I am providing a community.
Each member is able to add his own contacts at the community.

For example:

A knows B
A knows F
B knows C
C knows D

I want to find the shortest path between A and D so that I can display

A knows D because he/she knows C and C knows D

Do you have any solutions? I think a recurive function would work, but
in my opinion it would be too slow.

I heard about "Dijkstra" or "AStern". Can these alogs help me with my
problem?

Some facts:
- PHP
- Mysql database
- table "members" with the field "member_id"
- table "contact" with the fields "member_id", "contact_member_id"

Bye
Mad
Jul 17 '05 #1
3 1889
On 1 Feb 2005 01:52:17 -0800, cr*****@gmx.de (Martin Berg) wrote:
I am providing a community.
Each member is able to add his own contacts at the community.

For example:

A knows B
A knows F
B knows C
C knows D

I want to find the shortest path between A and D so that I can display

A knows D because he/she knows C and C knows D

Do you have any solutions? I think a recurive function would work, but
in my opinion it would be too slow.

I heard about "Dijkstra" or "AStern". Can these alogs help me with my
problem?
Dijkstra's algorithm would certainly cover it. It's standard fare for
computing courses so there are thousands of hits for it on Google. It's usually
used on weighted graphs; your edges all have uniform weights so it simplifies
it further.

One example in PHP would be:
http://www.phpbuilder.com/snippet/de...snippet&id=714

Not sure what "AStern" is - could you be referring to A*, or is AStern a
variation on A*?
Some facts:
- PHP
- Mysql database
- table "members" with the field "member_id"
- table "contact" with the fields "member_id", "contact_member_id"


--
Andy Hassall / <an**@andyh.co.uk> / <http://www.andyh.co.uk>
<http://www.andyhsoftware.co.uk/space> Space: disk usage analysis tool
Jul 17 '05 #2
On 1 Feb 2005 01:52:17 -0800, cr*****@gmx.de (Martin Berg) reverently
intoned upon the aether:
Hi,

I am providing a community.
Each member is able to add his own contacts at the community.

For example:

A knows B
A knows F
B knows C
C knows D

I want to find the shortest path between A and D so that I can display

A knows D because he/she knows C and C knows D

Do you have any solutions? I think a recurive function would work, but
in my opinion it would be too slow.

I heard about "Dijkstra" or "AStern". Can these alogs help me with my
problem?

Some facts:
- PHP
- Mysql database
- table "members" with the field "member_id"
- table "contact" with the fields "member_id", "contact_member_id"


Dijkstra's algorithm is simply a refined breadth first search. You
can find a visual example of it at:

http://www.eas.asu.edu/trace/eee459/sriram.html

A good starting place to learn more with readable pseudo-code:

http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

In your case all the edges on the graph have the same weight, so as
already noted, your problem is greatly simplified. It should be noted
here that you still have a directed graph. For instance, in the above
example, A knows D at a cost of 3 (A->B->C->D), but D does not know A.
Or you could choose to make your relationship symmetric. Then A->B
implies B->A. How you choose to handle this affects how to construct
your graph.

In this case, I would suggest first selecting the entire table. Then
I would suggest loading this data into an array of arrays.
Recursively performing database queries could get very expensive in
terms of time and network resources. Then use this array as your map
of the graph. How you create this array depends on if you want your
A->B to imply B->A.

Since all the efficient algorithms I know of for this type of problem
are breadth first, you should use an iterative algorithm. Using
recursion will give a depth first algorithm which will waste CPU time.

I would suggest exploring doing an update every time a user updates
their contacts and storing the results in the database rather than
calculating it all the time as it could get computationally expensive
with a lot of users.

hope this helps,

Sean

"In the End, we will remember not the words of our enemies,
but the silence of our friends."

- Martin Luther King Jr. (1929-1968)

Photo Archive @ http://www.tearnet.com/Sean
Last Updated 29 Sept. 2004
Jul 17 '05 #3
Martin Berg schrieb:
I heard about "Dijkstra" or "AStern". Can these alogs help me with my
problem?


I implemented A* in PHP and it's not what you need.

Regards,
Matthias
Jul 17 '05 #4

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

1
by: M.M. | last post by:
Hi all, The Java community is working on the adoption of Groovy as a JCP standard (http://www.jcp.org/en/jsr/detail?id=241). Groovy is a dynamic/agile language for Java...
8
by: Chua Wen Ching | last post by:
Hi there. I was wondering is there any C# A* Pathfinding source code! I try to find and the best place is planetsourcecode vb.net A* Pathfinding... but vb.net syntax is too different if...
2
by: eBay Sellers Community | last post by:
-- If you like eBay and enjoy buying and selling there. Please take the time to join the site below! eBay Sellers Community http://www.ebay-sellers-community.com
1
by: Edward | last post by:
I've studied Portal, Report, whose whitepaper can tell the mechanism at the first time, but Community is different. I succeeded in localizing the page to chinese, but that experience didn't make...
10
by: VB Programmer | last post by:
1. Is there an ASP.NET 2.0 version available yet? 2. Is there a VB.NET version available? 3. How do I install the source version on my dev machine (I have SQL Server 2000, VS.NET, IIS, etc...)...
5
by: metaperl.bzr | last post by:
hi everyone, I am the first of what may be hundreds of refugees from the Perl community. Not only is Python a more productive language, with many more nice apps, but the people are friendly as...
1
by: flit | last post by:
Hi all, I had one problem with csv files. And I put the message on 2 microsoft board and in this group. Results: No response from microsoft, and always 3 responses for posts on this lists....
1
by: socialdetour | last post by:
I hope that this isn't received as spam, but I would like to announce my new ASP.NET-based community website to the .NET community. The product is designed to handle complex user profiles,...
0
by: Steve Holden | last post by:
For those who weren't at PyCon, or who missed the announcement (which seems to include all of the recipients :-) I have just made a post in the PSF blog to publicize the first PSF Community Awards....
0
by: DolphinDB | last post by:
Tired of spending countless mintues downsampling your data? Look no further! In this article, you’ll learn how to efficiently downsample 6.48 billion high-frequency records to 61 million...
0
by: ryjfgjl | last post by:
ExcelToDatabase: batch import excel into database automatically...
0
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
1
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
0
by: Vimpel783 | last post by:
Hello! Guys, I found this code on the Internet, but I need to modify it a little. It works well, the problem is this: Data is sent from only one cell, in this case B5, but it is necessary that data...
0
by: jfyes | last post by:
As a hardware engineer, after seeing that CEIWEI recently released a new tool for Modbus RTU Over TCP/UDP filtering and monitoring, I actively went to its official website to take a look. It turned...
0
by: CloudSolutions | last post by:
Introduction: For many beginners and individual users, requiring a credit card and email registration may pose a barrier when starting to use cloud servers. However, some cloud server providers now...
0
by: Defcon1945 | last post by:
I'm trying to learn Python using Pycharm but import shutil doesn't work
0
by: af34tf | last post by:
Hi Guys, I have a domain whose name is BytesLimited.com, and I want to sell it. Does anyone know about platforms that allow me to list my domain in auction for free. Thank you

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.