git.iko.soy/hakyll
on 9eda342 help sign in
hakyll/src/Hakyll/Core/DirectedGraph.hs
95 lines 3.4 kB history raw
1--------------------------------------------------------------------------------
2-- | Representation of a directed graph. In Hakyll, this is used for dependency
3-- tracking.
4module Hakyll.Core.DirectedGraph
5 ( DirectedGraph
6 , fromList
7 , toList
8 , member
9 , nodes
10 , neighbours
11 , reverse
12 , reachableNodes
13 ) where
16--------------------------------------------------------------------------------
17import Prelude hiding (reverse)
18import Control.Arrow (second)
19import Data.Monoid (mconcat)
20import Data.Set (Set)
21import Data.Maybe (fromMaybe)
22import qualified Data.Map as M
23import qualified Data.Set as S
26--------------------------------------------------------------------------------
27import Hakyll.Core.DirectedGraph.Internal
30--------------------------------------------------------------------------------
31-- | Construction of directed graphs
32fromList :: Ord a
33 => [(a, Set a)] -- ^ List of (node, reachable neighbours)
34 -> DirectedGraph a -- ^ Resulting directed graph
35fromList = DirectedGraph . M.fromList . map (\(t, d) -> (t, Node t d))
38--------------------------------------------------------------------------------
39-- | Deconstruction of directed graphs
40toList :: DirectedGraph a
41 -> [(a, Set a)]
42toList = map (second nodeNeighbours) . M.toList . unDirectedGraph
45--------------------------------------------------------------------------------
46-- | Check if a node lies in the given graph
47member :: Ord a
48 => a -- ^ Node to check for
49 -> DirectedGraph a -- ^ Directed graph to check in
50 -> Bool -- ^ If the node lies in the graph
51member n = M.member n . unDirectedGraph
54--------------------------------------------------------------------------------
55-- | Get all nodes in the graph
56nodes :: Ord a
57 => DirectedGraph a -- ^ Graph to get the nodes from
58 -> Set a -- ^ All nodes in the graph
59nodes = M.keysSet . unDirectedGraph
62--------------------------------------------------------------------------------
63-- | Get a set of reachable neighbours from a directed graph
64neighbours :: Ord a
65 => a -- ^ Node to get the neighbours of
66 -> DirectedGraph a -- ^ Graph to search in
67 -> Set a -- ^ Set containing the neighbours
68neighbours x = fromMaybe S.empty . fmap nodeNeighbours .
69 M.lookup x . unDirectedGraph
72--------------------------------------------------------------------------------
73-- | Reverse a directed graph (i.e. flip all edges)
74reverse :: Ord a
75 => DirectedGraph a
76 -> DirectedGraph a
77reverse = mconcat . map reverse' . M.toList . unDirectedGraph
78 where
79 reverse' (id', Node _ neighbours') = fromList $
80 zip (S.toList neighbours') $ repeat $ S.singleton id'
83--------------------------------------------------------------------------------
84-- | Find all reachable nodes from a given set of nodes in the directed graph
85reachableNodes :: Ord a => Set a -> DirectedGraph a -> Set a
86reachableNodes set graph = reachable (setNeighbours set) set
87 where
88 reachable next visited
89 | S.null next = visited
90 | otherwise = reachable (sanitize neighbours') (next `S.union` visited)
91 where
92 sanitize = S.filter (`S.notMember` visited)
93 neighbours' = setNeighbours (sanitize next)
95 setNeighbours = S.unions . map (`neighbours` graph) . S.toList