Turn adjacency list into table

Question

I've hit a brick wall in a project I'm messing around with. I've got an adjacency list in a database where I've got a series of nested categories. It's in the format of Id,Category,Parent_Id and works quite well.

I'd like to display it as a table so that people can add and alter categories without too much confusion. This is where I'm failing. I can't for the life of me work out how to get it displaying correctly.

When I query the database, I end up with a series of nested tuples similar to this:

((1L, 'First', None), (2L, 'Second', None), (3L, 'Third', None), (4L, 'Fourth', 1L), (5L, 'Fifth', 4L), (6L, 'Sixth', 3L), (7L, 'Seventh', 8L), (8L, 'Eighth', None))

The data gets changed a bit, so there's no guarantee of order. I assume I need some sort of recursive function to turn it into a table, but I just can't get my head around it. Just something like this would be nice:

First | Fourth | Fifth 
Second
Third | Sixth
Eighth | Seventh

Can anyone give me some pointers on how to achieve this? It's almost impossible to get outside modules onto the box I'm working on and it's only running python 2.5, so any help would be greatly appreciated.

edit: Before posting I'd come up with the following code:

list = ((1L, 'First', None), (3L, 'Third', None), (4L, 'Fourth', 1L),
        (6L, 'Sixth', 3L), (7L, 'Seventh', 8L), (8L, 'Eighth', None), 
        (2L, 'Second', None), (5L, 'Fifth', 4L))

levels = []
levels.append([_[0] for _ in list if _[2] is None])
for x in xrange(0,len(list[0])):
   levels.append([])
   for item in list:
       levels[-1].append(item[0]) if item[2] in levels[-2] else None
   if sum([len(_) for _ in levels]) == len(list): break

From that I get nested lists for each level:

>>> levels

[[1L, 3L, 8L, 2L], [4L, 6L, 7L], [5L]]

From here I get a little lost. I assume to turn this into a table, I need as many lists as there will be rows in the finished table. I can find the longest list in the nest of lists to give the amount of rows, it's working in two dimensions to fill the table out that's had me stumped.

The actual output is a non-thing. I can print the table in a way that suits me without much effort. It's the thinking to create the table that's hurting me. I know it's possible to do with SQL queries such as in Suggest SQL Query to retrieve all leaf nodes from Adjacency List Model, I was just hoping there was a way to do it in Python so I could learn more about handling this sort of data set.

Answer 1

Not quite sure about the format of the expected output however here is an approach:

data = ((1L, 'First', None), (3L, 'Third', None), (4L, 'Fourth', 1L),
        (6L, 'Sixth', 3L), (7L, 'Seventh', 8L), (8L, 'Eighth', None), (2L, 'Second', None), (5L, 'Fifth', 4L))


def get_tuple_by_id(tuple_id):
    for item in data:
        if item[0] == tuple_id:
            return item


def arrange_data(items):
    new_list = ()

    for an_item in items:
        parent_id = an_item[2]
        if parent_id:
            parent = get_tuple_by_id(parent_id)
            new_tuple = an_item + (parent[1],)
            new_list += (new_tuple,)
        else:
            new_list += (an_item,)

    return sorted(new_list, key=lambda x: x[0])


def render(items):
    print '{name:15}{parent}'.format(name='name', parent='parent')
    print '{name:15}{parent}'.format(name='--------', parent='-------')
    for item in items:
        print '{name:15}{parent}'.format(name=item[1], parent=item[3] if item[2] else '')

ad = arrange_data(data)
render(ad)

Output:

name           parent
--------       -------
First          
Second         
Third          
Fourth         First
Fifth          Fourth
Sixth          Third
Seventh        Eighth
Eighth         

Below is an a solution for showing table and nesting level. It uses prettytable which is supported by python 2.5.

Install table renderer: pip install prettytable

from prettytable import PrettyTable


data = ((1L, 'First', None), (3L, 'Third', None), (4L, 'Fourth', 1L),
        (6L, 'Sixth', 3L), (7L, 'Seventh', 8L), (8L, 'Eighth', None), (2L, 'Second', None), (5L, 'Fifth', 4L))


def get_tuple_by_id(tuple_id):
    for item in data:
        if item[0] == tuple_id:
            return item


def arrange_data(items):
    new_list = ()

    for an_item in items:
        parent_id = an_item[2]
        if parent_id:
            parent = get_tuple_by_id(parent_id)
            new_tuple = an_item + (parent[1],)
            new_list += (new_tuple,)
        else:
            new_list += (an_item,)

    return sorted(new_list, key=lambda x: x[0])


ad = arrange_data(data)
t = PrettyTable(['Category', 'Level'])

for item in ad:
    t.add_row([item[1], 1 if item[2] else 0])

print t

Result:

+----------+-------+
| Category | Level |
+----------+-------+
|  First   |   0   |
|  Second  |   0   |
|  Third   |   0   |
|  Fourth  |   1   |
|  Fifth   |   1   |
|  Sixth   |   1   |
| Seventh  |   1   |
|  Eighth  |   0   |
+----------+-------+

Note: If you data in be nested multiple level then some modification can also achieve that. At the moment it's only considering 0 or 1 level nesting only.

The following handles multilevel nesting by using recursive function:

from prettytable import PrettyTable


data = (
    (1L, 'First', None), 
    (2L, 'Second', None), 
    (3L, 'Third', None), 
    (4L, 'Fourth', 1L),
    (5L, 'Fifth', 4L),
    (6L, 'Sixth', 3L), 
    (7L, 'Seventh', 8L), 
    (8L, 'Eighth', None), 
    (9L, 'Ninth', 5L),
    (10L, 'Tenth', 9L),
    (11L, 'Eleventh', 10L),
    (12L, 'Twelfth', 11L))


def get_tuple_by_id(tuple_id, level=1):
    for item in data:
        if item[0] == tuple_id:
            parent_id = item[2]
            if parent_id:
                level += 1
                return get_tuple_by_id(parent_id, level)
            else:
                return (item, level)


def arrange_data(items):
    new_list = ()

    for an_item in items:
        parent_id = an_item[2]
        if parent_id:
            parent, level = get_tuple_by_id(parent_id)
            print an_item, level

            new_tuple = an_item + (level,)
            new_list += (new_tuple,)
        else:
            an_item += (0,)
            new_list += (an_item,)

    return sorted(new_list, key=lambda x: x[0])


ad = arrange_data(data)
t = PrettyTable(['Category', 'Level'])

for item in ad:
    t.add_row([item[1], item[3]])

print t

Output:

+----------+-------+
| Category | Level |
+----------+-------+
|  First   |   0   |
|  Second  |   0   |
|  Third   |   0   |
|  Fourth  |   1   |
|  Fifth   |   2   |
|  Sixth   |   1   |
| Seventh  |   1   |
|  Eighth  |   0   |
|  Ninth   |   3   |
|  Tenth   |   4   |
| Eleventh |   5   |
| Twelfth  |   6   |
+----------+-------+

More about recursive function in case you are interested: https://en.wikipedia.org/wiki/Recursion_(computer_science)