content: {-# LANGUAGE CPP #-}
  module SparseGraph (
      Vertex, Weight,
      Graph,
      weight, insertEdge,
      randomGraph,
      mkGraph,
      toAdjMatrix,
      fromAdjMatrix,
      checksum
    ) where
  
  #if MIN_VERSION_containers(0,5,0)
  import qualified Data.IntMap.Strict as Map
  #else
  import qualified Data.IntMap as Map
  #endif
  import qualified Data.IntSet as IntSet
  import Data.IntMap (IntMap)
  import System.Random
  import Data.Array.Unboxed
  
  -- -----------------------------------------------------------------------------
  -- Graph representation
  
  -- <<Graph
  type Vertex = Int
  type Weight = Int
  
  type Graph = IntMap (IntMap Weight)
  
  weight :: Graph -> Vertex -> Vertex -> Maybe Weight
  weight g i j = do
    jmap <- Map.lookup i g
    Map.lookup j jmap
  -- >>
  
  insertEdge :: Vertex -> Vertex -> Weight -> Graph -> Graph
  insertEdge i j w m = Map.insertWith Map.union i (Map.singleton j w) m
  
  -- -----------------------------------------------------------------------------
  -- Testing
  
  randomGraph :: StdGen -> Int -> Int -> Int -> (Graph, [Vertex])
  randomGraph g max_vertex max_weight edges = (mat, vs)
    where
        (g1,g2) = split g
        (g3,g4) = split g2
        is = take edges $ randomRs (0,max_vertex) g1
        js = take edges $ randomRs (0,max_vertex) g3
        ws = take edges $ randomRs (1,max_weight) g4
  
        mat = foldr ins Map.empty (zip3 is js ws)
          where ins (i,j,w) = insertEdge i j w
  
        vs = IntSet.elems (IntSet.fromList (is ++ js))
  
  mkGraph :: [[Int]] -> Graph
  mkGraph xss = Map.fromList (zipWith row [0..] xss)
    where
     row i xs = (i, Map.fromList [ (j, w) | (j,w) <- zip [0..] xs, w /= 100 ])
  
  type AdjMatrix = UArray (Int,Int) Weight
  
  toAdjMatrix :: Int -> Graph -> AdjMatrix
  toAdjMatrix k m = accumArray (\_ e -> e) 999 ((0,0),(k,k))
        [ ((i,j),w) | (i,jmap) <- Map.toList m, (j,w) <- Map.toList jmap ]
  
  fromAdjMatrix :: AdjMatrix -> [[Int]]
  fromAdjMatrix m = chunk (k+1) (elems m)
    where
     (_, (k,_)) = bounds m
  
  chunk :: Int -> [a] -> [[a]]
  chunk _ [] = []
  chunk n xs = as : chunk n bs
    where (as,bs) = splitAt n xs
  
  checksum :: Graph -> Int
  checksum m = sum (concat (map Map.elems (Map.elems m)))
  
  
  