Re^2: Visualizing a dependency graph in a web page

Thanks, just after writing it occurred to me that it's of course not just a tree.

But I also need it to be ranked by phases, that's where the time-axis comes in.

the jobs without dependency run in phase 0
the jobs depending on phase 0 run in phase 1
and so on

This "rank" requirement (or was it "grade") already includes acyclic, otherwise this wouldn't be possible. I think this is an even narrower requirement than just DAG.

Anyway talking about it helped me sketching my own algorithm already... :)

I searched DAG with graphviz, but couldn't see them ranked in phases and the nodes were all circles (I have practically no hands-on experience with graph-viz)

> automate creating images of them without edges having to cross each other, etc.

Really? I have doubts it's always possible to draw a planar graph.

consider a 3d-cube, how do you want to draw a planar graph without crossings - here x ?

    0
  / | \
 /  |  \
A   B   C
|\ / \ /|
| x   x |
|/ \ / \|
a   b   c
 \  |  /
  \ | /
    1
[download]

Cheers Rolf
_{(addicted to the Perl Programming Language :)

Wikisyntax for the Monastery}

Comment on Re^2: Visualizing a dependency graph in a web page Select or Download Code

Replies are listed 'Best First'.
Re^3: Visualizing a dependency graph in a web page by kennethk (Abbot) on Apr 01, 2022 at 21:09 UTC
> automate creating images of them without edges having to cross each other, etc. Really? I have doubts it's always possible to draw a planar graph. consider a 3d-cube, how do you want to draw a planar graph without crossings - here x ? There are two basic cases where the graphs cannot be embedded in a 2-d representation without crossing lines: 3 nodes that are each fully connected w/ 3 other nodes `a -> A, B, C b -> A, B, C c -> A, B, C` [download] 5 densely connected nodes `A -> B, C, D, E B -> C, D, E C -> D, E D -> E` [download] All graphs that can't be embedded in a 2-d plane have those cases embedded in them. Your cube example actually can be embedded. You just lose the pretty perspective (or gain a new one...). `0 / \| \ / \| \ / B \ / / \ \ A---a c---C \ \ / / \ 1 / \ \| / \ \| / b` [download] This is proven by Kuratowski's theorem and is discussed here. #11929 First ask yourself `How would I do this without a computer?' Then have the computer do it the same way.	[reply] [d/l] [select]
Re^4: Visualizing a dependency graph in a web page by LanX (Saint) on Apr 01, 2022 at 21:46 UTC
Yes, you are right. I remember discussing K₅ and K_3,3 in university > Your cube example actually can be embedded. You just lose the pretty perspective (or gain a new one...). And this a good example why a good question often matters more than a good answer. In the context of this task I need the diagram to have a top-down semantic with Y being the time-axis. So 0 and 1 must be at different extremes, so flattening won't be possible with Q₃ ° Cheers Rolf _{(addicted to the Perl Programming Language :) Wikisyntax for the Monastery} °) FWIW I remember the notation B₃, but all these pandemics in the meantime must have messed with my head :)	[reply]
Re^5: Visualizing a dependency graph in a web page by kennethk (Abbot) on Apr 01, 2022 at 23:43 UTC
Yup, we should be talking about upward planar drawings. Looking forward to finding out your final strategy for getting it onto a screen. #11929 First ask yourself `How would I do this without a computer?' Then have the computer do it the same way.	[reply]
Re^6: Visualizing a dependency graph in a web page by LanX (Saint) on Apr 02, 2022 at 09:49 UTC
Re^7: Visualizing a dependency graph in a web page by karlgoethebier (Abbot) on Apr 02, 2022 at 10:15 UTC
Re^3: Visualizing a dependency graph in a web page by hv (Prior) on Apr 01, 2022 at 14:57 UTC
> > automate creating images of them without edges having to cross each other, etc. > Really? I have doubts it's always possible to draw a planar graph. You're quite right, that was a brainfart.	[reply]