CODEWITHSUNDEEP
pythonalgorithm
kb4shubham
kb4shubham

Reputation: 331

Which algorithm to use to populate the data in tree structure

I have this table in my database and I want to populate the data on a wabpage.

parent_topic    child_topic
      4             5
      4             6
      4             7
      5             8
      5             9
      5             11
      5             11
      5             13
      12            14
      13            15
      8             16
      8             17
      8             18
      16            19
      9             20
      20            21
      9             22
      9             23
      6             24
      25            25
      24            26
      6             27
      24            25
      25            21

I am working on python. What algorithm should I use in order to populate this table. The format is like following...

and so on... (Child topics are according to the table).
I was trying to use nested dictionary, but I was unable to create such dictionary.

Thanks in advance.

Upvotes: 2

Views: 757

Answers (3)

Leonardo.Z
Leonardo.Z

Reputation: 9791

I would strongly recommend you to read this blog Storing Hierarchical Data in a Database.

The blog gives a detailed introduction to two major approaches used in industry on how to store hierarchical data in a relational database: the adjacency list model, and the modified preorder tree traversal algorithm.

The adjacency list model approach is the one your database used. You iterate the tree by recursion from the top node. In many cases, people don't want to or can't load all the data into memory, so the iteration on each node will triage a new SQL query. That's the biggest disadvantage of the adjacency list approach.

django-treebeard is a library that implements efficient tree implementations based on Adjacency List for the Django framework. Thought you may not use django, you can still learn a lot from django.

The modified preorder tree traversal algorithm approach is more efficient when the number of reads to the tree is larger than changes to the tree (Usually this is true for web sites) so it is more popular than the the adjacency list approach.

There is also a excellent implementation of the modified preorder tree traversal algorithm for django : django-mptt

Upvotes: 3

Don
Don

Reputation: 17606

A recursive approach...

list_pc = [
    (4,5),
    (4,6),
    (4,7),
    (5,8),
    (5,9),
    (5,11),
    (5,11),
    (5,13),
    (12,14),
    (13,15),
    (8,16),
    (8,17),
    (8,18),
    (16,19),
    (9,20),
    (20,21),
    (9,22),
    (9,23),
    (6,24),
    (24,25),
    (24,26),
    (6,27),
    (24,25),
    (25,21),
]

dict_pc = {}
parents = set()
children = set()
for p, c in list_pc:
    parents.add(p)
    children.add(c)
    dict_pc.setdefault(p, []).append(c)

roots = sorted(list(parents - children))
def print_tree(level, p):
    global dict_pc
    print '.'*level, p
    for c in dict_pc.get(p, []):
        print_tree(level + 1, c)

for r in roots:
    print_tree(0, r)

output:

 4
. 5
.. 8
... 16
.... 19
... 17
... 18
.. 9
... 20
.... 21
... 22
... 23
.. 11
.. 11
.. 13
... 15
. 6
.. 24
... 25
.... 21
... 26
... 25
.... 21
.. 27
. 7
 12
. 14

Upvotes: 0

sbeliakov
sbeliakov

Reputation: 2179

Sorry for my Pseudo-Python :)

Assuming you have list topics of objects with method get_lines() that returns lines of topic:

def PrintTopic(topic, margin):
    for line in topics[topic].get_lines():
        print "   " * margin + line


def PrintRecursiveTopic(db, currentTopic, depth):
    PrintTopic(currentTopic, depth)
    for topic in db.topics.where(lambda x: x.parent_topic == currentTopic):
        PrintRecursiveTopic(db, topic.child_topic, depth + 1)

depth is for PrintTopic to print with margin

Upvotes: 0

Related Questions