reachableGraph loops on cyclic input
GHC.Data.Graph.Directed.reachableGraph
calculates a reachability map for its input graph: mapping a vertex to the set of vertices that are its transitive, directed neighbours.
For cyclic input, the current implementation returns a map where some of the values diverge. This can be demonstrated even in the simplest case of the one-vertex one-edge graph.
For reference, the current implementation is:
reachableGraph :: IntGraph -> IM.IntMap IS.IntSet
reachableGraph g = res
where
do_one v = IS.unions (IS.fromList (g ! v) : mapMaybe (flip IM.lookup res) (g ! v))
res = IM.fromList [(v, do_one v) | v <- vertices g]
For g = {0 -> [0]}
, this creates the map res = {0 -> mu r. IS.unions [IS.fromList [0], r]}
since g ! 0
is [0]
and thus mapMaybe (flip IM.lookup res) [0]
is [r]
. We're effectively creating the set IS.fromList (fix (0:))
, which diverges.