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

Completing relationship table

What I mean about completing relationship table is to define relationship 3 -> 1 whenever 1 -> 3 is defined. Thus, we’ll always have both directions of friendship relationship. Doing this can be done in straight SQL. Here’s what we need to do:

  1. Select all existing data from relationship table.
  2. Union it with the reverse direction relationship.
  3. Get the result of the union that doesn’t exist in existing table
  4. Insert the data above into relationship table.

Here’s the SQL to do that:

-- 4. Insert the resulting data into relationship.
INSERT INTO relationship
SELECT complete_relationship.* FROM

	-- 1. Select all existing data from relationship table.
	SELECT user_id, friend_id, weight FROM relationship
	-- 2. Reverse direction relationship.
	SELECT friend_id AS user_id, user_id AS friend_id, weight FROM relationship

) AS complete_relationship

-- 3. Data that doesn't exist in existing table
LEFT JOIN relationship ON complete_relationship.user_id = relationship.user_id
	AND complete_relationship.friend_id = relationship.friend_id
	relationship.user_id IS NULL;

Start working towards Floyd-Warshal algorithm function

I’d like to try to make this function as closely resembles my PHP version that I wrote before in the article Computing degrees of separation in social networking.

Defining Variables

Unlike the PHP version, PostgreSQL’s stored procedure function has access to the relationship data. Within the function, we can get the relationship data and the minimum & maximum user_id simply by querying relationship table. So let’s define the variables. First, we need to declare the variable to be used in PL/pgSQL.

	min_id INTEGER;
	max_id INTEGER;

Then we need to populate the variables. Note that we can simply select the minimum and maximum values of user_id because we’ve made the table “complete”; e.g. relationship between 0 -> 3 and 3 ->0 are defined.

	SELECT INTO min_id MIN(user_id) FROM relationship;
	SELECT INTO max_id MAX(user_id) FROM relationship;

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.