Visualizing a dependency graph in a web page

LanX has asked for the wisdom of the Perl Monks concerning the following question:

I have the requirement to visualize the state of night jobs with complex dependencies in a web page (think of make jobs running only if other jobs finnished)

The idea is to have as a basic a tree graph (simple case as ascii graphic, y is the time axis)


      .-------.   .-------.   .-------.    
      | job 1 |   | job 2 |   | job 7 |      
      |       |   |       |   |       |     
      .-------.   .-------.   .-------.  
          .         .   .         .      
          ...........   ...........    
                .           . 
                .           . 
.-------.   .-------.   .-------.   
| job 3 |   | job 4 |   | job 5 |     
|       |   |       |   |       |    
.-------.   .-------.   .-------.
    .           .           .
    .........................
                .
                .
            .-------.   
            | job 6 |   
            |       |   
            .-------.
[download]

Now the drawing logic for various dependency trees is challenging, we want to have at least a reasonable default, which can be adjusted manually.

I thought about using something like graphviz to draw the graph and to use Perl to translate the topology to HTML/JS.

In order to search for existing solutions, I need to figure out how these kind of diagrams are called.

I searched for various combinations of (dependency,job,task,scheduler) x (diagram,tree,graph,chart) but the images never fit.

Any pointers?

update

added "job 7" to make the complexity more apparent.

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

Wikisyntax for the Monastery}

Comment on Visualizing a dependency graph in a web page Select or Download Code

Replies are listed 'Best First'.
Re: Visualizing a dependency graph in a web page by hv (Prior) on Apr 01, 2022 at 13:13 UTC
What you have is a "directed acyclic graph" (DAG), ie a graph (in the mathematical sense) in which the edges connecting nodes are one-way ("directed"), and such that following the edges in the right direction never creates a loop ("acyclic"). Such graphs are well-studied, and the constraints make it easy to automate creating images of them without edges having to cross each other, etc. See https://stackoverflow.com/questions/3522889/visualizing-a-dag for example.	[reply]
Re^2: Visualizing a dependency graph in a web page by LanX (Saint) on Apr 01, 2022 at 14:17 UTC
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}	[reply] [d/l] [select]
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
Re^5: Visualizing a dependency graph in a web page by kennethk (Abbot) on Apr 01, 2022 at 23:43 UTC
Some notes below your chosen depth have not been shown here
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]
Re: Visualizing a dependency graph in a web page by marto (Cardinal) on Apr 01, 2022 at 13:18 UTC
Some time ago I was asked to look at something similar, and spent a little time looking at a perl backend sending JSON to a front end using D3.js, along the lines of this. The task didn't get very far as the client wanted some other work done.	[reply]
Re: Visualizing a dependency graph in a web page by hippo (Archbishop) on Apr 01, 2022 at 13:24 UTC
I don't know what it would be called - your keywords sound fine. I'd try "dependency" + "tree" + "graph" maybe. Anyway, the graphical dependency trees on MetaCPAN sound like the sort of thing you might want. eg: https://cpandeps.grinnz.com/?dist_version=&phase=test&recommends=1&suggests=1&perl_version=v5.34.0&style=auto&dist=XML-Twig. Might be a reasonable starting point? 🦛	[reply]
Re: Visualizing a dependency graph in a web page by Fletch (Bishop) on Apr 01, 2022 at 14:10 UTC
I you just want a static image I'd use GraphViz2 and let graphviz do the heavy lifting. If you want something you can interact with then d3 or vega would be the things to peek at (the latter may have something close to off the shelf, the former you might need to do more yourself but may wind up being more flexible). The cake is a lie. The cake is a lie. The cake is a lie.	[reply]
Re^2: Visualizing a dependency graph in a web page by etj (Priest) on Apr 09, 2022 at 20:24 UTC
I'd just add that if you make a Graph object you can give it to `$gv = GraphViz2->from_graph($g)` then produce an SVG from that with `$gv->run(output_file => 'out.svg')`. See https://metacpan.org/pod/GraphViz2#from_graph for more.	[reply] [d/l] [select]
Re^2: Visualizing a dependency graph in a web page by LanX (Saint) on Apr 01, 2022 at 14:23 UTC
Thanks, I'll take a look into it. > I you just want a static image I'd use GraphViz2 and let graphviz do the heavy lifting. no, but I need a start that can be manually adjusted. And AFAIK it's possible to export coordinates with graphviz. Cheers Rolf _{(addicted to the Perl Programming Language :) Wikisyntax for the Monastery}	[reply]
Re^3: Visualizing a dependency graph in a web page by Fletch (Bishop) on Apr 01, 2022 at 14:40 UTC
Definitely could ask `dot` to spit out things as an SVG or JSON which you then could instrument / manipulate with d3 or vega. Edit: also WRT node shapes mentioned elsewhere: you should be able to specify `shape => "whatever"` in the `add_node` call and pick a value from the supported shape tags. The cake is a lie. The cake is a lie. The cake is a lie.	[reply] [d/l] [select]
Re^3: Visualizing a dependency graph in a web page by Anonymous Monk on Apr 01, 2022 at 18:29 UTC
https://stackoverflow.com/a/40943217	[reply]
Re: Visualizing a dependency graph in a web page by Anonymous Monk on Apr 01, 2022 at 23:50 UTC
Wish jsgraphviz -> https://graphviz.org/about/ viz.js - graphviz built with emscripten for use on the web and in node.js http://viz-js.com very good	[reply]
Re^2: Visualizing a dependency graph in a web page by LanX (Saint) on Apr 02, 2022 at 10:37 UTC
> http://viz-js.com Wow, that's actually pretty cool. =) Thanks a lot, will try it out! Cheers Rolf _{(addicted to the Perl Programming Language :) Wikisyntax for the Monastery}	[reply]
Re^3: Visualizing a dependency graph in a web page by LanX (Saint) on Apr 03, 2022 at 13:17 UTC
For the records, this is an decent solution for the case described in the OP http://viz-js.com `# http://www.graphviz.org/content/cluster digraph G { node [shape=box] { rank = same j4; j3; } j1 -> j4; j2 -> j4; j2 -> j5; j7 -> j5; j3 -> j6; j4 -> j6; j5 -> j6 }` [download] Cheers Rolf _{(addicted to the Perl Programming Language :) Wikisyntax for the Monastery}	[reply] [d/l]