search

haskell / fgl

A Functional Graph Library for Haskell
http://hackage.haskell.org/package/fgl
Other
184 stars 54 forks source link

5.8.1.0 crashes when computing dominators in graphs with unreachable nodes #109

Closed koalaman closed 1 year ago

koalaman commented 1 year ago

When computing dominators for connected, directed graphs, 5.8.1.0 crashes when it encounters nodes not reachable from the root. Here's a MCVE:

import Data.Graph.Inductive.Graph
import Data.Graph.Inductive.Query.Dominators
import Data.Graph.Inductive.PatriciaTree

main = do
    -- The graph  1 -> 2 <- 3
    let graph = mkGraph [(1,()), (2, ()), (3, ())] [(1,2,()), (3,2,())] :: Gr () ()
    -- 5.8.0.0: [(1,[1]),(2,[2,1]),(3,[1,2,3])]
    -- 5.8.1.0: Exception: IntMap.!: key 3 is not an element of the map
    print $ dom graph 1

The issue appears to have been introduced in c8f56c18.

athas commented 1 year ago

I can reproduce. I will take a look.

Do we agree that the old behaviour of dom was clearly wrong, though? I'm fine with just reverting the change if the original behaviour was somehow sensible (beyond being just a load-bearing bug for various things), but the results it produced for unconnected graphs really did not mesh with my intuition of what "dominator" means.