git.iko.soy/hakyll
on 877cb21 help sign in
hakyll/src/Hakyll/Core/DirectedGraph.hs
90 lines 3.3 kB history raw
1--------------------------------------------------------------------------------
2-- | Representation of a directed graph. In Hakyll, this is used for dependency
3-- tracking.
4{-# LANGUAGE DeriveDataTypeable #-}
5{-# LANGUAGE GeneralizedNewtypeDeriving #-}
6module Hakyll.Core.DirectedGraph
7 ( DirectedGraph
9 , fromList
10 , toList
12 , member
13 , nodes
14 , neighbours
15 ) where
18--------------------------------------------------------------------------------
19import Control.Arrow (second)
20import Control.DeepSeq (NFData)
21import Data.Binary (Binary)
22import Data.Map (Map)
23import qualified Data.Map as M
24import Data.Maybe (fromMaybe)
25import Data.Monoid (Monoid (..))
26import Data.Set (Set)
27import qualified Data.Set as S
28import Data.Typeable (Typeable)
29import Prelude hiding (reverse)
32--------------------------------------------------------------------------------
33-- | Type used to represent a directed graph
34newtype DirectedGraph a = DirectedGraph {unDirectedGraph :: Map a [a]}
35 deriving (Show, Binary, NFData, Typeable)
38--------------------------------------------------------------------------------
39-- | Allow users to concatenate different graphs
40instance Ord a => Monoid (DirectedGraph a) where
41 mempty = DirectedGraph M.empty
42 mappend (DirectedGraph m1) (DirectedGraph m2) = DirectedGraph $
43 M.unionWith (\x y -> sortUnique (x ++ y)) m1 m2
46--------------------------------------------------------------------------------
47-- | Construction of directed graphs
48fromList :: Ord a
49 => [(a, [a])] -- ^ List of (node, reachable neighbours)
50 -> DirectedGraph a -- ^ Resulting directed graph
51fromList = DirectedGraph . M.fromList . map (second sortUnique)
54--------------------------------------------------------------------------------
55-- | Deconstruction of directed graphs
56toList :: DirectedGraph a
57 -> [(a, [a])]
58toList = M.toList . unDirectedGraph
61--------------------------------------------------------------------------------
62-- | Check if a node lies in the given graph
63member :: Ord a
64 => a -- ^ Node to check for
65 -> DirectedGraph a -- ^ Directed graph to check in
66 -> Bool -- ^ If the node lies in the graph
67member n = M.member n . unDirectedGraph
70--------------------------------------------------------------------------------
71-- | Get all nodes in the graph
72nodes :: Ord a
73 => DirectedGraph a -- ^ Graph to get the nodes from
74 -> Set a -- ^ All nodes in the graph
75nodes = M.keysSet . unDirectedGraph
78--------------------------------------------------------------------------------
79-- | Get a set of reachable neighbours from a directed graph
80neighbours :: Ord a
81 => a -- ^ Node to get the neighbours of
82 -> DirectedGraph a -- ^ Graph to search in
83 -> [a] -- ^ Set containing the neighbours
84neighbours x dg = fromMaybe [] $ M.lookup x $ unDirectedGraph dg
87--------------------------------------------------------------------------------
88-- | Sort and make unique
89sortUnique :: Ord a => [a] -> [a]
90sortUnique = S.toAscList . S.fromList