Re: double linked list

are you joe celko, guy who wrote those sql books?

"--CELKO--" <71062(dot)1056(at)compuserve(dot)com> wrote in message
news:c0d87ec0(dot)0301291315(dot)7ae946eb(at)posting(dot)google(dot)com(dot)(dot)(dot)
> >> The table at hand is more a kind of a collection of graphs where I
> want to find all possible paths between a given starting point and a
> given end point. <<
>
> For the reachabiity index of a general graph, you need Warshal's
> algorithm.
>
> Let V = number of nodes in the graph
> Let A[i,j] be the adjacency matrix for the undirected graph
>
> FOR j:= 1 TO V
> DO FOR i:= 1 TO V
> DO IF A[i,j] = 1
> THEN FOR k := 1 TO V
> DO IF A[j,k]] = 1
> THEN A[i,k]] := 1;
>
> You can also do a summation to get the length of the path from i to j.
> You can concatenate names of the nodes into a string that gives the
> path, etc.
>
> Her is a first attempt at some SQL; I am sure it can be done better
>
> CREATE TABLE Graph
> (i CHAR(2) NOT NULL,
> j CHAR(2) NOT NULL,
> flag CHAR(1) NOT NULL DEFAULT 'n'
> CHECK (flag IN ('n', 'y')),
> PRIMARY KEY (i,j));
>
> INSERT INTO Graph (i, j, flag)
> SELECT DISTINCT G1.i, G2.j, 'y'
> FROM Graph AS G1, Graph AS G1
> WHERE G1.i <> G2.j
> AND EXISTS
> (SELECT *
> FROM Graph AS G3
> WHERE G3.i = G1.j
> AND G3.j = G2.i)
> AND NOT EXISTS
> (SELECT *
> FROM Graph AS G3
> WHERE (G3.i = G1.i AND G3.j = G1.j))
> OR (G3.i = G2.i AND G3.j = G2.j));
>
> You wll have to run this statement until the size of Graph does not
> change -- no new rows are being added.