Re: transitive closure of a graph

From: vc <boston103_at_hotmail.com>
Date: 12 Oct 2005 14:45:50 -0700
Message-ID: <1129153550.780006.41620@g47g2000cwa.googlegroups.com>

Mikito Harakiri wrote:
> Adam Machanic wrote:
> > That won't work for the following undirected graph:
> >
> > E
> > / /\ \
> > A / \ D
> > \ / \ /
> > B C
> >
> > CREATE TABLE Edges (point1 CHAR(1), point2 CHAR(1))
> >
> > INSERT Edges VALUES ('A', 'A')
> > INSERT Edges VALUES ('B', 'B')
> > INSERT Edges VALUES ('C', 'C')
> > INSERT Edges VALUES ('D', 'D')
> > INSERT Edges VALUES ('E', 'E')
> > INSERT Edges VALUES ('E', 'A')
> > INSERT Edges VALUES ('A', 'E')
> > INSERT Edges VALUES ('E', 'D')
> > INSERT Edges VALUES ('D', 'E')
> > INSERT Edges VALUES ('A', 'B')
> > INSERT Edges VALUES ('B', 'A')
> > INSERT Edges VALUES ('D', 'C')
> > INSERT Edges VALUES ('C', 'D')
> > INSERT Edges VALUES ('B', 'E')
> > INSERT Edges VALUES ('E', 'B')
> > INSERT Edges VALUES ('C', 'E')
> > INSERT Edges VALUES ('E', 'C')
> >
> >
> > ... I don't think a solution is possible without string or binary
> > manipulation, due to the fact that you only have access to the last anchor
> > in the recursive part. If you had access to the entire set of preceding
> > rows it might be different...

>

> If I see the problem correctly, here is step-by-step execution

>

> 1.
> AE, EA, AB, BA, CD, DC, BE, EB, CE, EC -- all included;
> the other edges in the candidate set
> AA, BB, CC, DD, EE -- all excluded as invalidating tail <> head
> predicate

>

> 2. AE+EB=AB, AE+EC=AC, ..., AD, DA, AC, CA, BD, DB, BC, CB, -- all
> included;
> the other edges in the candidate set
> AA, BB, CC, DD, EE -- all excluded as invalidating e.head = ee.tail
> predicate

>

> Including the AB edge twice is a big problem! Apparently, the source of
> the problem is DB2 and SQLServer 2005 artifact that they allow "union
> all" only...

The duplicates are not a problem at all. Since you represent the undirected graph with two bidirectional ones, the recursive query naturally fails as it encounters cycles. It will fail even on a trivial graph like that:

1---2---3

... if represented like {(1,2), (2,1), (2,3), (3,2)}

>

> P.S. Please don't remove the crossposts, as I might be lazy to look
> each of the 3 groups for followups.
Received on Wed Oct 12 2005 - 16:45:50 CDT