Re: transitive closure of a graph

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. Received on Wed Oct 12 2005 - 04:11:35 CEST