search

cylc / cylc-flow

Cylc: a workflow engine for cycling systems.
https://cylc.github.io
GNU General Public License v3.0
330 stars 93 forks source link

Remove redundant graph edges. #4365

Open hjoliver opened 7 years ago

hjoliver commented 7 years ago

Use of family triggers on families with internal structure creates a lot of unnecessary dependencies.

Example (from https://github.com/cylc/cylc/pull/2311 ref https://github.com/cylc/cylc/pull/2311#issuecomment-305157438), this graph:

graph = "model => NCM:succeed-all => upload"

where family NCM has internal dependencies:

graph = "NCM__select => NCM__frames<n> => NCM__movie"

results in a graph where all dependencies between internal family members and the outside graph are redundant: foo

Graphviz "transitive reduction" (also available via pygraphviz) can fix this: tred foo.dot > foo-tred.dot: baz

It would be good to do this in Cylc. To get rid of redundant prerequisites as well as simplify the graph we should generate the pygraphviz graph structure early on, from the raw Cylc graph string, and then - after transitive reduction - use that to generate task prerequisites.

hjoliver commented 7 years ago

For the record, graphviz also has a way to overlay some edges that diverge from or converge on a single node, dot -Gconcentrate foo.dot (which, in the absence of transitive reduction, is quite nice): bar