Graphs.jl icon indicating copy to clipboard operation
Graphs.jl copied to clipboard
verified publisher icon JuliaGraphs

Feature Request: Dominator Tree

Open schlichtanders opened this issue 4 years ago • 1 comments

It would be nice to have an implementation of the Lengauer-Tarjan algorithm for creating the dominator tree from a given directed graph. Dominator

By looking around for solutions I've found this previous attempt in LightGraphs which somehow hasn't got any attention

https://github.com/sbromberger/LightGraphs.jl/pull/1357 it tries to solve this old issue https://github.com/sbromberger/LightGraphs.jl/issues/1279

an alternativ implementation seems to be in Core.Compiler.DomTree but it seems to be an implementation detail of the compiler, not sure whether it can be reused for Graphs.jl

schlichtanders avatar Feb 14 '22 15:02 schlichtanders

Hi @schlichtanders :wave: I'm not an expert in dominator trees, but any addition to the library is welcome! Do you think you can revisit the old PR you mentioned and resubmit it here with the appropriate tests?

gdalle avatar Mar 10 '22 08:03 gdalle