我有一个 DAG，代表一个基于堆栈的数据流语言的程序。每个节点代表一个函数或值。边表示输入和输出，其中每个节点可能有 0 个或多个边。
首先，这是代码:
def to_table(nodes):
table = []
table_width = 0
empty = (None, 1)
for name, indegree, outdegree in nodes:
cell_width = max(indegree, outdegree)
# Create a row of empty cells, the width of the table.
current_row = [empty] * table_width
# Right-pad preceding rows.
for row in table:
row.extend([empty] * cell_width)
table_width += cell_width
for n in range(indegree):
# If we've run out of inputs, left-pad preceding rows.
if len(current_row) == 0:
current_row.append(empty)
for row in table:
row = [empty] + row
table_width += 1
# Drop one empty cell.
current_row.pop()
for row in table:
row.pop();
table_width -= 1
current_row.append((name, cell_width))
table.append(current_row)
return table
该算法采用如下图:
1 2 3 4
\ / \ /
+ +
\ /
\ /
\ /
*
|
print
表示为后序遍历，其中每个元素都是一个元组(名称、入度、出度):
[
("1", 0, 1),
("2", 0, 1),
("+", 2, 1),
("3", 0, 1),
("4", 0, 1),
("+", 2, 1),
("*", 2, 1),
("print", 1, 0),
]
并将其呈现为表格。
+---+---+---+---+
| 1 | 2 | 3 | 4 |
+---+---+---+---+
| + | + |
+-------+-------+
| * |
+---------------+
| print |
+---------------+
即独立节点横向排列，依赖关系用纵向排列表示。如果函数没有足够的输入，它会生成空单元格。
o +---+
| 2 |
+---+---+
| * |
+-------+
该算法通过为每个单元格添加一个新的空行并在右侧填充表格、删除右侧的单元格或在左侧添加它们来“下沉”节点，直到其输入得到满足。
+---+
| 1 |
+---+
+---+ o
| 1 |
+---+---+
| 2 |
o +---+
+---+ o
| 1 |
+---+---+
| 2 |
+---+-------+
| + |
o +-------+
+---+ o
| 1 |
+---+---+
| 2 |
+---+---+
| + |
o +-------+
+---+ o
| 1 |
+---+---+
| 2 |
+---+---+
| + |
+-------+
最后一步(从上面的代码中省略)是将占用的单元格与空单元格垂直合并。
+---+---+
| 1 | 2 |
+---+---+
| + |
+-------+
问题在于，这并没有考虑到在将新单元格放入一行时更改列宽。
+---+---+---+ o
| 1 | 2 | 3 |
+---+---+---+
| + |
+-------+-------+
| + |
o +-------+
+---+---+---+ o
| 1 | 2 | 3 |
+---+---+---+
| + |
+---+---+---+
| + |
o +-------+
Wrong output:
+---+---+---+
| 1 | 2 | 3 |
+---+---+---+
| + |
+-------+
| + |
o +-------+
Desired output:
+---+---+---+
| | 2 | 3 |
| 1 +---+---+
| | + |
+---+-------+
| + |
+-----------+
我应该如何在算法中跟踪这些信息？有前一行的列宽列表？此外，有没有更有效的方法来做到这一点？当前算法为每个节点的每个输入遍历整个表。
最后，这是测试用例:
def render(table):
print "<table>"
for row in table:
print "<tr>"
for name, width in row:
if name is None:
print "<td class='empty' colspan='%d'> </td>" % width
else:
print "<td colspan='%d'>%s</td>" % (width, name)
print "</tr>"
print "</table>"
print """<!DOCTYPE html>
<html><head><title>Test</title>
<style>
td { border: 1px solid black }
td.empty { border: 1px dashed grey }
</style>
</head><body>"""
render(to_table([
("1", 0, 1),
("2", 0, 1),
("3", 0, 1),
("+", 2, 1),
("+", 2, 1),
]))
print """</body></html>"""
最佳答案
在结果表中，每个图节点有一个单元格，这意味着 可以通过充分装饰图形来描述表格。主要的 我们想要的附加属性是每个节点的行跨度和列跨度。
最简单的属性是colspan，它只是
子节点的 colspans，如果没有子节点则为 1。
rowspan 可以作为差值gheight(parent) - gheight(node)
其中 gheight(node) 是 1 + 其子节点 gheight 的最大值，或者 0
如果没有子节点。
在输入数据的单次遍历中，您可以计算“colspan”和“gheight”
节点的属性。在您的示例中，它们是
[(1, 0), (1, 0), (1, 0), (2, 1), (3, 2)]
只需做很少的工作，您就可以在同一个循环中计算行跨度。 这是我的实现
NAME, INDEGREE, OUTDEGREE, ROWSPAN, COLSPAN, GHEIGHT = range(6)
def decorate_graph(nodes):
deco = []
stk = []
for name, indegree, outdegree in nodes:
node = [name, indegree, outdegree, 0, 1, 0]
deco.append(node)
if indegree:
subn = stk[-indegree:]
del stk[-indegree:]
node[COLSPAN] = sum(sn[COLSPAN] for sn in subn)
node[GHEIGHT] = 1 + max(sn[GHEIGHT] for sn in subn)
for sn in subn:
sn[ROWSPAN] = node[GHEIGHT] - sn[GHEIGHT]
stk.append(node)
g = 1 + max(n[GHEIGHT] for n in stk)
for n in stk:
n[ROWSPAN] = g - n[GHEIGHT]
return deco
if __name__ == '__main__':
g = [
("1", 0, 1),
("2", 0, 1),
("3", 0, 1),
("+", 2, 1),
("+", 2, 1),
]
d = decorate_graph(g)
for item in d:
print(item)
输出是
['1', 0, 1, 2, 1, 0]
['2', 0, 1, 1, 1, 0]
['3', 0, 1, 1, 1, 0]
['+', 2, 1, 1, 2, 1]
['+', 2, 1, 1, 3, 2]
每个节点都装饰有 rowspan、colspan 和 gheight 属性。
关于python - 将 DAG 渲染为表格的算法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/41096830/