How to nicely lay out a tree in the form of a table (using merged cells)

Background: I have some data that I want to present in a table. Each column in the table has a header. Some of these headers in turn, have common headers. In other words, I have a tree of headers that I want to show in the table cells.

Problem: How to nicely lay out a tree in the form of table by means of merging cells (cf merged cells in Excel or rowspan / colspan in HTML tables)?

Some requirements:

Given a tree like the following:

+ Header 1
|---+ Header 2
|   |---- Header 4
|   '---+ Header 5
|       |---- Header 8
|       '---- Header 9
'---+ Header 3
    |---- Header 6
    '---- Header 7

• The resulting table should always be rectangular, i.e. this is not acceptable:

  .-------------------------------------------.
  |                  Header 1                 |
  +--------------------------+----------------+
  |    Header 2              |    Header 3    |
  +----------+---------------+--------+-------+
  | Header 4 |   Header 5    |  Hdr 6 | Hdr 7 |
  '----------+-------+-------+--------+-------'
             | Hdr 8 | Hdr 9 |
             '-------+-------'
  

• The height of the cells should be as evenly distributed as possible. (There should be no unecessary height constraints between siblings.) For instance solving the above situation by simply letting the leaves grow downwards like this is not acceptable:

  .-------------------------------------------.
  |                  Header 1                 |
  +--------------------------+----------------+
  |    Header 2              |    Header 3    |
  +----------+---------------+--------+-------+  <-- Height of Header 3
  |          |   Header 5    |        |       |      constrained by
  | Header 4 +-------+-------+  Hdr 6 | Hdr 7 |      height of Header 2
  |          | Hdr 8 | Hdr 9 |        |       |
  '----------+-------+-------+--------+-------'
  

• The correct output should look something like this:

  .-------------------------------------------.
  |                  Header 1                 |
  +--------------------------+----------------+
  |    Header 2              |    Header 3    |
  +----------+---------------+                |
  | Header 4 |   Header 5    |--------+-------+  <-- constraint relaxed.
  |          +-------+-------+  Hdr 6 | Hdr 7 |
  |          | Hdr 8 | Hdr 9 |        |       |
  '----------+-------+-------+--------+-------'
  

• The number of rows used should be minimized. In other words, the right version is preferred over the left version below:

  .--------------------------.         .--------------------------.
  |  Rowspan 3               |         |  Rowspan 1               |
  +-------------+------------+         +-------------+------------+
  |  Rowspan 4  | Rowspan 6  |   -->   |  Rowspan 2  | Rowspan 3  |
  +-------------+            |         +-------------+            |
  |  Rowspan 6  +------------+         |  Rowspan 3  +------------+
  |             | Rowspan 4  |         |             | Rowspan 2  |
  '-------------+------------'         '-------------+------------'
  
  Unecessarily large rowspans.             Minimized rowspans.
    (actual height: 13 rows)             (actual height: 6 rows)
  

Answer

As usual, explaining the problem carefully seem to have helped. I believe I figured it out. The key idea is to traverse the tree recursively and (among a few other things) compute the least common multiple of the depths of all subtrees in each step.

The answer is written in Java but it should be trivial to rewrite into PHP, C# or what-have-you. It refers to the following two auxiliary classes and targets HTML-tables.

class Tree {
    String val;
    Tree[] children;
    ...
}

class Cell {
    String val;
    int row, col, rowspan, colspan;
    ...
}

The solution is broken up in two parts:

1. Conversion from Tree to List<Cell>.

2. Layout of List<Cell> to a proper <table>...</table>.

   (Presumably not required if targetting for instance a spread-sheet.)

Conversion from Tree to List<Cell>

This is done using the methods rowsToUse and getCells defined below. The former computes the total number of rows required to lay out a given tree, and the latter generates the actual Cells. The arguments denote the following:

• t is the root of the tree for which Cells should be generated.
• row and col denotes the current row and column of the top-most (root) cell.
• rowsLeft specifies how many rows the current tree should be distributed on.

Here are the two methods:

public static int rowsToUse(Tree t) {
    int childrenRows = t.children.length == 0 ? 0 : 1;
    for (Tree child : t.children)
        childrenRows = lcm(childrenRows, rowsToUse(child));
    return 1 + childrenRows;
}


public static List<Cell> getCells(Tree t, int row, int col, int rowsLeft) {

    // Add top-most cell corresponding to the root of the current tree.
    int rootRows = rowsLeft / rowsToUse(t);
    List<Cell> cells = new ArrayList<Cell>();
    cells.add(new Cell(t.val, row, col, rootRows, width(t)));

    // Generate cells for subtrees.
    for (Tree child : t.children) {
        cells.addAll(getCells(child, row+rootRows, col, rowsLeft-rootRows));
        col += width(child);
    }

    return cells;
}

The methods depth, width and lcm are straight forward. See full source at the bottom if you like.

Layout of List<Cell> to a proper <table>...</table>

public static String getHtmlTable(List<Cell> cells) {

    // Sort the cells primarily on row, secondarily on column.
    Collections.sort(cells, new Comparator<Cell>() {
        public int compare(Cell c1, Cell c2) {
            int pri = Integer.valueOf(c1.row).compareTo(c2.row);
            int sec = Integer.valueOf(c1.col).compareTo(c2.col);
            return pri != 0 ? pri : sec;
        }
    });

    // Lay out the cells row by row.
    StringBuilder result = new StringBuilder("<table><tbody>");
    for (int row = 0, i = 0; i < cells.size(); row++) {
        result.append("<tr>n");
        for (; i < cells.size() && cells.get(i).row == row; i++)
            result.append(cells.get(i).asTdTag());
        result.append("</tr>n");
    }
    return result.append("</tbody></table>").toString();
}

Full source and demo.

Here’s the full source. Given the tree

Tree t = new Tree("1",
           new Tree("2",
             new Tree("4"),
               new Tree("5",
                 new Tree("8"),
                 new Tree("9"))),
           new Tree("3",
             new Tree("6"),
             new Tree("7")));

it produces the following table body:

<tr><td colspan='5'>1</td></tr>
<tr><td colspan='3' rowspan='2'>2</td><td colspan='2' rowspan='3'>3</td></tr>
<tr></tr>
<tr><td rowspan='4'>4</td><td colspan='2' rowspan='2'>5</td></tr>
<tr><td rowspan='3'>6</td><td rowspan='3'>7</td></tr>
<tr><td rowspan='2'>8</td><td rowspan='2'>9</td></tr>

which looks like

Full source:

import java.io.*;
import java.util.*;

class Tree {

    String val;
    Tree[] children;

    public Tree(String val, Tree... children) {
        this.val = val;
        this.children = children;
    }
}


class Cell {
    String val;
    int row, col, rowspan, colspan;
    public Cell(String val, int row, int col, int rowspan, int colspan) {
        this.val = val;
        this.row = row;
        this.col = col;
        this.rowspan = rowspan;
        this.colspan = colspan;
    }

    public String asTdTag() {
        String cs = colspan == 1 ? "" : " colspan='" + colspan + "'";
        String rs = rowspan == 1 ? "" : " rowspan='" + rowspan + "'";
        return "<td" + cs + rs + ">" + val + "</td>";
    }
}


public class TreeTest {

    public static int rowsToUse(Tree t) {
        int childrenRows = t.children.length == 0 ? 0 : 1;
        for (Tree child : t.children)
            childrenRows = lcm(childrenRows, rowsToUse(child));
        return 1 + childrenRows;
    }


    public static List<Cell> getCells(Tree t, int row, int col, int rowsLeft) {

        // Add top-most cell corresponding to the root of the current tree.
        int rootRows = rowsLeft / rowsToUse(t);
        List<Cell> cells = new ArrayList<Cell>();
        cells.add(new Cell(t.val, row, col, rootRows, width(t)));

        // Generate cells for subtrees.
        for (Tree child : t.children) {
            cells.addAll(getCells(child, row+rootRows, col, rowsLeft-rootRows));
            col += width(child);
        }

        return cells;
    }


    public static int width(Tree t) {
        if (t.children.length == 0)
            return 1;
        int w = 0;
        for (Tree child : t.children)
            w += width(child);
        return w;
    }


    public static int lcm(int a, int b) {
        int c = a * b;
        while (b > 0) {
            int t = b;
            b = a % b;
            a = t;
        }
        return c / a;
    }


    public static String getHtmlTable(List<Cell> cells) {

        // Sort the cells primarily on row, secondarily on column.
        Collections.sort(cells, new Comparator<Cell>() {
            public int compare(Cell c1, Cell c2) {
                int pri = Integer.valueOf(c1.row).compareTo(c2.row);
                int sec = Integer.valueOf(c1.col).compareTo(c2.col);
                return pri != 0 ? pri : sec;
            }
        });

        // Lay out the cells row by row.
        StringBuilder result = new StringBuilder("<table><tbody>");
        for (int row = 0, i = 0; i < cells.size(); row++) {
            result.append("<tr>n");
            for (; i < cells.size() && cells.get(i).row == row; i++)
                result.append("  " + cells.get(i).asTdTag() + "n");
            result.append("</tr>n");
        }
        return result.append("</tbody></table>").toString();
    }


    public static void main(String[] args) throws IOException {

        Tree t = new Tree("1",
                new Tree("2",
                  new Tree("4"),
                    new Tree("5",
                      new Tree("8"),
                      new Tree("9"))),
                new Tree("3",
                  new Tree("6"),
                  new Tree("7")));

        FileWriter fw = new FileWriter("tree.html");

        List<Cell> cells = getCells(t, 0, 0, rowsToUse(t));

        fw.write("<html><head><style>table, td { border-style: solid; } " +
                 "table { border-spacing: 0px; border-width: 0 0 1px 5px; } " +
                 "td { padding: 15px; text-align: center; " +
                 "border-width: 1px 5px 0 0;} </style></head><body>");
        fw.write(getHtmlTable(cells));
        fw.write("</body></html>");

        fw.close();
    }
}