blob: 52a712da24650a5c622e6492d629b36c4e851d72 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
|
-- | Internal structure of the DirectedGraph type. Not exported outside of the
-- library.
--
module Hakyll.Core.DirectedGraph.Internal
( Node (..)
, DirectedGraph (..)
) where
import Prelude hiding (reverse, filter)
import Data.Monoid (Monoid, mempty, mappend)
import Data.Set (Set)
import Data.Map (Map)
import qualified Data.Map as M
import qualified Data.Set as S
-- | A node in the directed graph
--
data Node a = Node
{ nodeTag :: a -- ^ Tag identifying the node
, nodeNeighbours :: (Set a) -- ^ Edges starting at this node
} deriving (Show)
-- | Append two nodes. Useful for joining graphs.
--
appendNodes :: Ord a => Node a -> Node a -> Node a
appendNodes (Node t1 n1) (Node t2 n2)
| t1 /= t2 = error "appendNodes: Appending differently tagged nodes"
| otherwise = Node t1 (n1 `S.union` n2)
-- | Type used to represent a directed graph
--
newtype DirectedGraph a = DirectedGraph {unDirectedGraph :: Map a (Node a)}
deriving (Show)
-- | Allow users to concatenate different graphs
--
instance Ord a => Monoid (DirectedGraph a) where
mempty = DirectedGraph M.empty
mappend (DirectedGraph m1) (DirectedGraph m2) = DirectedGraph $
M.unionWith appendNodes m1 m2
|
