Re: double linked list

From: Juergen <jasche_at_gmx.de>
Date: 31 Jan 2003 04:49:24 -0800
Message-ID: <2ee07259.0301310449.2cbc1468@posting.google.com>

first of all thanks for Your answers. They certainly gave me direction on what to learn concerning SQL.

Being a novice in SQL and after doing just a couple of days of research on that matter I got the impression that SQL hasn't yet evolved to that point to provide simple to use keywords for these kind of problems. Oracle 9i seems to
have been progressed over 8i in this regard. One can use subqueries with the *with as* clause, one can use the *connect by* statement on views and joined statements and there may be a couple of other features...
However I am restricted to 8i and java and the requirement not to use pl/sql for the sake of a common code base.

Currently I figure to use

  select cs, cb, level
    from link_t
   start with cb in (

 	    select cb
              from link_t
             where ´cs = 'A')

 connect by prior cb = cs

that will return a tree containing all paths with the root as the common starting point. I would load this structure into a middle teer and apply some sort of commonly used tree traversial algorithm to it to search for nodes and endpoints of interest.

Cheers and thanks again

Juergen

71062.1056_at_compuserve.com (--CELKO--) wrote in message news:<c0d87ec0.0301291315.7ae946eb_at_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.
Received on Fri Jan 31 2003 - 06:49:24 CST