"Tracy Pierce" <[log in to unmask]> wrote in message
news:a0ds2k01al9@enews2.newsguy.com...
> I have a set of activities which sometimes include other activities; this
is
> recursive, the result resembles a tree structure, similar to a directory
> tree.  Until now I've quite simply disallowed 'multiple parents', but
> largely because my brain's too feeble to see a cleaner loop-avoidance
> mechanism.
>
> (Clear as mud?  Here I have A includes B & D, B includes C, E includes F,
> all just lovely.  This works nicely even in a physical sense, and looks
like
> a tree.)
>
> ActA
>  |-ActB
>  |-ActC
>     |-ActD
> ActE
>  |-ActF
>
> Now I need to add ActF to ActC, basically meaning I want to allow leaf F
> appear on multiple trees.  This is ok, but the procedure of adding ActF to
> ActC must include enough exhaustive checking to ensure that I disallow
> creation of loops, such as that which would occur if I were to add ActA to
> ActC.
>
> Can anyone here on good old HP3000-L point me in the direction of the
> perfect solution?  (I just KNOW there are papers out there, so even a good
> Google key would be a great pointer!)

Simple answer:

On every addition of a link, walk the tree below the item you are linking,
looking for the leaf you are linking to.
If you don't find it, all is OK. If you do find it, this is a loop; refuse
the link.

(I'm assuming that 'walk the tree' isn't problematic with your structure;
you need a depth-first walk, such that if, say, the above also had an ActG
linked below ActB (just to make the following sequence clear), and you tried
to link A to C, your codes would look at ActA's structure in the sequence
A-B, B-G, A-C, C-D, C-F. Though of course, you'd stop on encountering A-C,
as C is the leaf in question....

Complex answer (when walking the tree every time could get real
s-l-o-o-o-w):

This is a classic manufacturing structure situation, and can be addressed
using LLCs (Lowest Level Codes). Please excuse me if I talk about parents
and components, rather than node and leaf....

And your diagram isn't how these things are normally drawn 'across' the
page - imagine these were folders in Windows Explorer[1], in which case
they'd look like:

ActA
    | - Act B
        | - Act C
    |- ActD

ActE
    | - ActF

Then the depths (indents) are the levels. ActA and ActE, having no parents,
are at level 0. For Act B, the level must be incremented, so this appears at
level 1.
ActC is at level 2; ActD is at level 1, like ActB.

And so on, so ActF is at level 1.

When ActF is then added to ActC, which is at level 2, its level must be at
least 3. So you need to do a Lowest Level push-down, which involves
increasing the LLC of ActF and all its components so that ActF is at level
3, and its lower level components all lower than that.

As ActF has no lower level components, you can make its LLC 3 without any
problem. Note that this still works for ActE; as long as ActF has a larger
LLC than ActE, this is OK. It doesn't need to be exactly one lower, but it
must be at least one lower.

Now imagine adding ActA to ActC. As you walked the tree, Act A would now
become level 3, B and D would be level 4, and ActC would be level 5 - but
hang on, ActC is where we came in....

So we would have detected the loop, on the basis of re-encountering the
parent we are linking to, and would refuse the linkage; this is the easy
case. For very deep trees, the loop might be enormous, so we would also set
a limit on LLC (say 99), and we would stop if this limit was breached, even
if we hadn't yet looped back to ActC.

So the LLC pushdown has two steps; a trial push-down to see if it works, and
then a real updating of the LLCs.

The pushdown can be optimised, so that it stops exploring the tree not just
at every component with no structure, but also at every component which is
already at a 'low enough' level. For instance, if you linked ActE to ActA
(having already linked ActF to ActC, so ActF is at level 3), then ActE would
go to level 1, and ActF would need to be level 2 or lower. But since it is
already level 3, this is low enough already, and we don't even need to look
and see if it has components.

But this is the 'industrial strength' answer; Hopefully the simple one will
suffice for you.

[1] I give Windows Explorer only as an example. The crucial difference
(though it doesn't affect how the tree is shown) is that the ActF being
linked to ActC is the *same* ActF as the one below ActE; in Explorer, it
would just be a different folder with the same name.

--
Roy Brown

* To join/leave the list, search archives, change list settings, *
* etc., please visit http://raven.utc.edu/archives/hp3000-l.html *