agnishom

Untitled

Oct 14th, 2021
680
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. module Graph.Algorithms where
  2.  
  3. import Data.Set (Set)
  4. import qualified Data.Set as Set
  5.  
  6. foldGraph :: Ord v =>
  7.                 (v -> x -> x)       -- operation
  8.             ->  x                   -- initial value
  9.             ->  [v]                 -- initial states
  10.             ->  (v -> [v])          -- successors
  11.             ->  x                   -- final value
  12. foldGraph op init inits succ = go Set.empty inits
  13.     where
  14.         go _ [] = init
  15.         go sofar (v:vs)
  16.             | Set.member v sofar = go sofar vs
  17.             | otherwise = v `op` (go (Set.insert v sofar) ((succ v) ++ vs))
  18.  
  19. collectGraph :: Ord v =>
  20.                 (v -> [x])          -- result at each vertex
  21.                 -> [v]              -- initial vertices
  22.                 -> (v -> [v])       -- successors
  23.                 -> [x]
  24. collectGraph forv =
  25.     foldGraph (\v x -> forv v ++ x) []
  26.  
  27.  
  28. reachability :: Ord v =>
  29.                    [v]                 -- initial states
  30.                 -> (v -> [v])          -- successors
  31.                 -> (v -> Bool)         -- final states
  32.                 -> Bool
  33. reachability inits succ final = foldGraph
  34.                                     (\v x -> final v || x)
  35.                                     False
  36.                                     inits
  37.                                     succ
RAW Paste Data