Skip to content

Add detection of strongly connected components in the data flow precedence rules

Illya Shapoval requested to merge ishapova/Gaudi:add-tarjan-graph-algo into master

The feature detects strongly connected components (SCCs) of any topology, with cycles and loops being the simplest instances. The check is performed at initialization and produces an error upon detection of an SCC (am open to turn this into a warning if needed). It can be disabled by setting PrecedenceSvc::VerifyTaskPrecedenceRules to False.

The PRG validator is based on Tarjan's algorithm (with minor modifications), which matches the lower bound of O(V+E) for the problem of this type.

Edited by Illya Shapoval

Merge request reports