content: module TestData.Graph ( randomGraph )
  where
  
  import System.Random.MWC
  import qualified Data.Array.ST as STA
  import qualified Data.Vector.Unboxed as V
  
  import Control.Monad.ST ( ST, runST )
  
  randomGraph :: Int -> (Int, V.Vector Int, V.Vector Int)
  randomGraph e
    = runST (
      do
        g <- create
        arr <- STA.newArray (0,n-1) [] :: ST s (STA.STArray s Int [Int])
        addRandomEdges n g arr e
        xs <- STA.getAssocs arr
        let (as,bs) = unzip [(i,j) | (i,js) <- xs, j <- js ]
        return (n, V.fromListN (length as) as, V.fromListN (length bs) bs)
      )
    where
      n = e `div` 10
  
  addRandomEdges :: Int -> Gen s -> STA.STArray s Int [Int] -> Int -> ST s ()
  addRandomEdges n g arr = fill
    where
      fill 0 = return ()
      fill e
        = do
            m <- random_index
            n <- random_index
            let lo = min m n
                hi = max m n
            ns <- STA.readArray arr lo
            if lo == hi || hi `elem` ns
              then fill e
              else do
                     STA.writeArray arr lo (hi:ns)
                     fill (e-1)
  
      random_index = do
                       x <- uniform g
                       let i = floor ((x::Double) * toEnum n)
                       if i == n then return 0 else return i
  
  