Add directed graph modules

1 files changed, 25 insertions, 0 deletions

diff --git a/src/Hakyll/Core/DirectedGraph/ObsoleteFilter.hs b/src/Hakyll/Core/DirectedGraph/ObsoleteFilter.hs
new file mode 100644
index 0000000..a3bc57a
--- /dev/null
+++ b/src/Hakyll/Core/DirectedGraph/ObsoleteFilter.hs
@@ -0,0 +1,25 @@
+-- | Module exporting a function that works as a filter on a dependency graph.
+-- Given a list of obsolete nodes, this filter will reduce the graph so it only
+-- contains obsolete nodes and nodes that depend (directly or indirectly) on
+-- obsolete nodes.
+--
+module Hakyll.Core.DirectedGraph.ObsoleteFilter
+    ( obsoleteFilter
+    ) where
+
+import qualified Data.Set as S
+
+import Hakyll.Core.DirectedGraph
+import qualified Hakyll.Core.DirectedGraph as DG
+
+-- | Given a list of obsolete items, filter the dependency graph so it only
+-- contains these items
+--
+obsoleteFilter :: Ord a
+               => [a]              -- ^ List of obsolete items
+               -> DirectedGraph a  -- ^ Dependency graph
+               -> DirectedGraph a  -- ^ Resulting dependency graph
+obsoleteFilter obsolete graph =
+    let reversed = DG.reverse graph
+        allObsolete = S.unions $ map (flip reachableNodes reversed) obsolete
+    in DG.filter (`S.member` allObsolete) graph