Re: transitive closure of a graph

vc wrote:
> Mikito Harakiri wrote:
> > vc wrote:
> > > 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)}
> >
> > I fail to see why. Start with the temporary table
> >
> > {(1,2), (2,1), (2,3), (3,2)}
> >
> > First join would produce new edges
> >
> > {(1,1), (2,2), (3,3), (1,3), (3,1)}
>
> The first join will produce
>
> {(1,1), (2,2), {2,2}, {3,3}, (1,3), (3,1)}
>
> Since we eliminate self-loops, it's actually {(1,3), {3,1)}.

No, I specifically mentioned that we don't need artificial cludges like eliminating self-loops. Query

with TransClosedEdges (tail, head) as
( select tail, head from Edges
  union /*no all*/
  select e.tail, ee.head from Edges e, TransClosedEdges ee   where e.head = ee.tail
)
select /*no distinct*/ * from TransClosedEdges

is good enough.

> >
> > With union semantics the temporary table inflates to
> >
> > {(1,1), (2,2), (3,3), (1,3), (3,1), (1,2), (2,1), (2,3), (3,2)}
>
> No matter the 'union', the next join will produce {(2,3), (2,1}} and
> so on:
>
> {{(1,2), (2,1), (2,3), (3,2), (1,3), {3,1), {2,3}, {2,1}, ... }

You seem to start confusing brackets there, but, regardless, here is a question. Given the set A = {1,2,3} what is the maximum cardinality of the set AxA ? Correct, 9 -- therefore, the ellipsis in the last expression don't make any sense. Received on Thu Oct 13 2005 - 02:14:44 CEST