Re: transitive closure of a graph

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

>

>

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

>

I don't understand what you are trying to say here. Received on Thu Oct 13 2005 - 05:01:57 CEST