Re: Need Algorithm or Data Structure for Organizing "Hierarchical" Data

Tech-Archive recommends: Repair Windows Errors & Optimize Windows Performance

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.


<jehugaleahsa@xxxxxxxxx> wrote in message
news:ff1fb00e-c295-4ec7-8d3d-213f3f86de85@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
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.


.

Relevant Pages

  • Re: More Efficient: Hashtable or List cont.....
    ... Ignacio Machin ... My app needs to potentially store a large number of custom objects and be ... Is using enumerators to iterate through the data structure a good idea? ...
    (microsoft.public.dotnet.languages.csharp)
  • Re: PEP 372 -- Adding an ordered directory to collections
    ... I think for this data structure it's important to keep all the ... My guess is that it includes it for performance reasons. ... making byindex() a method of odict, ... layer where one only has to iterate over the linked list offset times ...
    (comp.lang.python)
  • Iterating Over Dictionary From Arbitrary Location
    ... In my application I will be having several messages and my own type of IDs to go with these messages. ... Hence a dictionary seems a better choice than a list, as I will be using my own IDs to index into the data structure. ... even if it was possible to sort a dictionary, it is not possible to iterate over it from a given location. ... So, it seems I want the best of both worlds: specific indexing using my own IDs/keys (not just by list element location), sorting and the ability to start iterating from a specific location. ...
    (comp.lang.python)
  • Re: iterating through object structure
    ... I have a data structure as follows ): ... I can't seem to iterate through it, ... Can't say I can recreate it, ... Rik Wasmus ...
    (comp.lang.php)