Print Page | Close Window

dependency based graph traversal -- a new feature

Printed From: MetaCase
Category:
Forum Name: MetaEdit+
Forum Description: All topics relating to MetaEdit+ or DSM
URL: https://www.metacase.com/forums/forum_posts.asp?TID=856
Printed Date: 27.Mar.2026 at 03:35
Software Version: Web Wiz Forums 12.05 - http://www.webwizforums.com


Topic: dependency based graph traversal -- a new feature
Posted By: grossd18
Subject: dependency based graph traversal -- a new feature
Date Posted: 12.Oct.2016 at 23:15
Hi, 

In the modelling language that i am implementing one object can refer to one or more other objects via property collection. One outcome of this ability is that when generating the model I have to ensure that no "forward references" are generated -- i am not generating code over objects in a property collection for which no prior generated definitions exists. 

i think the usual way to handle this is to build a kind of dependency graph (or stack) to ensure that code generation always generates non-dependent objects first. 

It would be great if a foreach or do loop could be structured so that it automatically takes into account inter-object references and traverses the graph accordingly, so that the MERL programmer doesnt need to deal with that anymore. 

hope my description is understandable ..

thanks,

Daniel





Replies:
Posted By: stevek
Date Posted: 12.Oct.2016 at 23:44
Funny, I kind of http://www.metacase.com/forums/topic855_post2144.html#2144" rel="nofollow - guessed you were facing this problem :). Do you have any freedom in the modeling language, or is it already existing and must be implemented as-is? Having unrestricted references like that makes life hard for modelers too - everything can rely on anything else, and it's easy to build cycles or spaghetti then. 

With an Object that has a References property, which contains a collection of Objects, there's no way for a single loop to iterate over everything in the right order. (Not a MERL issue, just a fact of that kind of structure.) Instead, you generally proceed by recursion: process this object, recurse to each element in :References that you haven't met before. E.g. the code below will print each Object exactly once, listing its References, and recursing throughout the whole transitively reachable collection of Objects, without duplication or going into an infinite loop on cycles:
_handleObject()
if __Unique() then
   id newline /* write the definition of this object itself */
   do :References { ' - ' id newline }
   do :References { _handleObject() }
endif

You can start it off with a simple "foreach .Object { _handleObject() }". Where the references to the next objects are by relationships not properties, you can tell MERL to start at the top of the tree (or forest): "foreach .Object; where not ~To { _handleObject() }". 

I can't see a way out of needing to tell MERL a) where to start from, b) how to navigate on from there, and c) how to avoid duplicates/cycles. They're different each time, so you need your own line of code for them. The good news is that it really is just one line of code for each - the rest above is for the output.



Print Page | Close Window

Forum Software by Web Wiz Forums® version 12.05 - http://www.webwizforums.com
Copyright ©2001-2022 Web Wiz Ltd. - https://www.webwiz.net