Re: transitive closure of a graph
Date: 12 Oct 2005 14:45:50 -0700
Message-ID: <1129153550.780006.41620_at_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 - 23:45:50 CEST