Python: tree structure and numerical codes?

Question

I'm using Python and I have some data that I want to put into a tree format and assign codes to. Here's some example data:

Africa    North Africa    Algeria
Africa    North Africa    Morocco
Africa    West Africa     Ghana
Africa    West Africa     Sierra Leone

What would be an appropriate tree structure for this data?

Also, is there a way that I can then retrieve numerical codes from this tree structure, so that I could query the data and get codes like the following example?

def get_code(place_name):
    # Python magic query to my tree structure
    return code
get_code("Africa") # returns 1
get_code("North Africa") # returns 1.1
get_code("Morocco") # returns 1.1.2

Thank you for your help - I still have much to learn about Python :)

Answer 1

I would recommend, assuming you can count on there being no duplication among the names, something like:

class Node(object):
    byname = {}

    def __init__(self, name, parent=None):
        self.name = name
        self.parent = parent
        self.children = []
        self.byname[name] = self
        if parent is None:  # root pseudo-node
            self.code = 0
        else:  # all normal nodes
            self.parent.children.append(self)
            self.code = len(self.parent.children)

    def get_codes(self, codelist):
        if self.code:
            codelist.append(str(self.code))
            self.parent.get_codes(codelist)

root = Node('')

def get_code(nodename):
    node = Node.byname.get(nodename)
    if node is None: return ''
    codes = []
    node.get_codes(codes)
    codes.reverse()
    return '.'.join(codes)

Do you also want to see the Python code for how to add a node given a hierarchical sequence of names, such as ['Africa', 'North Africa', 'Morocco']? I hope it would be pretty clear given the above structure, so you might want to do it yourself as an exercise, but of course do ask if you'd rather see a solution instead;-).

Getting the hierarchical sequence of names from a text line (string) depends on what the separators are -- in your example it looks like it's just a bunch of spaces added for purely aesthetic reasons connected with lining up the columns (if that's the case I'd recommend a simple re based approach to split on sequence of two+ spaces), but if it's actually (e.g.) tab characters as the separators, the csv module from Python's standard library would serve you better. I just can't tell from the short example you posted in your Q!-)

Edit: the OP says they can get the sequence of names just fine but would like to see the code to add the relevant nodes from those -- so, here goes!-)

def addnodes(names):
    parent = root
    for name in names:
        newnode = Node.byname.get(name)
        if newnode is None:
            newnode = Node(name, parent)
        parent = newnode

See why it's important that node names are unique, to make the above class work? Since Node.byname is a single per-class dict, it can record only one "corresponding node" for each given name -- thus, a name that's duplicated in two or more places in the hierarchy would "clash" and only one of the two or more nodes would be properly recorded.

But then again, the function get_code which the OP says is the main reason for this whole apparatus couldn't work as desired if a name could be ambiguous, since the OP's specs mandate it returning only one string. So, some geographical list like

America   United States    Georgia
Europe    Eastern Europe   Georgia

(where two completely unrelated areas just happen to be both named 'Georgia' -- just the kind of thing that unfortunately often happens in real-world geography, as the above example shows!-) would destroy the whole scheme (depending on how the specs for get_code happen to be altered to deal with an ambiguous-name argument, of course, the class structure could surely be altered accordingly and accomodate the new, drastically different specs!).

The nice thing about encapsulating these design decisions in a class (albeit in this case with a couple of accompanying functions -- they could be elegantly be made into class methods, of course, but the OP's specs rigidly demand that get_code be a function, so I decided that, in that case addnodes might as well also be one!-) is that the specific design decisions are mostly hidden from the rest of the code and thus can easily be altered (as long as specs never change, of course -- that's why it's so crucial to spend time and attention defining one's API specs, much more than on any other part of design and coding!-) to refactor the internal behavior (e.g. for optimization, ease of debugging/testing, and so on) while maintaining API-specified semantics intact, and thus leaving all other parts of the application pristine (not even needing re-testing, actually, as long of course as the parts that implement the API are very thoroughly unit-tested -- not hard to do, since they're nicely isolated and stand-alone!-).

Answer 2

An ad-hoc POD ("plain old data") class representing a tree would do fine, something like:

class Location(object):
  def __init__(self, data, parent)
    self.data = data
    self.parent = parent
    self.children = []

Now assign/read the data attribute, or add/remove children, perhaps with helper methods:

def add_child(self, child):
  self.children.append(child)

Now, to actually divide your data into tree levels, a simple algorithm would be look at all the places with a common level-data (such as Africa) and assign them a location, then recursively for next level of data.

So, for Africa you create a location with data = Africa. Then, it will have a Location child for North Africa, West Africa and so on.

For "get the code" have a dictionary mapping each country to its location node, and use the parent links in the nodes. Traverse from the node to the top (until parent is None) at each level assigning the part of the code to be the index in the children list of the parent.