Topological sort and finding longest path in DAG to solve a stacking boxes variation (no rotation)

Question

Given n elements (boxes) I have to output the max number of boxes that can fit one into another. Each box has width (x), height (y) and depth (z). One box j can hold another box k if: j.x > k.x and j.y > k.y and j.z > k.z. Rotation is not allowed.

Searching some approaches on the net, I found this can be a way:

organize boxes in a directed unweighted graph where the edge (j,k) means j holds k
use topological sort on the grapgh
find the longest path and print it

I'm trying to better understand what will happen after doing the topological sort on the graph. If I understand correctly, I should be able to perform topological sort with a DFS-visit variation. In an example I've seen, the output of the sort is a single linked list. So if i output the list, why this is not already the longest path (meaning the longest sequence of boxes that can fit one into another)? If that's not the case and I also need to find the longest path, do I need to do it on the new graph made by the edges in the list returned by the topological sort (meaning it'll be a directed acyclic graph)?

Answer 1

The topological order is not guaranteed to be a solution. Indeed the topological order clearly has length $n$ while there are instances in which it is not possible to stack all boxes. As an example consider $n=2$ boxes that do not fit into one another (e.g., with sizes $(1,1,2)$ and $(1,2,1)$).

You need to find the longest path in the original graph. You can do that by computing the longest path from each vertex $v$. In order to do so let $G=(V,E)$ be the graph (notice that $G$ is acyclic!), let $\sigma = \langle v_1, v_2, \dots, v_n \rangle$ be a topological order of $G$, and define $d(v_i)$ as the length of the longest path starting from $v_i$ in $G$. When the out-degree of $v_i$ is $0$ we have $d(v_i)=0$. Otherwise we have: $$ d(v_i) = 1 + \max_{(v_i,v_j) \in E} d(v_j). $$ Notice that, by the definition of topological order, $v_j$ must follow $v_i$ in $\sigma$. This means that we can compute all values $d(v_i)$ using a dynamic programming algorithm that examines the vertices of $G$ in reverse topological order. To find a longest path (rather than just the path's length), and hence the sequences of boxes to stack, you can store for each $v_i$ a value $\pi(v_i) \in \arg \max_{(v_i,v_j) \in E} d(v_j)$. Then, if $v^*$ maximizes $d(v^*)$, the sought path is: $$ \underbrace{ v^*, \pi(v^*), \pi(\pi(v^*)), \pi(\pi(\pi(v^*))), \dots}_{d(v^*)+1\mbox{ times}} $$

The whole algorithm can also be formulated in terms of boxes, doing away with the graph $G$. The main observation is that if box $b_1$ stacks into box $b_2$ then the volume of $b_1$ must be smaller than the volume of $b_2$. As a consequence, it suffices to consider boxes in non-decreasing order of volume.