Tree structure

Discussion in 'Python' started by Bevan Jenkins, Jul 26, 2011.

  1. 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
    Bevan Jenkins, Jul 26, 2011
    #1
    1. Advertising

  2. Bevan Jenkins

    Marco Nawijn Guest

    On Jul 26, 6:53 am, 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


    Hello Bevan,

    Is it an option to use XML as an in-memory representation. It
    naturally provides the
    interface you need, like traversing from parent to children and back.
    In addition, you
    get querying capabilities like XPATH for free. In python I recommend
    lxml.

    Your task than is to fill the tree based on the information in the
    database. The ORM functionality
    from sqlalchemy will be of help here. In addition, you somehow have to
    populate the QT tree with the
    data from your in-memory XML representation. I have no experience with
    QT so I cannot help you there.

    Regards,

    Marco
    Marco Nawijn, Jul 26, 2011
    #2
    1. Advertising

  3. Bevan Jenkins

    Peter Otten Guest

    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")
    Peter Otten, Jul 26, 2011
    #3
  4. On Jul 26, 8:46 pm, Peter Otten <> wrote:
    > 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.
    >> SNIP<<
    > > 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")- Hide quoted text -
    >
    > - Show quoted text -


    Peter,
    Thank you that does what I need! Now I just need to incorporate into
    PyQt but that shouldn't be too hard...

    Macro,
    I need to look into lxml in the coming months, so I might revisit this
    then.
    Bevan Jenkins, Jul 27, 2011
    #4
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Stub

    B tree, B+ tree and B* tree

    Stub, Nov 12, 2003, in forum: C Programming
    Replies:
    3
    Views:
    10,089
  2. sharan
    Replies:
    4
    Views:
    674
    CBFalconer
    Oct 30, 2007
  3. sharan
    Replies:
    2
    Views:
    819
    SM Ryan
    Oct 31, 2007
  4. sharan
    Replies:
    1
    Views:
    677
    CBFalconer
    Oct 30, 2007
  5. anne001
    Replies:
    1
    Views:
    227
Loading...

Share This Page