Unfortunately no one can be told what FluxBB is - you have to see it for yourself.
You are not logged in. Please login or register.
FluxBB.org Forums » Programming » Shortest path problem
Does anyone know a fast php & mysql implementation of a shortest path algorithm with fixed edge path costs?
I've seen implementations of Dijkstra's algorithm in T-SQL or PL/SQL, but I wonder if there is an implementation that would just allow to solve the "Friend of a Friend" problem with minimal costs.
Without having to spend half an hour Googling to find out, I'd just like to know what the hell you're referring to, in straight forward terms. 
And the onliest solution I've seen so far was done with Oracle (the only one being with better performance than the usual way)
Last edited by Felix (2008-05-19 19:12:05)
I want to build a "social network" extension and try to find the best way to implement a Friend of a Friend connection path. (Facebook has something like that I think)
e.g. We both have the same friend, but don't know each other. The algorithm should give me a path from me, over our same friend to you. (Me - Friend - You)
But it should also find connections, that have a bigger distance, e.g. (Me - Friend1 - Friend2 - Friend3 - You)
Know what I'm talking about?
@Felix: The Oracle implementation is what I meant with PL/SQL. The same guy also did a T-SQL (SQL-Server) implementation...
Last edited by Christian (2008-05-19 19:19:40)
Ah, right. That makes more sense. 
Sorry for that faux-pas
Just took a quick search and found the following Script:
http://sourceforge.net/projects/slashster/
No idea if it is of any use, but it sounds quite promising (looks like a pretty overhead aswell with 111kb)
Do you want to implement just the Friend of a Friend Connection but also the "real" FOAF Concept? (http://www.foaf-project.org/)
Hmm, MySQL can use T-SQL, no?
Slashster writes all the connections of a person to a file. It even looks like, that it has several bugs. Nevertheless it is a good starting point.
I've not thought of implementing the FOAF Concept by now, but it could be an extension to my extension later on.
@elbekko:
MySQL stored procedures are similar to both, T-SQL and PL/SQL, but MySQL only supports stored procedures since version 5.0 and this is not very widely used.
Also the implementations I found are a bit too heavy for just calculating the Friend Connection path.
@elbekko:
MySQL stored procedures are similar to both, T-SQL and PL/SQL, but MySQL only supports stored procedures since version 5.0 and this is not very widely used.
Also the implementations I found are a bit too heavy for just calculating the Friend Connection path.
What about PgSQL then? Can't say as I've delved into the area yet, (never really had a need to), but as far as I remember, that is far more advanced with regards to that area.
Are you talking about algorithms for finding the shortest path between two specific nodes (rather than a tree from a starting node to every other, like Dijkstra's)? I've researched that a lot... unless there have been any new discoveries since I last looked, there aren't any algorithms that are provably, consistently more time-efficient than Dijkstra's O(|E| log |V|), but there are a great deal of algorithms that use heuristics and/or preprocessing to improve (sometimes vastly) the running time of typical cases, though pathological cases might perform poorly. A good place to start is A*. Then look around on Google Scholar for more recent additions. I think Microsoft Research was putting out some interesting papers on that.
Only for my understanding: Isn't this exactly the Traveling salesman problem?
Travelling salesman is the shortest path that goes through every node, not the shortest path to a specific node.
Aah ok, I see Thanks
Oookay, I informed myself and tried some things...
I came up with that solution, which is quite limited, but it works... (somehow)
function searchNode($start, $end, $connection)
{
$sql = '
SELECT
r1.user_id AS node0,
r1.friend_id AS node1,
r2.friend_id AS node2,
r3.friend_id AS node3,
r4.friend_id AS node4
FROM relation r1
JOIN relation r2 ON r2.user_id = r1.friend_id
JOIN relation r3 ON r3.user_id = r2.friend_id
JOIN relation r4 ON r4.user_id = r3.friend_id
WHERE r1.user_id = \'%1$d\'
AND
( r2.user_id = \'%2$d\'
OR r2.friend_id = \'%2$d\'
OR r3.friend_id = \'%2$d\'
OR r4.friend_id = \'%2$d\' )
';
$sort = false;
if($start > $end)
{
$tStart = $end;
$end = $start;
$start = $tStart;
$sort = true;
}
$result = mysqli_query($connection, sprintf($sql, $start, $end));
while($row = mysqli_fetch_assoc($result))
{
if($sort == true)
$row = array_reverse($row);
echo '<pre>'.print_r($row, true).'</pre>';
}
}
searchNode(4, 1, $connection);$connection expects a mysqli_connection link.
Some Testdata:
CREATE TABLE `relation` (
`user_id` int(11) NOT NULL,
`friend_id` int(11) NOT NULL
) ENGINE=MyISAM DEFAULT CHARSET=utf8;
INSERT INTO `relation` (`user_id`, `friend_id`) VALUES
(1, 3),
(2, 4),
(3, 7),
(4, 0),
(5, 6),
(6, 4),
(7, 6),
(7, 8),
(0, 0),
(8, 1);It is far from perfect and I'm still testing it. No idea about its performance, wanted to get it fully working before comparing it to algorithms and other things.
Very open to comments and tips
That's funny, it looks similar to what I came up with:
deleted bad codeAs you said, its getting very slow, when there are a lot of users, but I'm planning to add an adminoption to specify the number of "joins".
Last edited by Christian (2008-05-21 20:57:53)
I'm planning for a max of 4 or 5 "hops", because everything about this is a) not performant and b) totally senseless for the current size of my community
So you're also developing a friend extension?
Actually yes... Tho it is pretty much in planning yet, because I wanted to wait until Beta3 before really getting into it.
Perhaps we could either exchange plans or even join the project? Let's have a talk
I already have some code for displaying the relations in the profile view:
I could possibly place a hook for calculating the relations, because I recognized that my algorithm didn't work in some special situations, which means I would have to pull more data from the DB and calculate the path in PHP as you seem to do.
In which situation did your algorithm fail?
I stored relations only in one direction beginning with the smallest user id (user_id|friend_id = 1|2 not 2|1), to handle the complete selection with sql, but that didn't work in situations where start id or end id of the algorithm are not stored in the correct columns. Its hard to describe, but I'm already trying to figure out, if there is a way to circumvent this problem.
Ok, I was able to solve the issue:
Looks better than the one in StudiVZ 
Christian,
Wold u like to help me for Shortest Path Problem?
I'm facing same problem as you.
Looking for your positive response.
Thanks in advance
Some posts above we posted "our" solution?
Or at least the best way we've found
FluxBB.org Forums » Programming » Shortest path problem
Powered by FluxBB
[ Generated in 0.032 seconds, 7 queries executed ]