Implementing Floyd-Warshal Algorithm in PL/pgSQL

Now that we have the minimum and maximum values for user_id, we can start working on implementing Floyd-Warshal algorithm in PL/pgSQL. Now, the relationship table may be incomplete because not all user’s relations are stored there at the moment. E.g. relationship between user_id 0 and user_id 1 is not defined. In my PHP version, we can simply detect if the variable is defined or not.

if (!isset($relationship[$j][$k])) $relationship[$j][$k] = 999999;

In PL/pgSQL, here’s the equivalent. Note that res is a PL/pgSQL variable as defined in previous page.

SELECT INTO
	res weight
FROM
	relationship
WHERE
	user_id = j
	AND friend_id = k
;
IF res IS NULL THEN
	INSERT INTO relationship VALUES (j, k, 999999);
END IF;

Alright … so now all we have to do is the 3 FOR loop and keep inserting the data into relationship table if it’s not defined, calculate minimum weight value, and update the data with the new minimum weight value. Here’s the PL/pgSQL code to do that.

FOR i IN min_id .. max_id LOOP
	FOR j IN min_id .. max_id LOOP
		FOR k IN min_id .. max_id LOOP

			SELECT INTO res MIN(weight) FROM
			(
				SELECT weight FROM relationship WHERE user_id = j
					AND friend_id = k
				UNION ALL
				SELECT SUM(weight) AS weight FROM
				(
					SELECT weight FROM relationship WHERE
						user_id = j AND friend_id = i
					UNION ALL
					SELECT weight FROM relationship WHERE
						user_id = i AND friend_id = k
				) AS foo
			) AS floyd_warshal_result;

			UPDATE relationship SET weight = res WHERE user_id = j
				AND friend_id = k;
		END LOOP;
	END LOOP;
END LOOP;

Putting it all together

Now that we know how to

• Define PL/pgSQL as a language in PostgreSQL database
• Complete the relationship table
• Assign minimum and maximum user_id
• Define a relationship if it is not defined
• Define Floyd-Warshal algorithm in PL/pgSQL

We are ready to put it all together as a complete PL/pgSQL function definition. Here’s all the PostgreSQL command.

-- Written by Maresa Nirwan

-- http://www.microshell.com

-- Make sure to execute CREATE LANGUAGE statement only once.
CREATE TRUSTED PROCEDURAL LANGUAGE 'plpgsql'
	HANDLER plpgsql_call_handler
	VALIDATOR plpgsql_validator;

-- Start function definition
CREATE OR REPLACE FUNCTION func_floyd_warshal() RETURNS integer AS
$BODY$DECLARE
	min_id INTEGER;
	max_id INTEGER;
	res INTEGER;
BEGIN
	-- First, we need to make sure that relationship between user A and B are
	-- defined both ways. A -> B implies B -> A
	INSERT INTO relationship
	SELECT complete_relationship.* FROM
	(
		SELECT user_id, friend_id, weight FROM relationship
		UNION
		SELECT friend_id AS user_id, user_id AS friend_id, weight FROM relationship
	) AS complete_relationship
	LEFT JOIN relationship ON complete_relationship.user_id = relationship.user_id
		AND complete_relationship.friend_id = relationship.friend_id
	WHERE
		relationship.user_id IS NULL;

	-- Get the minimum and maximum user_id
	SELECT INTO min_id MIN(user_id) FROM relationship;
	SELECT INTO max_id MAX(user_id) FROM relationship;

	-- Begin Floyd-Warshal Algorithm
	FOR i IN min_id .. max_id LOOP
		FOR j IN min_id .. max_id LOOP
			FOR k IN min_id .. max_id LOOP

				-- If a relationship between 2 users are not defined, define them with a reasonably
				-- high relationship degree.
				SELECT INTO res weight FROM relationship WHERE user_id = j AND friend_id = k;
				IF res IS NULL THEN
					INSERT INTO relationship VALUES (j, k, 999999);
				END IF;

				SELECT INTO res weight FROM relationship WHERE user_id = j AND friend_id = i;
				IF res IS NULL THEN
					INSERT INTO relationship VALUES (j, i, 999999);
				END IF;

				SELECT INTO res weight FROM relationship WHERE user_id = i AND friend_id = k;
				IF res IS NULL THEN
					INSERT INTO relationship VALUES (i, k, 999999);
				END IF;

				-- This code calculates Floyd-Warshal's algoritm section to get the minimum path
				-- between 2 users.
				-- min ( path[i][j], path[i][k]+path[k][j] )
				SELECT INTO res MIN(weight) FROM
				(
					SELECT weight FROM relationship WHERE user_id = j AND friend_id = k
					UNION ALL
					SELECT SUM(weight) AS weight FROM
					(
						SELECT weight FROM relationship WHERE user_id = j AND friend_id = i
						UNION ALL
						SELECT weight FROM relationship WHERE user_id = i AND friend_id = k
					) AS foo
				) AS floyd_warshal_result;

				-- Assign the new minimum path to the relationship.
				UPDATE relationship SET weight = res WHERE user_id = j AND friend_id = k;
			END LOOP;
		END LOOP;
	END LOOP;

	-- This is a special case scenario. Relationship between A -> A is defined as 0.
	UPDATE relationship SET weight = 0 WHERE user_id = friend_id;

	RETURN 1;
END;$BODY$
  LANGUAGE 'plpgsql' VOLATILE;