Algorithm for rendering DAG as table

Question

I have a DAG representing a program in a stack-based dataflow language. Each node represents a function or value. Edges represent inputs and outputs, of which each node may have 0 or more.

First, here’s the code:

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

The algorithm takes a graph like this:

1   2   3   4
 \ /     \ /
  +       +
   \     /
    \   /
     \ /
      *
      |
    print

Represented as a post-order traversal, where each element is a tuple (name, indegree, outdegree):

[
  ("1", 0, 1),
  ("2", 0, 1),
  ("+", 2, 1),
  ("3", 0, 1),
  ("4", 0, 1),
  ("+", 2, 1),
  ("*", 2, 1),
  ("print", 1, 0),
]

And renders it as a table.

+---+---+---+---+
| 1 | 2 | 3 | 4 |
+---+---+---+---+
|   +   |   +   |
+-------+-------+
|       *       |
+---------------+
|     print     |
+---------------+

That is, independent nodes are arranged horizontally, and dependencies are indicated by vertical arrangement. If a function doesn’t have enough inputs, it produces empty cells.

o   +---+
    | 2 |
+---+---+
|   *   |
+-------+

The algorithm proceeds by adding a new empty row for each cell and padding the table on the right, deleting cells on the right or adding them on the left to “sink” the node until its inputs are satisfied.

+---+
| 1 |
+---+

+---+   o
| 1 |
+---+---+
    | 2 |
o   +---+

+---+           o
| 1 |
+---+---+
    | 2 |
    +---+-------+
        |   +   |
o       +-------+

+---+       o
| 1 |
+---+---+
    | 2 |
    +---+---+
    |   +   |
o   +-------+

+---+   o
| 1 |
+---+---+
    | 2 |
+---+---+
|   +   |
+-------+

The final pass (omitted from the code above) is to merge occupied cells with empty cells vertically.

+---+---+
| 1 | 2 |
+---+---+
|   +   |
+-------+

The problem is that this doesn’t account for changing column widths while sinking a new cell into a row.

+---+---+---+       o
| 1 | 2 | 3 |
+---+---+---+
    |   +   |
    +-------+-------+
            |   +   |
o           +-------+

+---+---+---+   o
| 1 | 2 | 3 |
+---+---+---+
    |   +   |
    +---+---+---+
        |   +   |
o       +-------+


Wrong output:
+---+---+---+
| 1 | 2 | 3 |
+---+---+---+
    |   +   |
    +-------+
    |   +   |
o   +-------+

Desired output:
+---+---+---+
|   | 2 | 3 |
| 1 +---+---+
|   |   +   |
+---+-------+
|     +     |
+-----------+

How should I track this information in the algorithm? With a list of column widths for the preceding row? Furthermore, is there a more efficient way to do this? The current algorithm makes a pass over the whole table for each input of each node.

Finally, here’s the test case:

def render(table):
    print ""
    for row in table:
        print ""
        for name, width in row:
            if name is None:
                print "" % width
            else:
                print "" % (width, name)
        print ""
    print "  %s"

print """
Test

"""
render(to_table([
    ("1", 0, 1),
    ("2", 0, 1),
    ("3", 0, 1),
    ("+", 2, 1),
    ("+", 2, 1),
]))
print """"""

Gribouillis · Accepted Answer

In the resulting table, there is a cell per graph node, it means that the table can be described by adequately decorating the graph. The main additional attributes we want is a rowspan and a colspan for each node.

The easiest attribute is the colspan, it's simply the sum of the subnodes' colspans, or 1 if there is no subnode.

The rowspan can be obtained as the difference gheight(parent) - gheight(node) where gheight(node) is 1 + the max of the gheight of its subnodes, or 0 if there is no subnode.

In a single traversal of the input data you can compute the 'colspan' and 'gheight' attributes of the nodes. In your example, they are [(1, 0), (1, 0), (1, 0), (2, 1), (3, 2)]

With very little more work, you can compute the rowspan in the same loop. Here is my implementation

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)

The output is

['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]

Each node has been decorated with rowspan, colspan and gheight attributes.

Algorithm for rendering DAG as table

Answers (1)

Related Questions