Tree structure

[Peter Otten]

Bevan Jenkins wrote:

> Hello,
> 
> I am trying to create a tree structure for use with a PyQt QTreeView.
> But first I need to get my head around how to create the tree
> structure.  I have a dictionary (for testing purposes) but I will
> later use a table via sqlalchemy.
> 
> The use case is hydrology, so I  would like to have a hydrologically
> connected river tree, in which you can browse upstream from the sea
> (making choices) or downstream from any named hydrological feature.
> Each key flows into its value pair. myrivers =
> {"river":"flows_into"}.  An example is below:
> 
> myrivers = {"little stream":"sea",
>     "mountain stream":"lake",
>     "lake":"big river",
>     "cold spring":"big river",
>     "big river":"sea"
>     "sea":""}
> 
> I would like the tree to look like (if the formatting works....). so
> you can browse downstream from each named river but also upstream from
> the sea picking which direction to go.
> 
> little stream
>     sea
> mountain stream
>     lake
>         big river
>             sea
> lake
>     big river
>         sea
> cold spring
>     big river
>         sea
> big river
>     sea
> sea
>     little stream
>     big river
>         lake
>             mountain stream
>         cold spring
> 
> <<this next part is probably not very clear>>
> So every key is a parent.  For all keys that have a value (not ""),
> the value is the child and is then used as a parent to get the next
> child until the sea and a value of "" is reached.  For the sea this is
> reversed, that you find all rivers that flow into the sea and then all
> rivers that flow into them.
> 
> 
> Any thoughts about how to acomplish this will be much appreciated,
> Bevan

If you turn the values into lists you can use the same function for both 
trees:

INDENT = " " * 4

def print_tree(lookup, node=None):
    def _tree(node, level):
        print "%s%s" % (INDENT * level, node)
        for node in lookup.get(node, ()):
            _tree(node, level+1)

    if node is None:
        for node in lookup:
            _tree(node, 0)
    else:
        _tree(node, 0)

def reversed_dict(tree):
    reversed_tree = {}
    for key, values in rivers.iteritems():
        for value in values:
            reversed_tree.setdefault(value, []).append(key)
    return reversed_tree

if __name__ == "__main__":
    rivers = {
        "little stream": "sea",
        "mountain stream": "lake",
        "lake": "big river",
        "cold spring": "big river",
        "big river": "sea",
        "see": ""}

    rivers = dict((k, [v]) for k, v in rivers.iteritems() if v)
    print_tree(rivers)
    print "---"
    print_tree(reversed_dict(rivers), "sea")