module Data.Graph.Generation where
import Control.Monad (replicateM)
import Data.List (foldl')
import System.Random
import Data.Graph.Types
newtype Probability = P Double deriving (Eq, Ord, Show)
probability :: Double -> Probability
probability v | v >= 1 = P 1 | v <= 0 = P 0 | otherwise = P v
erdosRenyi :: Graph g => Int -> Probability -> IO (g Int ())
erdosRenyi n (P p) = go [1..n] p empty
where
go :: Graph g => [Int] -> Double -> g Int () -> IO (g Int ())
go [] _ g = return g
go (v:vs) pv g = do
rnds <- replicateM (length vs + 1) $ randomRIO (0.0, 1.0)
flipDir <- randomRIO (True, False)
let vs' = zip rnds vs
let g' = insertVertex g v
go vs pv $! (foldl' (putV pv v flipDir) g' vs')
putV :: Graph g => Double -> Int -> Bool -> g Int () -> (Double, Int) -> g Int ()
putV pv v flipDir g (p', v')
| p' < pv = insertEdgePair g pair
| otherwise = g
where pair = if flipDir then (v', v) else (v, v')
randomMat :: Int -> IO [[Int]]
randomMat n = replicateM n randRow
where randRow = replicateM n (randomRIO (0,1)) :: IO [Int]