Re: [X] Tree/Graph structure in many-to-many relationship, avoiding/detecting circularity

In article <a5vq60$3ns$1_at_news.hccnet.nl>, "OddesE" <OddesE_XYZ_at_hotmail.com> wrote:

> "Kendall" <kendallwillets_at_yahoooooo.com> wrote in message
> news:u7vjq5b5mqg189_at_news.supernews.com...

>> In article <a5nh7d$hj8$1_at_news.hccnet.nl>, "OddesE"
>> <OddesE_XYZ_at_hotmail.com> wrote:
>>
 

> Thank you very much Kendall.
> I have looked at the code but I dont really understand it. Could you
> tell me something more. What are transitive closures? English is not my
> native tongue, so excuse me if I ask something that I should know. What
> about the situation when circularity already exists? I tried this:
>

Sorry for the poor documentation :-).

You can do a web search on "transitive closure" and hopefully get some definitions. The TC is defined as:

1. Every edge (a,b) in the graph
2. If (a,b) and (b,c) are in the TC, then (a,c) is in the TC.

These two rules are followed in the code. The last statement applies (2) repeatedly until no more members are found. The resultant table can be queried to check for loops and other conditions.

The TC can contain a large number of rows, but in a tree the number of TC rows will be approximately the average depth times the node count. There is no problem with loops in the graph.

I just remembered another method that someone else used:

1. Copy the tree into a temp table
2. Delete the leaf nodes in the temp tree
3. Repeat 2 until no more nodes are deleted
4. Remaining nodes must be in 1 or more loops

This process removes the leaves (which cannot be in a loop, since they have no child nodes) and then parents of leaves, etc. When the process ends the nodes left over must be in loops, because they're the only ones who still have both child nodes and parent nodes. Received on Mon Mar 04 2002 - 10:30:34 CST