graph.hs

module Main where

import qualified Data.Map as Map

import           Control.Monad (guard)
import           Data.Maybe    (isJust)


data Graph a = Graph (Map.Map a [a])            

empty :: Graph a
empty = Graph $ Map.empty

nodeExists :: (Ord a) => a -> Graph a -> Bool
nodeExists n (Graph m) = isJust $ Map.lookup n m

addNode :: (Ord a) => a -> Graph a -> Graph a
addNode n (Graph m) = Graph $ Map.insert n [] m

-- Args: from node, to node, graph
addEdge :: (Ord a) => a -> a -> Graph a -> Maybe (Graph a)
addEdge from to g@(Graph m) = do
    -- Make sure both nodes exist.
    guard $ nodeExists from g
    guard $ nodeExists to g

    -- Get the old adjacency list for the originating node.
    oldList <- Map.lookup from m

    -- Add the target node to the adj list.
    return $ Graph $ Map.insert from (to : oldList) m