diff options
Diffstat (limited to 'src/Hakyll/Core/DirectedGraph.hs')
| -rw-r--r-- | src/Hakyll/Core/DirectedGraph.hs | 31 |
1 files changed, 21 insertions, 10 deletions
diff --git a/src/Hakyll/Core/DirectedGraph.hs b/src/Hakyll/Core/DirectedGraph.hs index ff9121a..66cb84d 100644 --- a/src/Hakyll/Core/DirectedGraph.hs +++ b/src/Hakyll/Core/DirectedGraph.hs @@ -1,6 +1,6 @@ +-------------------------------------------------------------------------------- -- | Representation of a directed graph. In Hakyll, this is used for dependency -- tracking. --- module Hakyll.Core.DirectedGraph ( DirectedGraph , fromList @@ -12,6 +12,8 @@ module Hakyll.Core.DirectedGraph , reachableNodes ) where + +-------------------------------------------------------------------------------- import Prelude hiding (reverse) import Control.Arrow (second) import Data.Monoid (mconcat) @@ -20,47 +22,55 @@ import Data.Maybe (fromMaybe) import qualified Data.Map as M import qualified Data.Set as S + +-------------------------------------------------------------------------------- import Hakyll.Core.DirectedGraph.Internal + +-------------------------------------------------------------------------------- -- | Construction of directed graphs --- fromList :: Ord a => [(a, Set a)] -- ^ List of (node, reachable neighbours) -> DirectedGraph a -- ^ Resulting directed graph fromList = DirectedGraph . M.fromList . map (\(t, d) -> (t, Node t d)) + +-------------------------------------------------------------------------------- -- | Deconstruction of directed graphs --- toList :: DirectedGraph a -> [(a, Set a)] toList = map (second nodeNeighbours) . M.toList . unDirectedGraph + +-------------------------------------------------------------------------------- -- | Check if a node lies in the given graph --- member :: Ord a => a -- ^ Node to check for -> DirectedGraph a -- ^ Directed graph to check in -> Bool -- ^ If the node lies in the graph member n = M.member n . unDirectedGraph + +-------------------------------------------------------------------------------- -- | Get all nodes in the graph --- nodes :: Ord a => DirectedGraph a -- ^ Graph to get the nodes from -> Set a -- ^ All nodes in the graph nodes = M.keysSet . unDirectedGraph + +-------------------------------------------------------------------------------- -- | Get a set of reachable neighbours from a directed graph --- neighbours :: Ord a => a -- ^ Node to get the neighbours of -> DirectedGraph a -- ^ Graph to search in -> Set a -- ^ Set containing the neighbours -neighbours x = fromMaybe S.empty . fmap nodeNeighbours - . M.lookup x . unDirectedGraph +neighbours x = fromMaybe S.empty . fmap nodeNeighbours . + M.lookup x . unDirectedGraph + +-------------------------------------------------------------------------------- -- | Reverse a directed graph (i.e. flip all edges) --- reverse :: Ord a => DirectedGraph a -> DirectedGraph a @@ -69,8 +79,9 @@ reverse = mconcat . map reverse' . M.toList . unDirectedGraph reverse' (id', Node _ neighbours') = fromList $ zip (S.toList neighbours') $ repeat $ S.singleton id' + +-------------------------------------------------------------------------------- -- | Find all reachable nodes from a given set of nodes in the directed graph --- reachableNodes :: Ord a => Set a -> DirectedGraph a -> Set a reachableNodes set graph = reachable (setNeighbours set) set where |