-- A module for creating and handling directed graphs
-- Module to handle graph operations.  Implements a graph ADT.
-- In this case the adjacency list is saved in a Map rather than in
--   as a list.  It is thus faster for large data sets.
-- by Scot Drysdale on 8/21/07

module DigraphMap (AdjList, Digraph, Edge,
       insertVertex, insertEdge, makeDigraph, getAdj, empty, 
       vertexInGraph
       ) where

import qualified Data.Map as Map

-- In these type declarations, v is the vertex type 
-- and e is the edge label type

type AdjList v e = [(v, e)]
type Digraph v e = Map.Map v (AdjList v e)
type Edge v e    = (v, v, e)

-- Creates an empty Digraph
empty :: Digraph v e
empty = Map.empty

-- Inserts vertex vert into digraph g.
insertVertex       :: (Ord v) => v -> Digraph v e -> Digraph v e 
insertVertex vert g = Map.insert vert [] g

-- Insert edge into digraph.  Source and destination vertices must be present.
insertEdge         :: (Ord v) =>  Edge v e -> Digraph v e -> Digraph v e
insertEdge e@(source, dest, label) g
   | Map.member source g && Map.member dest g = 
         Map.insertWith (++) source [(dest, label)] g
   | otherwise      = error "insertEdge: edge endpoint not in the graph"

-- Create a digraph out of a list of vertices and a list of edges
makeDigraph        :: (Ord v) => [v] -> [Edge v e] -> Digraph v e
makeDigraph vertices edges = foldr insertEdge
         (foldr insertVertex empty vertices) edges

-- Get the adjacency list associated with vertex vert in graph
getAdj             :: (Ord v) => v -> Digraph v e ->AdjList v e
getAdj vert graph   = case Map.lookup vert graph of
                        Nothing -> error "getAdj: vertex not in graph"
                        (Just adjList) -> adjList
                        
-- Tests to see if a vertex is in the graph
vertexInGraph     :: (Ord v) => v -> Digraph v e -> Bool
vertexInGraph vert g = Map.member vert g