Bookmark and Share

Floyd-Warshal algorithm in PostgreSQL PL/pgSQL.

Posted: Saturday, January 24th, 2009 at 12:04 pmUpdated: Friday, January 30th, 2009 at 10:11 pm

Running Floyd-Warshal PostgreSQL function

The goal was to find out the average degree of separation. As discussed in my other article Computing degrees of separation in social networking, the average degree of separation is 1.3. Below is how we will run the function and calculating degree of separation.

-- Run Floyd-Warshal Algorithm. The code below would return 1.
SELECT func_floyd_warshal();

-- Get the average degree of separation. Since weight is an int,
-- and count(*) would return int, the division result in PostgreSQL
--  would return an int as well. Since we need a floating number,
-- we need to cast the weight and count to float.
SELECT
	SUM(weight)::float / count(*)::float AS average_separation
FROM
	relationship
WHERE
	user_id <> friend_id
;

On SQL above, make sure when calculating the average of separation, you don’t count relationship of A -> A or B -> B. Otherwise, you’ll get a slightly different result.

There you have it … I hope you enjoyed this article. Please leave comments / suggestions / questions if you have. I’m looking forward to improving my solution with your comments / suggestions / questions.

Pages: 1 2 3 4

One Response to “Floyd-Warshal algorithm in PostgreSQL PL/pgSQL.”

  1. mateolan Says:

    In last paragraph on pg 1, I think you meant:
    “…that implies 3 -> 0 with weight 1 as well….”
    instead of:
    “…that implies 3 -> 1 with weight 1 as well…”
    Otherwise, thanks for a nice article, you are a good writer.

Leave a Reply

Time limit is exhausted. Please reload the CAPTCHA.