News for hackers. Stuff that matters.
Re:Dependency by tunesmith on Monday August 17, 2020 @09:35PM (#24194416)
Hrm. Can any DAG be drawn as a box diagram?
Re:Dependency by andreareina on Monday August 17, 2020 @09:51PM (#24194493)
If a box diagram has to be a planar graph, then no:

    digraph G {
        a -> {x y z}
        b -> {x y z}
        c -> {x y z}
    }
cannot be drawn on the plane without any crossings.

https://en.wikipedia.org/wiki/Three_utilities_problem

Re:Dependency by Tomminn on Monday August 17, 2020 @11:38PM (#24195012)
Isn't two "utilities" enough here?

Suppose we have two components-- X and Y-- which depend on two other lower-level components-- A and B. How would you draw this as a block dependency diagram without repetition?

If both X and Y depend on B, then X and Y must be above B, and both touch B. If X and Y are orthogonal rectangles, then the entire X-Y edge is obscured from below. This means that another lower-level component A must can only interact with either X or Y. You'd need to allow X or Y to no longer be orthogonal rectangles to overcome this, or need to give up on the vertical organization of dependencies.

Re:Dependency by lopsidedBrain on Tuesday August 18, 2020 @02:29AM (#24195846)
Hmm. You're right, not if we are restricting ourselves to rectangles. But if we make A u-shaped, with B nestled in it, we'll be in business!
Re:Dependency by hoseja on Tuesday August 18, 2020 @02:51AM (#24195916)
Hey there was a phys article about that problem today!

https://phys.org/news/2020-08-solution-math-riddle.html

Re:Dependency by hardmath123 on Monday August 17, 2020 @10:02PM (#24194544)
This is a great question! I don’t actually know the precise condition for box-diagram-ability of a DAG, but I’ve spent a long time thinking about it; it’s partly why I wrote that program. It’s not a deterministic algorithm, it’s powered by a SAT solver which may return “UNSAT” indicating failure. If anyone has a better answer I would be _very_ interested in reading about it!
Re:Dependency by tunesmith on Monday August 17, 2020 @09:53PM (#24194508)
I guess the answer is no... assuming 1 is on the bottom:

1->2; 1->4; 2->3; 3->4

Unless 4 is slanted.

Re:Dependency by Jtsummers on Monday August 17, 2020 @09:42PM (#24194457)
The key part is performing a topological sort, which you can do on any DAG.