Re: transitive closure of a graph

From: vc <boston103_at_hotmail.com>
Date: 12 Oct 2005 20:01:57 -0700
Message-ID: <1129169095.729420.230870@g14g2000cwa.googlegroups.com>

Mikito Harakiri wrote:
> 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.

Ok. So without duplicates, we would have:

First, the current join set and TransClosedEdges: {(1,2), (2,1), (2,3), (3,2)}

then the current join set would be:

{(1,1), (2,2), (3,3), (1,3), (3,1)}

and TransClosedEdges would become (and stay unchanged):

{(1,1), (2,2), (3,3), (1,3), (3,1), (1,2), (2,1), (2,3), (3,2)}

then the next join set would be:

{(1,2), (2,1), (2,3),(3,2)}

and so on, never terminating (rather obvious, no ?)

> > 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.

I don't understand what you are trying to say here. Received on Wed Oct 12 2005 - 22:01:57 CDT