Re: double linked list
От | 71062.1056@compuserve.com (--CELKO--) |
---|---|
Тема | Re: double linked list |
Дата | |
Msg-id | c0d87ec0.0301291315.7ae946eb@posting.google.com обсуждение исходный текст |
Ответ на | Re: double linked list (71062.1056@compuserve.com (--CELKO--)) |
Список | pgsql-sql |
>> 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 VDO 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.
В списке pgsql-sql по дате отправления: