graphite 0.0.1.0 → 0.0.2.0

raw patch · 3 files changed

+76/−15 lines, 3 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/DGraph.hs +3/−3
• src/Data/Graph/Graph.hs +72/−11

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

@@ -15,12 +15,12 @@ newtype DGraph v e = DGraph { unDGraph :: HM.HashMap v (Links v e) }     deriving (Eq, Show) +-- | The Degree Sequence of a 'DGraph' is a list of pairs (Indegree, Outdegree)+type DegreeSequence = [(Int, Int)]+ instance (Arbitrary v, Arbitrary e, Hashable v, Num v, Ord v)  => Arbitrary (DGraph v e) where     arbitrary = insertArcs <$> arbitrary <*> pure empty---- | The Degree Sequence un a 'DGraph' is a list of pairs (Indegree, Outdegree)-type DegreeSequence = [(Int, Int)]  -- | The Empty (order-zero) 'DGraph' with no vertices and no arcs empty :: (Hashable v) => DGraph v e

@@ -5,8 +5,7 @@ module Data.Graph.Graph where  import Control.Monad (replicateM)-import Data.List     (foldl')-import Data.Maybe    (fromMaybe)+import Data.List     (foldl', reverse, sort) import System.Random  import           Data.Hashable@@ -23,10 +22,30 @@  => Arbitrary (Graph v e) where     arbitrary = insertEdges <$> arbitrary <*> pure empty --- | Generate a random 'Graph' of @n@ vertices-randomGraphIO :: Int -> IO (Graph Int ())-randomGraphIO n = replicateM n randRow-    >>= (\m -> return $ fromMaybe empty (fromAdjacencyMatrix m))+-- | Probability value between 0 and 1+newtype Probability = P Float deriving (Eq, Ord, Show)++-- | Construct a 'Probability' value+probability :: Float -> Probability+probability v | v >= 1 = P 1 | v <= 0 = P 0 | otherwise = P v++-- | Generate a random 'Graph' of the Erdős–Rényi G(n, p) model+erdosRenyiIO :: Int -> Probability -> IO (Graph Int ())+erdosRenyiIO n (P p) = go [1..n] p empty+    where+        go :: [Int] -> Float -> Graph Int () -> IO (Graph Int ())+        go [] _ g = return g+        go (v:vs) pv g = do+            rnds <- randomRs (0.0, 1.0) <$> newStdGen+            let vs' = zip rnds vs+            go vs pv $! (foldl' (putV pv v) g vs')++        putV :: Float -> Int -> Graph Int () -> (Float, Int) -> Graph Int ()+        putV pv v g (p', v') | p' < pv = insertEdge (v <-> v') g | otherwise = g+++randomMatIO :: Int -> IO [[Int]]+randomMatIO n = replicateM n randRow     where randRow = replicateM n (randomRIO (0,1)) :: IO [Int]  -- | The Empty (order-zero) 'Graph' with no vertices and no edges@@ -62,7 +81,7 @@ -- | @O(m*log n)@ Insert many directed 'Edge's into a 'Graph' -- | Same rules as 'insertEdge' are applied insertEdges :: (Hashable v, Eq v) => [Edge v e] -> Graph v e -> Graph v e-insertEdges as g = foldl' (flip insertEdge) g as+insertEdges es g = foldl' (flip insertEdge) g es  -- | @O(log n)@ Remove the undirected 'Edge' from a 'Graph' if present -- | The involved vertices are left untouched@@ -132,14 +151,18 @@     containsVertex graph v1 && containsVertex graph v2 && v2 `HM.member` v1Links     where v1Links = getLinks v1 g +-- | Retrieve the adjacent vertices of a vertex+adjacentVertices :: (Hashable v, Eq v) => Graph v e -> v -> [v]+adjacentVertices (Graph g) v = HM.keys $ getLinks v g+ -- | Retrieve the incident 'Edge's of a Vertex incidentEdges :: (Hashable v, Eq v) => Graph v e -> v -> [Edge v e]-incidentEdges g v = filter (\(Edge v1 v2 _) -> v == v1 || v == v2) $ edges g+incidentEdges (Graph g) v = fmap (uncurry (Edge v)) (HM.toList (getLinks v g))  -- | Degree of a vertex -- | The total number incident 'Edge's of a vertex vertexDegree :: (Hashable v, Eq v) => Graph v e -> v -> Int-vertexDegree g = length . incidentEdges g+vertexDegree (Graph g) v = length $ HM.keys $ getLinks v g  -- | Degrees of a all the vertices in a 'Graph' degrees :: (Hashable v, Eq v) => Graph v e -> [Int]@@ -161,7 +184,8 @@ -- | Tell if a 'Graph' is simple -- | A 'Graph' is @simple@ if it has no multiple edges nor loops isSimple :: (Hashable v, Eq v) => Graph v e -> Bool-isSimple = not . any isLoop . edges+isSimple g = foldl' go True $ vertices g+    where go bool v = bool && (not $ HM.member v $ getLinks v $ unGraph g)  -- | Tell if a 'Graph' is regular -- | An Undirected Graph is @regular@ when all of its vertices have the same@@ -169,12 +193,20 @@ isRegular :: Graph v e -> Bool isRegular = undefined +-- | Tell if two 'Graph's are isomorphic+areIsomorphic :: Graph v e -> Graph v' e' -> Bool+areIsomorphic = undefined++isomorphism :: Graph v e -> Graph v' e' -> (v -> v')+isomorphism = undefined++ -- | Generate a directed 'Graph' of Int vertices from an adjacency -- | square matrix fromAdjacencyMatrix :: [[Int]] -> Maybe (Graph Int ()) fromAdjacencyMatrix m     | length m /= length (head m) = Nothing-    | otherwise = Just $ insertEdges (foldl genEdges [] labeledM) empty+    | otherwise = Just $ insertEdges (foldl' genEdges [] labeledM) empty         where             labeledM :: [(Int, [(Int, Int)])]             labeledM = zip [1..] $ fmap (zip [1..]) m@@ -186,3 +218,32 @@ -- | Get the adjacency matrix representation of a directed 'Graph' toAdjacencyMatrix :: Graph v e -> [[Int]] toAdjacencyMatrix = undefined+++-- | The Degree Sequence of a simple 'Graph' is a list of degrees+newtype DegreeSequence = DegreeSequence { unDegreeSequence :: [Int]}+    deriving (Eq, Ord, Show)++-- | Construct a 'DegreeSequence' from a list of degrees+-- | Negative degree values are discarded+degreeSequence :: [Int] -> DegreeSequence+degreeSequence = DegreeSequence . reverse . sort . filter (>0)++-- | Get the 'DegreeSequence' of a simple 'Graph'+-- | If the graph is not @simple@ (see 'isSimple') the result is Nothing+getDegreeSequence :: (Hashable v, Eq v) => Graph v e -> Maybe DegreeSequence+getDegreeSequence g+    | (not . isSimple) g = Nothing+    | otherwise = Just $ degreeSequence $ degrees g++-- | Tell if a 'DegreeSequence' is a Graphical Sequence+-- | A Degree Sequence is a @Graphical Sequence@ if a corresponding 'Graph' for+-- | it exists+isGraphicalSequence :: DegreeSequence -> Bool+isGraphicalSequence = even . length . filter odd . unDegreeSequence++-- | Get the corresponding 'Graph' of a 'DegreeSequence'+-- | If the 'DegreeSequence' is not graphical (see 'isGraphicalSequence') the+-- | result is Nothing+fromGraphicalSequence :: DegreeSequence -> Maybe (Graph Int ())+fromGraphicalSequence = undefined