python - 将邻接表变成表

Question

我在忙乱的项目中碰壁了。我在数据库中有一个邻接列表，其中有一系列嵌套类别。它的格式为 Id,Cat​​egory,Parent_Id 并且效果很好。

我想将其显示为表格，以便人们可以添加和更改类别而不会造成太多混淆。这就是我失败的地方。我一辈子都想不出如何让它正确显示。

当我查询数据库时，我最终得到了一系列与此类似的嵌套元组:

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

数据稍有变化，因此无法保证顺序。我假设我需要某种递归函数来将它变成一个表，但我就是无法理解它。就像这样就好了:

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

任何人都可以给我一些关于如何实现这一目标的指示吗？几乎不可能将外部模块安装到我正在处理的盒子上，而且它只运行 python 2.5，因此非常感谢任何帮助。

编辑:在发布之前我想出了以下代码:

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

从中我得到了每个级别的嵌套列表:

>>> levels

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

从这里我有点迷路了。我想把它变成一个表格，我需要尽可能多的列表，因为完成的表格中会有行。我可以在列表嵌套中找到最长的列表来给出行数，它在两个维度上工作以填充让我感到困惑的表格。

实际输出不是东西。我可以毫不费力地以适合我的方式打印表格。创建表格的想法伤害了我。我知道可以使用 SQL 查询，例如 Suggest SQL Query to retrieve all leaf nodes from Adjacency List Model ，我只是希望有一种方法可以在 Python 中执行此操作，这样我就可以了解更多有关处理此类数据集的信息。

Answer 1

不太确定预期输出的格式，但这里有一种方法:

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)

输出:

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

下面是一个显示表格和嵌套级别的解决方案。它使用 python 2.5 支持的 prettytable。

安装表格渲染器: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

结果:

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

注意:如果你的数据是多层嵌套的，那么一些修改也可以实现。目前它只考虑 0 或 1 级嵌套。

下面使用递归函数处理多层嵌套:

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

输出:

+----------+-------+
| 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   |
+----------+-------+

更多关于递归函数的信息，如果您有兴趣:https://en.wikipedia.org/wiki/Recursion_(computer_science)