    module Bench.Vector.TestData.Graph
      ( randomGraph
      ) where

    import System.Random.Stateful
    import qualified Data.Vector as V
    import qualified Data.Vector.Mutable as MV
    import qualified Data.Vector.Unboxed as U

    randomGraph
      :: (StatefulGen g m, MV.PrimMonad m)
      => g
      -> Int
      -> m (Int, U.Vector Int, U.Vector Int)
    randomGraph :: forall g (m :: * -> *).
    (StatefulGen g m, PrimMonad m) =>
    g -> Int -> m (Int, Vector Int, Vector Int)
    randomGraph g
    g Int
    edges = do
      let vertices :: Int
    vertices = Int
    edges Int -> Int -> Int
    forall a. Integral a => a -> a -> a
    `div` Int
    10
      marr <- Int -> [Int] -> m (MVector (PrimState m) [Int])
    forall (m :: * -> *) a.
    PrimMonad m =>
    Int -> a -> m (MVector (PrimState m) a)
    MV.replicate Int
    vertices []
      addRandomEdges g vertices marr edges
      arr <- V.unsafeFreeze marr
      let (as, bs) = unzip [ (i, j) | i <- [0 .. vertices - 1], j <- arr V.! i ]
      return (vertices, U.fromList as, U.fromList bs)

    addRandomEdges
      :: (StatefulGen g m, MV.PrimMonad m)
      => g
      -> Int
      -> MV.MVector (MV.PrimState m) [Int]
      -> Int
      -> m ()
    addRandomEdges :: forall g (m :: * -> *).
    (StatefulGen g m, PrimMonad m) =>
    g -> Int -> MVector (PrimState m) [Int] -> Int -> m ()
    addRandomEdges g
    g Int
    vertices MVector (PrimState m) [Int]
    arr = Int -> m ()
    forall {m :: * -> *} {t}.
    (PrimState m ~ PrimState m, Eq t, Num t, StatefulGen g m,
     PrimMonad m) =>
    t -> m ()
    fill
      where
        fill :: t -> m ()
    fill t
    0 = () -> m ()
    forall a. a -> m a
    forall (m :: * -> *) a. Monad m => a -> m a
    return ()
        fill t
    e = do
          m1 <- (Int, Int) -> g -> m Int
    forall a g (m :: * -> *).
    (UniformRange a, StatefulGen g m) =>
    (a, a) -> g -> m a
    forall g (m :: * -> *). StatefulGen g m => (Int, Int) -> g -> m Int
    uniformRM (Int
    0, Int
    vertices Int -> Int -> Int
    forall a. Num a => a -> a -> a
    - Int
    1) g
    g
          m2 <- uniformRM (0, vertices - 1) g
          let lo = Int -> Int -> Int
    forall a. Ord a => a -> a -> a
    min Int
    m1 Int
    m2
              hi = Int -> Int -> Int
    forall a. Ord a => a -> a -> a
    max Int
    m1 Int
    m2
          ns <- MV.read arr lo
          if lo == hi || hi `elem` ns
            then fill e
            else MV.write arr lo (hi : ns) >> fill (e - 1)