Doctrine2: Dependency graph for a set of entities
So, after digging through the Doctrine source code for a while, I found that they have indeed an implementation of topological sorting (DFS for that matter). It's implemented in Doctrine\ORM\Internal\CommitOrderCalculator.
And where is this CommitOrderCalculator used? In UnitOfWork, of course.
So, instead of manually calculating the correct commit order, I just needed … to move the call to $em->flush() outside the foreach loop that went through the entities and let UOW do the work itself.
Duh.