common/util/Util/Graph.hs

-- Copyright (c) Facebook, Inc. and its affiliates.

module Util.Graph
  ( postorder
  ) where

import Data.Hashable
import qualified Data.HashSet as HashSet
import qualified Data.HashMap.Strict as HashMap

-- | Post-order traversal of a graph: guarantees that the dependents
-- of a node occur before it in the result list, while as far as
-- possible retaining the original order of the nodes.
postorder
  :: (Hashable vertex, Eq vertex)
  => [node]
    -- ^ Nodes in the order of traversal
  -> (node -> vertex)
    -- ^ Extract a hashable vertex from the node
  -> (node -> [vertex])
    -- ^ Out-edges from a node. Vertices that aren't in the set of
    -- nodes are ignored.
  -> [node]
    -- ^ Result of post-order traversal
postorder nodes vert out = go HashSet.empty nodes (\_ -> [])
  where
  m = HashMap.fromList [ (vert n, n) | n <- nodes ]

  go seen [] cont = cont seen
  go seen (n : nodes) cont
    | v `HashSet.member` seen = go seen nodes cont
    | otherwise = go (HashSet.insert v seen) deps
       (\seen -> n : go seen nodes cont)
    where
      v = vert n
      deps = [ n | v <- out n, Just n <- [HashMap.lookup v m] ]