Re: transitive closure of a graph

From: Mikito Harakiri <mikharakiri_nospaum_at_yahoo.com>
Date: 13 Oct 2005 11:52:02 -0700
Message-ID: <1129229522.477451.134650_at_g49g2000cwa.googlegroups.com>

Serge Rielau wrote:
> Mikito Harakiri wrote:
> > Mikito Harakiri wrote:
> >
> >>Transitive closure (TC) of a graph is
> >>
> >>with TransClosedEdges (tail, head) as
> >>( select tail, head from Edges
> >> union all
> >> select e.tail, ee.head from Edges e, TransClosedEdges ee
> >> where e.head = ee.tail
> >>)
> >>select distinct * from TransClosedEdges
> >>
> >>except that this query might never terminate.
> >
> >
> > Oops, it's actually quite obvious
> >
> > with TransClosedEdges (tail, head) as
> > ( select tail, head from Edges
> > where tail <> head --*******
> > union all
> > select e.tail, ee.head from Edges e, TransClosedEdges ee
> > where e.head = ee.tail
> > and e.tail <> ee.head --*******
> > )
> > select distinct * from TransClosedEdges
> >
> > Graeme handles more general case, hence the complication.
> >
> There will be a new developerWorks article on mapping CONnECT BY to DB2
> tomorrow (if all goes well).

See your article. Unfortunately, understanding code in C is beyond my capabilities. What is "binary-encoded path"? Suppose we have

Name Sal
------------ ---

KING         100
--> SMITH     50

-----> JONES 20
-----> JAMES 30 What is the binary-encoded path for JAMES node is? Received on Thu Oct 13 2005 - 20:52:02 CEST