# Re: Floyd's algorithm in SQL

Date: 2 Dec 2004 03:22:04 -0800

Message-ID: <1101986524.436551.300750_at_c13g2000cwb.googlegroups.com>

--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;
**>
**> You could also have used a SQLSTATE code to detect any empty
**> insertion. I am not sure if that would actually be faster or not.
**>
**> SELECT * FROM Paths;
**> source destination lgth
**> =========================
**> a b 1
**> a e 1
**> b c 1
**> c d 1
**> d a 1
**> a c 2
**> b d 2
**> c a 2
**> d b 2
**> d e 2
**> a d 3
**> b a 3
**> c b 3
**> c e 3
**> d c 3
**> a a 4
**> b b 4
**> b e 4
**> c c 4
**> d d 4
**>
**> What I'd like to know is:
**>
**> 1) Can I put Paths in a VIEW defined by a recursive WITH operator? I
**> don't have a copy of a product that implements this SQL-99 feature.
**>
**> 2) Can I modify my SQL-92 code or the SQL-99 to handle the lowest
*

cost

> problem? That is, each edge has a positive cost; what is the

**CHEAPEST
**

> path from x to y, not the SHORTEST path?

*>
**> There is fame, glory and virtual beer in this puzzle.
*

Received on Thu Dec 02 2004 - 12:22:04 CET