Need Algorithm or Data Structure for Organizing "Hierarchical" Data

[jehugaleahsa]

Hello:

I have a bunch of related items that are either parents, children or
not directly related to each other. In my case, I have a bunch of
database tables joined with foreign keys. Another example would be a
family tree.

I would like to take a flat list of these items and build the
hierarchy. So, in other words, I would like to take one element and
figure out its relationship to the other items. When I am all done, I
should have a somewhat complex structure.

I want to allow situations such as: I am my own grandpa; I have
multiple children; I have multiple parents; I'm completely unrelated
to this guy.

If the resulting structure can't be iterated over, I am willing to
eliminate the "I am my own grandpa" situation. It's not necessary,
just nice.

I would want all orphaned items to be at the top level. All the
children of these elements can be at the next level. And so on . . .

I would like to require the algorithm or data structure to take a
Comparison<T> delegate to determine rank between two items.

I would like to provide iterators that do breadth-first, depth-first,
etc. However, so long as parent and child relationships are many-to-
many, I don't think iteration is feasible. Grouping is always an
option.

My throught was to take a new item and pass it to the comparison
delegate for each existing item in the data structure. I would keep a
list of parents and a list of children. I would then create a child
"node" under the parents. I would create a child "node" under the new
node foreach child.

However, unless I chop off requirements, I feel like this is a very
complex problem. I was wondering if anyone knew of an algorithm or
data structure that did something similar. I would rather not reinvent
the wheel.

 

[jehugaleahsa]

What you need is a graph.  You can iterate over it with either a depth-first
or breadth-first search.

I wrote some classes to do this.  You can download the documentation (as a
PDF) for free, as well as the source code.http://www.lulu.com/content/1995848

You can find other implementations/ideas by searching the net.

I was actually able to avoid the graph data structure by making it
illegal for nodes to be their own ancestors. The algorithm I came up
with is still insanely slow for large data sets: O(n2 + n*lg(n) + 2n).
I am not sure how to build such a structure without each node looking
at each other at least once.

Thanks for your help,
Travis