Re: transitive closure concept



Date view Thread view Subject view Author view Attachment view

From: Adrian Carcu (adi1302@yahoo.com)
Date: Sun 25 Jan 2004 - 02:45:06 GMT


Hello,

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)=
     Sequence{1..GeneralizableElement.allInstances->size}->iterate(it:Integer;
	  ac:Set(GeneralizableElement) = Set{self} |
          ac->union(ac.specialization.child->asSet))

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

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

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) |
    	     		ac->union(it.rclosure(ac)))   	    
    	  endif

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

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

--- Stefan Haustein <haustein@kimo.cs.uni-dortmund.de> 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)   www-ai.cs.uni-dortmund.de
> 
> 
> 
> 
> To remove yourself from this list please mail puml-list-request@cs.york.ac.uk
> with a message containing the word "unsubscribe".
> 


__________________________________
Do you Yahoo!?
Yahoo! SiteBuilder - Free web site building tool. Try it!
http://webhosting.yahoo.com/ps/sb/

Date view Thread view Subject view Author view Attachment view