module Graph.Algorithms where

import Data.Set (Set)
import qualified Data.Set as Set

foldGraph :: Ord v =>
                (v -> x -> x)       -- operation
            ->  x                   -- initial value
            ->  [v]                 -- initial states
            ->  (v -> [v])          -- successors
            ->  x                   -- final value
foldGraph op init inits succ = go Set.empty inits
    where
        go _ [] = init
        go sofar (v:vs)
            | Set.member v sofar = go sofar vs
            | otherwise = v `op` (go (Set.insert v sofar) ((succ v) ++ vs))

collectGraph :: Ord v =>
                (v -> [x])          -- result at each vertex
                -> [v]              -- initial vertices
                -> (v -> [v])       -- successors
                -> [x]
collectGraph forv =
    foldGraph (\v x -> forv v ++ x) []


reachability :: Ord v =>
                   [v]                 -- initial states
                -> (v -> [v])          -- successors
                -> (v -> Bool)         -- final states
                -> Bool
reachability inits succ final = foldGraph
                                    (\v x -> final v || x)
                                    False
                                    inits
                                    succ