Pathfinding in community

[Martin Berg]

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

[Andy Hassall]

Re: Pathfinding in community

On 1 Feb 2005 01:52:17 -0800, crontab@gmx.de (Martin Berg) wrote:
[color=blue]
>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?[/color]

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/detail.php?type=snippet&id=714

Not sure what "AStern" is - could you be referring to A*, or is AStern a
variation on A*?
[color=blue]
>Some facts:
>- PHP
>- Mysql database
>- table "members" with the field "member_id"
>- table "contact" with the fields "member_id" , "contact_member _id"[/color]

--
Andy Hassall / <andy@andyh.co. uk> / <http://www.andyh.co.uk >
<http://www.andyhsoftwa re.co.uk/space> Space: disk usage analysis tool

[Sean]

Re: Pathfinding in community

On 1 Feb 2005 01:52:17 -0800, crontab@gmx.de (Martin Berg) reverently
intoned upon the aether:
[color=blue]
> 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"[/color]

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

[Matthias Esken]

Re: Pathfinding in community

Martin Berg schrieb:
[color=blue]
> I heard about "Dijkstra" or "AStern". Can these alogs help me with my
> problem?[/color]

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

Regards,
Matthias