1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
|
module 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 g edges = do
let vertices = edges `div` 10
marr <- MV.replicate 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 g vertices arr = fill
where
fill 0 = return ()
fill e = do
m1 <- uniformRM (0, vertices - 1) g
m2 <- uniformRM (0, vertices - 1) g
let lo = min m1 m2
hi = max m1 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)
|
