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

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)?

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.
• If you have the values $\pi(v_i)$ as defined in my answer then you shouldn't need any BFS visit nor to scan the adjacency list of $v_i$. A valid vertex following $v_i$ in a longest path is $\pi(v_i)$. Aug 17, 2021 at 15:41