# Re: Floyd's algorithm in SQL

From: Jarl Hermansson <jarl_at_mimer.com>
Date: Thu, 2 Dec 2004 11:28:16 +0000 (UTC)
Message-ID: <Xns95B37DC794338jarl_at_62.127.77.84>

Oops, my first attempt to answer was messed up. Here's what I was trying to post:

--CELKO-- wrote:
> I am re-doing the graphs section for the third edition of SQL FOR
> SMARTIES and would like some feedback and help.
>
> Here is a version of Floyd's algorithm to find the transitive closure
> of a graph. You can also look up Warshall's algorithm, which is an
> earlier and more specialized version of Floyd's algorithm. Given a
> directed graph G represented by an adjacency matrix A[i, j], WHERE
> A[i, j] = 1 if the edge (i, j) is in the graph, compute the matrix P
> of paths with their lengths. Now put it into SQL:
>
> CREATE TABLE Paths
> (source CHAR(1)NOT NULL,
> destination CHAR(1) NOT NULL,
> lgth INTEGER DEFAULT 0 NOT NULL);
>
> CREATE TABLE Edges
> (source CHAR(1)NOT NULL,
> destination CHAR(1)NOT NULL,
> PRIMARY KEY (source, destination),
> lgth INTEGER DEFAULT 1 NOT NULL);
>
> INSERT INTO Edges (source, destination) VALUES ('a', 'b');
> INSERT INTO Edges (source, destination) VALUES ('b', 'c');
> INSERT INTO Edges (source, destination) VALUES ('c', 'd');
> INSERT INTO Edges (source, destination) VALUES ('d', 'a');
> INSERT INTO Edges (source, destination) VALUES ('a', 'e');
>
> The algorithm extends each known path by one edge at a time. Since no
> path can be longer than the number of nodes in the graph, we have an
> upper bound on iterations. But we can also stop when the INSERT
> statement adds no new paths.
>
> CREATE PROCEDURE Floyd()
> LANGUAGE SQL
> DETERMINISTIC
> BEGIN
> DECLARE old_path_tally INTEGER;
> SET old_path_tally = 0;
> DELETE FROM Paths; -- clean out working table
> INSERT INTO Paths SELECT * FROM Edges; -- load the edges
>
> -- add one edge to each path
> WHILE old_path_tally < (SELECT COUNT(*) FROM Paths)
> DO INSERT INTO Paths (source, destination, lgth)
> SELECT E1.source, P1.destination, (E1.lgth + P1.lgth)
> FROM Edges AS E1, Paths AS P1
> WHERE E1.destination = P1.source
> AND NOT EXISTS -- path is not here already
> (SELECT *
> FROM Paths AS P2
> WHERE E1.source = P2.source
> AND P1.destination = P2.destination);
> SET old_path_tally = (SELECT COUNT(*) FROM Paths);
> END WHILE;
> END;
Celko,