From: Shashank Date <ADATE@...>
Date: 2002-09-17T02:51:41+09:00
Subject: Re: Dependency "trees" - suggestions?


> This is not really a tree because many packages can depend on one, so
> a node can have multiple parents.  But it *is* directed and *must* be
> acyclic.

So this is a DAG "Directed Acyclic Graph" for which there many algorithms
available.

> In other words, whenever a node is added, it must be checked that it
hasn't produced a cycle.
>
> The million dollar question: how?

I am sure there is one for this too. You may want to search for DAG
construction algorithms in Google.
HTH,

-- shanko