tree erstellen...

Installation und Anwendung von Datenbankschnittstellen wie SQLite, PostgreSQL, MySQL, der DB-API 2.0 und sonstigen Datenbanksystemen.
Antworten
Benutzeravatar
jens
Moderator
Beiträge: 8482
Registriert: Dienstag 10. August 2004, 09:40
Wohnort: duisburg
Kontaktdaten:

Freitag 2. März 2007, 11:59

Also ich breche mir gerade einen ab :(

Ich schaffe es nicht eine Baum zu erstellen. Hab folgende Daten:

Code: Alles auswählen

data = [
    {'shortcut': 'Index',               'id': 1L,   'parent': 0L},
    {'shortcut': 'Elementary',          'id': 13L,  'parent': 10L},
    {'shortcut': 'OldDefault',          'id': 12L,  'parent': 10L},
    {'shortcut': 'SourceCode',          'id': 7L,   'parent': 2L},
    {'shortcut': 'RSS',                 'id': 6L,   'parent': 2L},
    {'shortcut': 'SmallWhite',          'id': 14L,  'parent': 10L},
    {'shortcut': 'SmallDark',           'id': 11L,  'parent': 10L},
    {'shortcut': 'Designs',             'id': 10L,  'parent': 0L},
    {'shortcut': 'TinyTextileExample',  'id': 3L,   'parent': 2L},
    {'shortcut': 'ExamplePages',        'id': 2L,   'parent': 0L},
    {'shortcut': 'Contact',             'id': 5L,   'parent': 2L},
    {'shortcut': 'SiteMap',             'id': 4L,   'parent': 2L},
    {'shortcut': '3.Ebene',             'id': 15L,  'parent': 3L},
]
Das soll daraus werden:

Code: Alles auswählen

sitemap = [
    {'parent': 0L, 'id': 1L, 'shortcut': 'Index'},
    {
        'parent': 0L, 'id': 10L, 'shortcut': 'Designs',
        'subitems': [
            {'parent': 10L, 'id': 13L, 'shortcut': 'Elementary'},
            {'parent': 10L, 'id': 12L, 'shortcut': 'OldDefault'},
            {'parent': 10L, 'id': 14L, 'shortcut': 'SmallWhite'},
            {'parent': 10L, 'id': 11L, 'shortcut': 'SmallDark'}
        ]
    },
    {
        'parent': 0L, 'id': 2L, 'shortcut': 'ExamplePages',
        'subitems': [
            {'parent': 2L, 'id': 7L, 'shortcut': 'SourceCode'},
            {'parent': 2L, 'id': 6L, 'shortcut': 'RSS'},
            {
                'parent': 2L, 'id': 3L, 'shortcut': 'TinyTextileExample',
                'subitems': [
                    {'parent': 3L, 'id': 15L, 'shortcut': '3.Ebene'},
                ]
            },
            {'parent': 2L, 'id': 5L, 'shortcut': 'Contact'},
            {'parent': 2L, 'id': 4L, 'shortcut': 'SiteMap'}
        ]
    }
]
Schön wäre auch, wenn ein "deep/Level" info eingefügt wird.

Jemand eine Idee, wie man das macht? Ist IMHO eine Allgemeine Fragestellung. Geht wohl irgendwie rekursiv.

Was ähnliches hatten wir hier: http://www.python-forum.de/topic-7501.html Hilft mir aber gerade nicht so weiter...

EDIT: Ha, ich hab was: [EDIT2: Alte Version gelöscht]
Zuletzt geändert von jens am Freitag 2. März 2007, 12:36, insgesamt 1-mal geändert.

CMS in Python: http://www.pylucid.org
GitHub | Open HUB | Xing | Linked in
Bitcoins to: 1JEgSQepxGjdprNedC9tXQWLpS424AL8cd
Benutzeravatar
jens
Moderator
Beiträge: 8482
Registriert: Dienstag 10. August 2004, 09:40
Wohnort: duisburg
Kontaktdaten:

Freitag 2. März 2007, 12:36

So, eine neue Version. Nun hab ich auch meine Level Angabe drin:

Code: Alles auswählen

from pprint import pprint

data = [
    {'id': 1,   'parent': 0,  'name': '1. Entry'},
    {'id': 2,   'parent': 1,  'name': '1.1. first subitem'},
    {'id': 3,   'parent': 1,  'name': '1.2. second subitem'},
    {'id': 4,   'parent': 2,  'name': '1.2.1 first sub-subitem'},
    {'id': 5,   'parent': 2,  'name': '1.2.2 second sub-subitem'},
    {'id': 6,   'parent': 0,  'name': '2. Entry'},
    {'id': 7,   'parent': 6,  'name': '2.1. first subitem'},
]


class TreeGenerator(object):
    def __init__(self, start_level=1):
        self.start_level = start_level

    def insert_level(self, data, level):
        """
        insert in every row a 'level'-key
        """
        for row in data:
            row["level"] = level
        return data

    def make_dict(self, data, key_name):
        """
        generate a dict based on key_name
        """
        result = {}
        for row in data:
            key = row[key_name]
            if not key in result:
                result[key] = [row]
            else:
                result[key].append(row)

        return result

    def generate(self, data):
        """
        returns the tree data
        """
        parent_dict = self.make_dict(data, "parent")

        root_id = min(parent_dict.keys())
        print "root id:", root_id

        root = parent_dict.pop(root_id)
        root = self.insert_level(root, self.start_level)

        tree = self.gen(root, parent_dict, level=self.start_level+1)
        return tree


    def gen(self, block, data, level):
        """
        generate recurive the tree data
        """
        for row in block:
            id = row["id"]
            if id in data:
                subitems = data.pop(id)
                subitems = self.insert_level(subitems, level)
                row["subitems"] = self.gen(subitems, data, level+1)

        return block


tree = TreeGenerator().generate(data)
print "="*80
pprint(tree)
Wie kann man es besser machen???

Was ich eigentlich auch noch brauche: slicing!
Also: gib mir alle Eintrage ab dem Level-X oder bis zum Level-Y...

Ausgabe ist dann:

Code: Alles auswählen

[{'id': 1,
  'level': 1,
  'name': '1. Entry',
  'parent': 0,
  'subitems': [{'id': 2,
                'level': 2,
                'name': '1.1. first subitem',
                'parent': 1,
                'subitems': [{'id': 4,
                              'level': 3,
                              'name': '1.2.1 first sub-subitem',
                              'parent': 2},
                             {'id': 5,
                              'level': 3,
                              'name': '1.2.2 second sub-subitem',
                              'parent': 2}]},
               {'id': 3,
                'level': 2,
                'name': '1.2. second subitem',
                'parent': 1}]},
 {'id': 6,
  'level': 1,
  'name': '2. Entry',
  'parent': 0,
  'subitems': [{'id': 7,
                'level': 2,
                'name': '2.1. first subitem',
                'parent': 6}]}]

CMS in Python: http://www.pylucid.org
GitHub | Open HUB | Xing | Linked in
Bitcoins to: 1JEgSQepxGjdprNedC9tXQWLpS424AL8cd
rayo
User
Beiträge: 773
Registriert: Mittwoch 5. November 2003, 18:06
Wohnort: Schweiz
Kontaktdaten:

Freitag 2. März 2007, 12:58

Hi

Also einen Baum von einem gewissen Level bekommst du mit Levelorder-Traversierung, z.B. so:

Code: Alles auswählen

def get_sub_tree(tree ,level):
    result = []
    q = Queue()
    for x in tree:
        q.put(x)

    while not q.empty():
        item = q.get()
        if item['level'] == level:
            result.append(item)
        else:
            if item.has_key('subitems'):
                for x in item['subitems']:
                    q.put(x)
    return result
Und bis Level x würde ich den Baum so lassen und einfach bei der bearbeitung beim Level x abbrechen.

Gruss
keboo
User
Beiträge: 132
Registriert: Sonntag 19. Februar 2006, 14:03

Mittwoch 28. März 2007, 13:54

Hallo Leute!

Ich bin im moment verzeweifelt dabei eine Produktbaum aus einer postgres DB rauszuholen.

Ich habe dabei eine Junction Table in welcher immer zu einer ID die darunterliegende ID angegeben ist.

Wie kann man den Code von Jens anpassen, damit zu einer ID nicht die ParentID sondern, die ChildrenID angeben werden kann in data?

Danke für eure Hilfe,

Johannes
Antworten