-- This module implements the AdjacencyList type which is an instance
-- of several of the graph type classes.

module AdjacencyList(AdjacencyList, adj_list, 
		     vertex, edge, idx, module Graph,
		     Vertex, Edge) where

  import Graph
  import Array
  
  data AdjacencyList = AdjList (Array Int [Int]) deriving (Read, Show)
  data Vertex = V Int deriving (Eq, Ord, Read, Show)
  data Edge = E Int Int deriving (Eq, Ord, Read, Show)

  adj_list :: Int -> [(Int,Int)] -> AdjacencyList
  adj_list n elist = 
    AdjList (accumArray (++) [] (0, n - 1) [ (s, [t]) | (s,t) <- elist])

  vertex n = (V n)
  edge u v = (E u v)
  idx (V v) = v

  instance Graph AdjacencyList Edge Vertex where
    src (E s t) g = V s
    tgt (E s t) g = V t

  instance IncidenceGraph AdjacencyList Edge Vertex where
    out_edges (V s) (AdjList adj) = [ E s t | t <- (adj!s) ]
    out_degree (V s) (AdjList adj) = length (adj!s)

  instance VertexListGraph AdjacencyList Vertex where
    vertices (AdjList adj) = [V v | v <- (iota n) ]
      where (s,n) = bounds adj
    num_vertices (AdjList adj) = n+1
      where (s,n) = bounds adj

  instance EdgeListGraph AdjacencyList Edge Vertex where
    edges (AdjList adj) = [(E s t) | s <- (iota n), t <- (adj!s) ]
      where (s,n) = bounds adj
    num_edges (AdjList adj) = count_edges n
      where (s,n) = bounds adj
            count_edges 0 = 0
            count_edges i = (length (adj!i)) + count_edges (i - 1)

  iota 0 = [0]
  iota n = n : (iota (n - 1))