Re: transitive closure concept

Date view Thread view Subject view Author view Attachment view

From: Adrian Carcu (
Date: Sun 25 Jan 2004 - 02:45:06 GMT


I think an iterative version of closure can be achieved using iterate's
accumulator and unions of sets. The example below generates all the
subclasses of a class. Although in this example there are no cycles,
the code works for cycles too.

def: let iclosure:Set(GeneralizableElement)=
	  ac:Set(GeneralizableElement) = Set{self} |

I'm sure the code can be further optimized/simplified (maybe the number of
steps, the fact that each iteration expands all the nodes, even those already

There is a more efficient recursive version that handles cycles.
The set s is used to keep track of the already included nodes to avoid

def: let rclosure(s:Set(GeneralizableElement)):Set(GeneralizableElement)=
    	  if s->includes(self) then s
    	  else self.specialization.child->iterate(it:GeneralizableElement;
    	    		ac:Set(GeneralizableElement) = s->including(self) |

Can be invoked using: someinstance.rclosure(Set{}).

I'd be interested in shorter/more efficient variations if anyone has ideas or
if there are some papers on the subject.
Best regards,

Adrian Carcu
Student - Master
Babes-Bolyai University
Cluj-Napoca, Romania

--- Stefan Haustein <> wrote:
> Thomas Baar wrote:
> > Sometimes, you don't need Dan Chiorean's TC-operator. This is the case when
> > the closure-relation does not have cycles. Then you can use a technique of
> > recursive definition as it is done in the UML metamodel to define the 
> > set allparents of all direct and indirect superclasses.
> If you allow the definition of recursive functions inside OCL -- which seems 
> required for your approach -- I do not see why the relation must not have 
> cycles: You could easily define an utility operation with an "exclude"
> parameter 
> for "visited" instances (or simply count down steps from allInstances() to
> 0)?
> Best regards,
> Stefan
> -- 
> Dipl.-Inform. Stefan Haustein
> Univ. Dortmund, FB 4, LS 8   tel: +49 231 755 2499
> Baroper Str. 301             fax: +49 231 755 5105
> D-44221 Dortmund (Germany)
> To remove yourself from this list please mail
> with a message containing the word "unsubscribe".

Do you Yahoo!?
Yahoo! SiteBuilder - Free web site building tool. Try it!

Date view Thread view Subject view Author view Attachment view