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