我有一个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>"""