convert flat structure into hierarchical one

Discussion in 'Python' started by Ksenia Marasanova, Sep 26, 2004.

  1. I get this kind of list from a database. (The tuple structure is: id,
    name, parent_id)

    [(1, 'grandparent', None), (2, 'parent', 1), (3, 'otherparent', 1), (4,
    'child', 3)]

    I would like to transfer it (in Python) into a tree structure. I don't
    care much about format, as long as I'll be able to get all the
    information, based on one id. For example, if I have id=3, I want to
    get
    - name ('otherparent')
    - children (one child, with id=4, name='child')
    - parent id

    Any tips? Recipes? ;-)


    Thanks,
    Ksenia.
     
    Ksenia Marasanova, Sep 26, 2004
    #1
    1. Advertising

  2. Ksenia Marasanova

    Dan Perl Guest

    I started writing a script that would implement a solution to your problem,
    but it turned out that it is not so trivial. You have all kind of issues,
    depending on whether your structure is sparse or not, and what especially
    made me give up (I may still try it later, but right now I don't have the
    time) is that you may retrieve a child before its parent, so either you
    create a dummy that you update later, or you recursively retrieve all the
    ancestors in the tree up to the root of the tree.

    Here is my suggestion in brief, though. Implement a class for the tree and
    a class for the tree nodes. The 'tree' class keeps a list of instances of
    the 'tree node' class. Depending on the sparsity of the tree, you can have
    a list indexed by the id's of the nodes (with None for empty spaces), or an
    arbitrary list and you do the search for the node in the list that has the
    particular id.

    The 'tree node' class would have 4 attributes: id, name, parent_id, and
    children. 'children' would be a list. BTW, this attribute is not
    mandatory, but it is more efficient having it if it is rarely updated but
    often accessed.

    The 'tree' class would also have a method 'addNode'. In it, create a new
    instance of the 'tree node class', add it to the list in the tree and update
    the node matching the parent_id. Here is where the complication come in.
    You may have to pad the list with 'None' and you may not yet have a node
    matching the parent in the 'tree' list. Override the __getitem__ method in
    the 'tree' class to retrieve the node based on its id.

    Hope this helps.

    Dan

    "Ksenia Marasanova" <> wrote in message
    news:...
    >I get this kind of list from a database. (The tuple structure is: id, name,
    >parent_id)
    >
    > [(1, 'grandparent', None), (2, 'parent', 1), (3, 'otherparent', 1), (4,
    > 'child', 3)]
    >
    > I would like to transfer it (in Python) into a tree structure. I don't
    > care much about format, as long as I'll be able to get all the
    > information, based on one id. For example, if I have id=3, I want to get
    > - name ('otherparent')
    > - children (one child, with id=4, name='child')
    > - parent id
    >
    > Any tips? Recipes? ;-)
    >
    >
    > Thanks,
    > Ksenia.
    >
     
    Dan Perl, Sep 26, 2004
    #2
    1. Advertising

  3. On Sun, 26 Sep 2004 19:49:41 +0200, Ksenia Marasanova <>
    declaimed the following in comp.lang.python:

    > I get this kind of list from a database. (The tuple structure is: id,
    > name, parent_id)
    >
    > [(1, 'grandparent', None), (2, 'parent', 1), (3, 'otherparent', 1), (4,
    > 'child', 3)]


    Note that your data has "parent" and "otherparent" both linked
    to the one "grandparent"... I hope this isn't supposed to represent a
    genealogical structure... <G> (The latter should have two "parent-ID"
    pointers per tuple: "father" and "mother".)

    >
    > I would like to transfer it (in Python) into a tree structure. I don't
    > care much about format, as long as I'll be able to get all the
    > information, based on one id. For example, if I have id=3, I want to
    > get
    > - name ('otherparent')
    > - children (one child, with id=4, name='child')
    > - parent id
    >


    If you truly want it as a tree in Python memory, you'll have to
    traverse the tree in other to find any particular node -- especially if
    the number of children per node is variable (meaning you can't reserve
    ID#s for them -- Genealogical /ancestor/ reporting schemes using
    ahnentafel numbering can be computed; for node-n, father is node-n*2,
    mother is node-n*2 + 1).

    For general usage I'd forget using a literal tree. Stuff the
    data in a dictionary using the ID# as the key, and the related data
    being the name, parent ID#, list of child ID#s

    {3:("otherparent", 1, [4])}

    --
    > ============================================================== <
    > | Wulfraed Dennis Lee Bieber KD6MOG <
    > | Bestiaria Support Staff <
    > ============================================================== <
    > Home Page: <http://www.dm.net/~wulfraed/> <
    > Overflow Page: <http://wlfraed.home.netcom.com/> <
     
    Dennis Lee Bieber, Sep 27, 2004
    #3
  4. Thanks to all for helpfull suggestions!
    I think I'll use the tree class as Dan suggested, but instead of
    creating the list of node instances in advance, will do it on demand.
    I'll use the function of Mike in the constructor of the tree, and will
    use the resulting data for internal tree searching and node generation.
    I think it's much faster then creating all the node instances from the
    beginning, and I actually seldom need a whole three, only parts of it.

    And no, it's not a genealogical structure :).. I used words as 'parent'
    and 'child' just to explain the tree structure better. It's for a
    website, where all navigation parts are stored in one tree. Until now,
    I had a recursive SQL function in PostgreSQL, but with the growing of
    the tree (hey, it's alive! ;-) the function is getting slower, so I
    want to move it to Python.

    Ksenia.
     
    Ksenia Marasanova, Sep 27, 2004
    #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. Paddy McCarthy
    Replies:
    3
    Views:
    715
    Anthony J Bybell
    Sep 24, 2004
  2. Michael Schuerig

    WSDL for hierarchical structure?

    Michael Schuerig, Nov 9, 2004, in forum: XML
    Replies:
    0
    Views:
    468
    Michael Schuerig
    Nov 9, 2004
  3. Steve Mac
    Replies:
    3
    Views:
    448
    Joris Gillis
    Dec 31, 2004
  4. Alfonso Morra
    Replies:
    5
    Views:
    398
    Michael Wojcik
    Oct 4, 2005
  5. Alfonso Morra
    Replies:
    0
    Views:
    385
    Alfonso Morra
    Oct 3, 2005
Loading...

Share This Page