git.iko.soy/hakyll
on 9939708 help sign in
hakyll/src/Hakyll/Core/DirectedGraph.hs
76 lines 2.5 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 , nodes
8 , neighbours
9 , reverse
10 , filter
11 , reachableNodes
12 ) where
14import Prelude hiding (reverse, filter)
15import Data.Monoid (mconcat)
16import Data.Set (Set)
17import Data.Maybe (fromMaybe)
18import qualified Data.Map as M
19import qualified Data.Set as S
21import Hakyll.Core.DirectedGraph.Internal
23-- | Construction of directed graphs
24--
25fromList :: Ord a
26 => [(a, Set a)] -- ^ List of (node, reachable neighbours)
27 -> DirectedGraph a -- ^ Resulting directed graph
28fromList = DirectedGraph . M.fromList . map (\(t, d) -> (t, Node t d))
30-- | Get all nodes in the graph
31--
32nodes :: Ord a
33 => DirectedGraph a -- ^ Graph to get the nodes from
34 -> Set a -- ^ All nodes in the graph
35nodes = M.keysSet . unDirectedGraph
37-- | Get a set of reachable neighbours from a directed graph
38--
39neighbours :: Ord a
40 => a -- ^ Node to get the neighbours of
41 -> DirectedGraph a -- ^ Graph to search in
42 -> Set a -- ^ Set containing the neighbours
43neighbours x = fromMaybe S.empty . fmap nodeNeighbours
44 . M.lookup x . unDirectedGraph
46-- | Reverse a directed graph (i.e. flip all edges)
47--
48reverse :: Ord a
49 => DirectedGraph a
50 -> DirectedGraph a
51reverse = mconcat . map reverse' . M.toList . unDirectedGraph
52 where
53 reverse' (id', Node _ neighbours') = fromList $
54 zip (S.toList neighbours') $ repeat $ S.singleton id'
56-- | Filter a directed graph (i.e. remove nodes based on a predicate)
57--
58filter :: Ord a
59 => (a -> Bool) -- ^ Predicate
60 -> DirectedGraph a -- ^ Graph
61 -> DirectedGraph a -- ^ Resulting graph
62filter predicate =
63 DirectedGraph . M.filterWithKey (\k _ -> predicate k) . unDirectedGraph
65-- | Find all reachable nodes from a given node in the directed graph
66--
67reachableNodes :: Ord a => a -> DirectedGraph a -> Set a
68reachableNodes x graph = reachable (neighbours x graph) (S.singleton x)
69 where
70 reachable next visited
71 | S.null next = visited
72 | otherwise = reachable (sanitize neighbours') (next `S.union` visited)
73 where
74 sanitize = S.filter (`S.notMember` visited)
75 neighbours' = S.unions $ map (flip neighbours graph)
76 $ S.toList $ sanitize next