CODEWITHSUNDEEP
pythondata-structureshierarchy
miltonjbradley
miltonjbradley

Reputation: 601

iterating through hierarchical structures in Python

I have a set of numbered groups in a data set that are organized hierarchically. Each group has a numbered title and has several members of that group. For example:

01 : Tony, John, Meredith
01.01 : Alex, Fred, Melissa
02 : Alley, Henry, Natalie
02.01.02 : Chris, Pete
03 : Andrew
03.01 : Nancy, Peter, Harold

What data structure should I use in python to organize these groups? I need to maintain the hierarchy so that 01.01 is a child of 0.1. The structure of the data goes up to 7 levels deep such as: 01.03.01.01.02.04.05, this group is a child of the group 01.03.01.01.02.04, and so on. Any help is much appreciated. I am not sure what data structure to create so I can iterate over it. Thanks.

Upvotes: 0

Views: 1243

Answers (2)

Rory Daulton
Rory Daulton

Reputation: 22534

You ask "What data structure should I use in python to organize these groups?"

A key principle of top-down programming is that you do not decide the implementation of an abstract data structure until you have decided the operations that will be done on the structure as well as their relative frequencies and any other criteria (such as simplicity and memory usage). You have not stated that information, so we cannot recommend a particular implementation.

I can think of many ways to do what you ask: a tree, lists within lists, dictionaries within dictionaries, etc. Each has its advantages and disadvantages. I do wonder about one point. In your structure, every item at a new sub-level begins with '01', with the exception of '02.01.02 : Chris, Pete' which begins with '02'. Is that intentional? If you keep the otherwise apparent numbering, that opens up some simpler implementations.

With the added information in your comment, I recommend nested lists. Each data item has a sequence of indices that ends in zero, and anything else in the structure is a list that holds other data items and lists. In your example, if we let the entire structure be named a, then item 01 is a[1][0], item 01.01 is in a[1][1][0], item 02.01.02 is in a[2][1][2][0], and so on. This structure allows more items to be inserted later, so we can easily add item 01.01.01 without disturbing the other items. There is no need to store the item numbers in the structure: they are directly inferred from the position of the data items in the structure.

This implementation also allows the entire structure to have a data item, which has an empty item number and is stored in a[0]. A missing data item can be flagged by None, a blank item can be another empty item such as ''. Here is code that shows your example structure and code that prints it out.

def print_structure(structure, level=''):
    """Iterate through a heirarchical data structure, printing the data
       items with their level numbers"""
    for i, item in enumerate(structure):
        if i == 0:
            # Process each data item appropriately
            if item is not None:
                print(level + ' : ' + str(item))
        else:
            new_level = format(i, '02')
            if level:
                new_level = level + '.' + new_level
            print_structure(item, new_level)


a = [None,
     ['Tony, John, Meredith',
      ['Alex, Fred, Melissa']],
     ['Alley, Henry, Natalie',
      [None,
       ['?'],
       ['Chris, Pete']]],
     ['Andrew',
      ['Nancy, Peter, Harold']]]

print_structure(a)

In this implementation, each of your "groups" is a string. I put the group '?' where you said a group exists but did not state just what it is, and I put None where you did not say a data item exists. To modify the processing of the structure, just change the two lines after the comment Process each data item appropriately. The printout from the above code is

01 : Tony, John, Meredith
01.01 : Alex, Fred, Melissa
02 : Alley, Henry, Natalie
02.01.01 : ?
02.01.02 : Chris, Pete
03 : Andrew
03.01 : Nancy, Peter, Harold

Saving to and restoring from JSON is easy. This should meet your needs, though there are some modifications that could be made to either structure or code, of course.

Upvotes: 1

alexis
alexis

Reputation: 50180

If your main goal is to produce a JSON-friendly structure you can write out, use nested dictionaries (or OrderedDict if the order of elements is important). It keeps things simple, and writing it out with json will be trivial. Each dictionary can have a key members (a list or set of the children directly assigned to it), and a key subgroups that is a list or dict of the sub-dictionaries. It's not hard to create since the titles of the parent groups are prefixes of the subgroups.

Upvotes: 0

Related Questions