module Hakyll.Core.DirectedGraph
( DirectedGraph
, fromList
, toList
, member
, nodes
, neighbours
, reverse
, reachableNodes
, sanitize
) where
import Prelude hiding (reverse)
import Control.Arrow (second)
import Data.Monoid (mconcat)
import Data.Set (Set)
import Data.Maybe (fromMaybe)
import qualified Data.Map as M
import qualified Data.Set as S
import Hakyll.Core.DirectedGraph.Internal
fromList :: Ord a
=> [(a, Set a)]
-> DirectedGraph a
fromList = DirectedGraph . M.fromList . map (\(t, d) -> (t, Node t d))
toList :: DirectedGraph a
-> [(a, Set a)]
toList = map (second nodeNeighbours) . M.toList . unDirectedGraph
member :: Ord a
=> a
-> DirectedGraph a
-> Bool
member n = M.member n . unDirectedGraph
nodes :: Ord a
=> DirectedGraph a
-> Set a
nodes = M.keysSet . unDirectedGraph
neighbours :: Ord a
=> a
-> DirectedGraph a
-> Set a
neighbours x = fromMaybe S.empty . fmap nodeNeighbours
. M.lookup x . unDirectedGraph
reverse :: Ord a
=> DirectedGraph a
-> DirectedGraph a
reverse = mconcat . map reverse' . M.toList . unDirectedGraph
where
reverse' (id', Node _ neighbours') = fromList $
zip (S.toList neighbours') $ repeat $ S.singleton id'
reachableNodes :: Ord a => Set a -> DirectedGraph a -> Set a
reachableNodes set graph = reachable (setNeighbours set) set
where
reachable next visited
| S.null next = visited
| otherwise = reachable (sanitize' neighbours') (next `S.union` visited)
where
sanitize' = S.filter (`S.notMember` visited)
neighbours' = setNeighbours (sanitize' next)
setNeighbours = S.unions . map (`neighbours` graph) . S.toList
sanitize :: Ord a => DirectedGraph a -> DirectedGraph a
sanitize (DirectedGraph graph) = DirectedGraph $ M.map sanitize' graph
where
sanitize' (Node t n) = Node t $ S.filter (`M.member` graph) n