From: 71062.1056@compuserve.com (--CELKO--)
Subject: Re: double linked list
Date: 29 Jan 2003 13:15:51 -0800
Organization: http://groups.google.com/
Lines: 47
Message-ID: <c0d87ec0.0301291315.7ae946eb@posting.google.com>
References: <2ee07259.0301280744.582e4b7c@posting.google.com>
	<c0d87ec0.0301281554.581797ee@posting.google.com>
	<2ee07259.0301290412.5eb3290a@posting.google.com>
Content-Type: text/plain; charset=ISO-8859-2
Content-Transfer-Encoding: 8bit
To: pgsql-sql@postgresql.org

>> 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.