Received: from localhost (postgresql.org [64.49.215.8])
	by postgresql.org (Postfix) with ESMTP id DC7CF476086
	for <pgsql-sql@postgresql.org>; Wed, 29 Jan 2003 16:30:42 -0500 (EST)
Received: from news.hub.org (news.hub.org [64.49.215.80])
	by postgresql.org (Postfix) with ESMTP id 4C1BF4758E1
	for <pgsql-sql@postgresql.org>; Wed, 29 Jan 2003 16:30:42 -0500 (EST)
Received: by news.hub.org (Postfix, from userid 8)
	id 0822143A6B3; Wed, 29 Jan 2003 16:30:41 -0500 (EST)
From: "Ryan" <rgaffuri@cox.net>
X-Newsgroups: comp.databases.theory, comp.databases.rdb,
	comp.databases.postgresql.sql, comp.databases.oracle.misc
References: <2ee07259.0301280744.582e4b7c@posting.google.com>
	<c0d87ec0.0301281554.581797ee@posting.google.com>
	<2ee07259.0301290412.5eb3290a@posting.google.com>
	<c0d87ec0.0301291315.7ae946eb@posting.google.com>
Subject: Re: double linked list
Lines: 53
X-Priority: 3
X-MSMail-Priority: Normal
X-Newsreader: Microsoft Outlook Express 6.00.2600.0000
X-MimeOLE: Produced By Microsoft MimeOLE V6.00.2600.0000
Message-ID: <DJXZ9.53859$GX4.2201155@news2.east.cox.net>
Date: Wed, 29 Jan 2003 21:30:11 GMT
X-Complaints-To: abuse@cox.net
Organization: Cox Communications
To: pgsql-sql@postgresql.org
X-Virus-Scanned: by AMaViS new-20020517
X-Archive-Number: 200302/18
X-Sequence-Number: 11416

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

"--CELKO--" <71062.1056@compuserve.com> wrote in message
news:c0d87ec0.0301291315.7ae946eb@posting.google.com...
> >> 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.