将邻接表变为 table
Turn adjacency list into table
我在忙乱的项目中碰壁了。我在数据库中有一个邻接列表，其中有一系列嵌套类别。
它的格式是Id,Category,Parent_Id，效果很好。
我想将其显示为 table 以便人们可以添加和更改类别而不会造成太多混淆。这就是我失败的地方。我一辈子都想不出如何让它正确显示。
当我查询数据库时，我得到了一系列类似这样的嵌套元组：
((1L, 'First', None), (2L, 'Second', None), (3L, 'Third', None), (4L, 'Fourth', 1L), (5L, 'Fifth', 4L), (6L, 'Sixth', 3L), (7L, 'Seventh', 8L), (8L, 'Eighth', None))
数据稍有改动，因此无法保证顺序。我假设我需要某种递归函数来将它变成 table，但我无法理解它。像这样就好了：
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]]
从这里我有点迷路了。我假设将其变成 table，我需要与完成的 table 中的行一样多的列表。我可以在列表嵌套中找到最长的列表来给出行数，它在两个维度上工作以填充让我感到困惑的 table。
实际输出是一个非物。我可以毫不费力地以适合我的方式打印 table 。伤害我的是创造 table 的想法。我知道可以使用 SQL 查询，例如 Suggest SQL Query to retrieve all leaf nodes from Adjacency List Model，我只是希望 Python 中有一种方法可以做到这一点，这样我就可以了解更多有关处理此类数据的信息设置。
不太确定预期输出的格式，但这是一种方法：
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
下面是显示 table 和嵌套级别的解决方案。它使用 python 2.5.
支持的 prettytable
安装 table 渲染器：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)
我在忙乱的项目中碰壁了。我在数据库中有一个邻接列表，其中有一系列嵌套类别。
它的格式是Id,Category,Parent_Id，效果很好。
我想将其显示为 table 以便人们可以添加和更改类别而不会造成太多混淆。这就是我失败的地方。我一辈子都想不出如何让它正确显示。
当我查询数据库时，我得到了一系列类似这样的嵌套元组：
((1L, 'First', None), (2L, 'Second', None), (3L, 'Third', None), (4L, 'Fourth', 1L), (5L, 'Fifth', 4L), (6L, 'Sixth', 3L), (7L, 'Seventh', 8L), (8L, 'Eighth', None))
数据稍有改动，因此无法保证顺序。我假设我需要某种递归函数来将它变成 table，但我无法理解它。像这样就好了：
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]]
从这里我有点迷路了。我假设将其变成 table，我需要与完成的 table 中的行一样多的列表。我可以在列表嵌套中找到最长的列表来给出行数，它在两个维度上工作以填充让我感到困惑的 table。
实际输出是一个非物。我可以毫不费力地以适合我的方式打印 table 。伤害我的是创造 table 的想法。我知道可以使用 SQL 查询，例如 Suggest SQL Query to retrieve all leaf nodes from Adjacency List Model，我只是希望 Python 中有一种方法可以做到这一点，这样我就可以了解更多有关处理此类数据的信息设置。
不太确定预期输出的格式，但这是一种方法：
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
下面是显示 table 和嵌套级别的解决方案。它使用 python 2.5.
支持的 prettytable安装 table 渲染器：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)