Re: Building a tree class with *multiple* parents
Date: Tue, 13 Feb 2001 23:37:32 -0600
Message-ID: <3A8A199C.B22D07_at_bga.com>
"A. Melon" wrote:
>
> Pretend I don't have access to the STL and have to roll my own
> tree class.
>
> I understand how to build a Node class with three pointers of class Node,
> Parent, LeftSibling and RightSibling. This works great for trees where
> nodes can have one and only one parent. But how can you modify a tree
> to allow one ** or more than one ** parent node?
>
> Think of a Bill-Of-Materials database. The factory builds many assemblies,
> some of which are top assemblies (these would be the root nodes) and the
> rest are subassemblies. Here's the tricky part - a subassembly can be used
> in more than one parent assembly. So these are the branches. Components
> are represented by nodes with no children - these are the leaves.
>
> I desire to have only one node per assembly - this rules out the
> assembly/next-higher-assembly concatenated-key method familiar to COBOLers.
>
> This is the pseudocode I've come up with so far:
>
> class Node {
> data
> data
> data
>
> NodeList Parents
> Node LeftSibling
> Node RightSibling
> }
>
> class NodeList {
> Node ItemStart
> Node ItemEnd
> }
>
> Any ideas on how to accomplish this? I would of course have to create
> functions to traverse, search and manipulate the nodes.
>
> Any help/ideas/suggestions would be greatly appreciated. Please post back
> to the list so that others may learn.
>
> TIA,
>
> Mark
Interesting.
First of all, you're not trying to build a tree at all! What
you're building is a directed graph (where all the edges are
duplicated to allow traversal in either direction).
There are two possible approaches that come to mind of the
top of my head.
One would be much like what you've proposed:
class Data {
...
...
<whatever>
}
class Node {
Data * data;
int in_degree;
Node ** in_edges; // i.e. your `Parent' pointers
// allocate in_degree of them
int out_degree;
Node ** out_edges; // i.e. your `Child' pointers
// allocate out_degree of them
}
In this case, any Node with in_degree == 0 would be a `top-level assembly' and any node with out_degree == 0 would be a component.
The other approach would be to couple an array (or vector) of Data objects (from above) with an adjacency matrix, i.e. an n x n two dimensional array (where n is the number of `things') where adj[n][m] == 1 means there's a child link from `thing' n to `thing' m.
Which approach is better (of these two; I'm sure someone will provide another take on this) depends upon the number of `things' and exactly how you plan to use them.
I hope this has been of some help.
[hint: do a web search on directed graph implementations]
HTH,
--ag
-- Artie Gold, Austin, TX (finger the cs.utexas.edu account for more info) mailto:agold_at_bga.com or mailto:agold_at_cs.utexas.edu -- A: Yes I would. But not enough to put it out.Received on Wed Feb 14 2001 - 06:37:32 CET