graphite 0.9.4.0 → 0.9.5.0

raw patch · 2 files changed

+71/−24 lines, 2 filesPVP: major bump suggested

API removals or changes: PVP suggests a major version bump

API changes (from Hackage documentation)

Files

• graphite.cabal +1/−1
• src/Data/Graph/Generation.hs +70/−23

@@ -1,5 +1,5 @@ name:                graphite-version:             0.9.4.0+version:             0.9.5.0 synopsis:            Graphs and networks library description:         Represent, analyze and visualize graphs homepage:            https://github.com/alx741/graphite#readme

@@ -1,48 +1,95 @@ {-# LANGUAGE ScopedTypeVariables #-} -module Data.Graph.Generation where+module Data.Graph.Generation+    ( erdosRenyi+    , erdosRenyiU+    , erdosRenyiD+    , rndGraph'+    , rndGraph+    , rndAdjacencyMatrix+    ) where  import Control.Monad (replicateM) import Data.List     (foldl') import System.Random +import Data.Hashable+ import Data.Graph.DGraph import Data.Graph.Types import Data.Graph.UGraph --- | Generate a random Erdős–Rényi G(n, p) model graph of /n/ vertices with a--- | /p/ connection probability+-- | Generate a random Erdős–Rényi G(n, p) model graph erdosRenyi :: Graph g => Int -> Float -> IO (g Int ())-erdosRenyi n p = go [1..n] (probability p) empty+erdosRenyi n = rndGraph' (1, n)++-- | 'erdosRenyi' convinience 'UGraph' generation function+erdosRenyiU :: Int -> Float -> IO (UGraph Int ())+erdosRenyiU = erdosRenyi++-- | 'erdosRenyi' convinience 'DGraph' generation function+erdosRenyiD :: Int -> Float -> IO (DGraph Int ())+erdosRenyiD = erdosRenyi+++-- | Generate a random graph with vertices in /v/ across range of given bounds,+-- random edge attributes in /e/ within given bounds, and some existing+-- probability for each possible edge as per the Erdős–Rényi model+rndGraph :: forall g v e . (Graph g, Hashable v, Eq v, Enum v, Random e)+ => (v, v)+ -> (e, e)+ -> Float+ -> IO (g v e)+rndGraph (n1, n2) edgeBounds p = go [n1..n2] (probability p) empty     where-        go :: Graph g => [Int] -> Float -> g Int () -> IO (g Int ())+        go :: [v] -> Float -> g v e -> IO (g v e)         go [] _ g = return g         go (v:vs) pv g = do             rnds <- replicateM (length vs + 1) $ randomRIO (0.0, 1.0)             flipDir <- randomRIO (True, False)+            edgeAttr <- randomRIO edgeBounds             let vs' = zip rnds vs             let g' = insertVertex v g-            go vs pv $! foldl' (putV pv v flipDir) g' vs'+            go vs pv $! foldl' (insertFlippedEdge pv v edgeAttr flipDir) g' vs' -        putV :: Graph g => Float -> Int -> Bool -> g Int () -> (Float, Int) -> g Int ()-        putV pv v flipDir g (p', v')-            | p' < pv = insertEdgePair pair g-            | otherwise = g-                where pair = if flipDir then (v', v) else (v, v') -        probability :: Float -> Float-        probability v | v >= 1 = 1 | v <= 0 = 0 | otherwise = v+-- | Same as 'rndGraph' but uses attributeless edges+rndGraph' :: forall g v . (Graph g, Hashable v, Eq v, Enum v)+ => (v, v)+ -> Float+ -> IO (g v ())+rndGraph' (n1, n2) p = go [n1..n2] (probability p) empty+    where+        go :: [v] -> Float -> g v () -> IO (g v ())+        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 v g+            go vs pv $! foldl' (insertFlippedEdge pv v () flipDir) g' vs' --- | 'erdosRenyi' convinience 'UGraph' generation function-erdosRenyiU :: Int -> Float -> IO (UGraph Int ())-erdosRenyiU  = erdosRenyi --- | 'erdosRenyi' convinience 'DGraph' generation function-erdosRenyiD :: Int -> Float -> IO (DGraph Int ())-erdosRenyiD  = erdosRenyi---- | Generate a random square binary matrix+-- | Generate a random adjacency matrix -- | Useful for use with 'fromAdjacencyMatrix'-randomMat :: Int -> IO [[Int]]-randomMat n = replicateM n randRow+rndAdjacencyMatrix :: Int -> IO [[Int]]+rndAdjacencyMatrix n = replicateM n randRow     where randRow = replicateM n (randomRIO (0,1)) :: IO [Int]++-- | Insert and edge between vertices if the probability is met+insertFlippedEdge :: (Graph g, Hashable v, Eq v)+ => Float+ -> v+ -> e+ -> Bool+ -> g v e+ -> (Float, v)+ -> g v e+insertFlippedEdge pv v edgeAttr flipDir g (p', v')+    | p' < pv = insertEdgeTriple triple g+    | otherwise = g+        where triple = if flipDir then (v', v, edgeAttr) else (v, v', edgeAttr)++-- | Bound a real value as probability value [0.0, 1.0]+probability :: Float -> Float+probability v | v >= 1 = 1 | v <= 0 = 0 | otherwise = v