3
スタックベースのデータフロー言語でプログラムを表すDAGがあります。各ノードは関数または値を表します。エッジは入力と出力を表し、各ノードは0以上を持つことができます。DAGをテーブルとしてレンダリングするアルゴリズム
まず、ここでのコードは次のとおり
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>"""