graphite 0.2.0.0 → 0.2.1.0

raw patch · 7 files changed

+88/−54 lines, 7 filesPVP: major bump suggested

API removals or changes: PVP suggests a major version bump

API changes (from Hackage documentation)

Files

• graphite.cabal +2/−1
• src/Data/Graph/Connectivity.hs +6/−6
• src/Data/Graph/DGraph.hs +0/−1
• src/Data/Graph/Generation.hs +36/−0
• src/Data/Graph/Types.hs +28/−1
• src/Data/Graph/UGraph.hs +15/−44
• src/Data/Graph/Visualize.hs +1/−1

@@ -1,5 +1,5 @@ name:                graphite-version:             0.2.0.0+version:             0.2.1.0 synopsis:            Graphs and networks library description:         Represent, analyze and visualize graphs homepage:            https://github.com/alx741/graphite#readme@@ -18,6 +18,7 @@   exposed-modules:     Data.Graph.Types                      , Data.Graph.UGraph                      , Data.Graph.DGraph+                     , Data.Graph.Generation                      , Data.Graph.Visualize                      , Data.Graph.Connectivity   build-depends:       base >= 4.7 && < 5

@@ -1,35 +1,35 @@ -- | For Connectivity analisis purposes a 'DGraph' can be converted into a--- | 'UGraph using 'toUndirected'+-- | 'UGraph' using 'toUndirected'  module Data.Graph.Connectivity where  import Data.Graph.UGraph import Data.Graph.DGraph --- | Tell if a 'UGraph is connected+-- | Tell if a 'UGraph' is connected -- | An Undirected Graph is @connected@ when there is a path between every pair -- | of vertices isConnected :: UGraph v e -> Bool isConnected = undefined --- | Tell if a 'UGraph is disconnected+-- | Tell if a 'UGraph' is disconnected -- | An Undirected Graph is @disconnected@ when its not @connected@. See -- | 'isConnected' -- TODO: An edgeles graph with two or more vertices is disconnected isDisconnected :: UGraph v e -> Bool isDisconnected = not . isConnected --- | Tell if two vertices of a 'UGraph are connected+-- | Tell if two vertices of a 'UGraph' are connected -- | Two vertices are @connected@ if it exists a path between them areConnected :: UGraph v e -> v -> v -> Bool areConnected = undefined --- | Tell if two vertices of a 'UGraph are disconnected+-- | Tell if two vertices of a 'UGraph' are disconnected -- | Two vertices are @disconnected@ if it doesn't exist a path between them areDisconnected :: UGraph v e -> v -> v -> Bool areDisconnected = undefined --- | Retrieve all the unreachable vertices of a 'UGraph+-- | Retrieve all the unreachable vertices of a 'UGraph' -- | The @unreachable vertices@ are those with no adjacent 'Edge's unreachableVertices :: UGraph v e -> [v] unreachableVertices = undefined

@@ -18,7 +18,6 @@ instance Graph DGraph where     empty = DGraph HM.empty     order (DGraph g) = HM.size g-    size = length . arcs     vertices (DGraph g) = HM.keys g     edgePairs = arcs' 

@@ -0,0 +1,36 @@+{-# LANGUAGE ScopedTypeVariables #-}++module Data.Graph.Generation where++import Control.Monad (replicateM)+import Data.List     (foldl')+import System.Random++import Data.Graph.Types++-- | 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 Erdős–Rényi G(n, p) model graph+erdosRenyiIO :: Graph g => Int -> Probability -> IO (g Int ())+erdosRenyiIO n (P p) = go [1..n] p empty+    where+        go :: Graph g => [Int] -> Float -> g Int () -> IO (g 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 :: Graph g => Float -> Int -> g Int () -> (Float, Int) -> g Int ()+        putV pv v g (p', v') | p' < pv = insertEdgePair (v, v') g | otherwise = g++-- | Generate a random square binary matrix+-- | Useful for use with 'fromAdjacencyMatrix'+randomMatIO :: Int -> IO [[Int]]+randomMatIO n = replicateM n randRow+    where randRow = replicateM n (randomRIO (0,1)) :: IO [Int]

@@ -21,11 +21,12 @@     -- | Retrieve the size of a graph     -- | The @size@ of a graph is its number of edges     size :: (Hashable v, Eq v) => g v e -> Int+    size = length . edgePairs      -- | Retrieve the vertices of a graph     vertices :: g v e -> [v] -    -- | Retrieve the edges of a graph as pairs+    -- | Retrieve the edges of a graph     edgePairs :: (Hashable v, Eq v) => g v e -> [(v, v)]      -- | Tell if a vertex exists in the graph@@ -49,6 +50,19 @@     minDegree :: (Hashable v, Eq v) => g v e -> Int     minDegree = minimum . degrees +    -- | Average degree of a graph+    avgDegree :: (Hashable v, Eq v) => g v e -> Double+    avgDegree g = fromIntegral (2 * size g) / (fromIntegral $ order g)++    -- | Density of a graph+    -- | The ratio of the number of existing edges in the graph to the number of+    -- | posible edges+    density :: (Hashable v, Eq v) => g v e -> Double+    density g = (2 * (e - n + 1)) / (n * (n - 3) + 2)+        where+            n = fromIntegral $ order g+            e = fromIntegral $ size g+     -- | Insert a vertex into a graph     -- | If the graph already contains the vertex leave the graph untouched     insertVertex :: (Hashable v, Eq v) => v -> g v e -> g v e@@ -58,10 +72,23 @@     -- | untouched     insertVertices :: (Hashable v, Eq v) => [v] -> g v e -> g v e +    -- | Tell if an edge exists in the graph     containsEdgePair :: (Hashable v, Eq v) => g v e -> (v, v) -> Bool++    -- | Retrieve the incident edges of a vertex     incidentEdgePairs :: (Hashable v, Eq v) => g v e -> v -> [(v, v)]++    -- | Insert an edge into a graph+    -- | The involved vertices are inserted if don't exist. If the graph already+    -- | contains the edge, its attribute is updated     insertEdgePair :: (Hashable v, Eq v) => (v, v) -> g v () -> g v ()++    -- | Remove the edge from a graph present+    -- | The involved vertices are left untouched     removeEdgePair :: (Hashable v, Eq v) => (v, v) -> g v e -> g v e++    -- | Remove the edge from a graph if present+    -- | The involved vertices are also removed     removeEdgePairAndVertices :: (Hashable v, Eq v) => (v, v) -> g v e -> g v e      -- | Tell if a graph is simple

@@ -4,9 +4,7 @@  module Data.Graph.UGraph where -import Control.Monad (replicateM) import Data.List     (foldl', reverse, sort)-import System.Random  import           Data.Hashable import qualified Data.HashMap.Lazy as HM@@ -18,10 +16,13 @@ newtype UGraph v e = UGraph { unUGraph :: HM.HashMap v (Links v e) }     deriving (Eq, Show) +instance (Arbitrary v, Arbitrary e, Hashable v, Num v, Ord v)+ => Arbitrary (UGraph v e) where+    arbitrary = insertEdges <$> arbitrary <*> pure empty+ instance Graph UGraph where     empty = UGraph HM.empty     order (UGraph g) = HM.size g-    size = length . edges     vertices (UGraph g) = HM.keys g     edgePairs g = toPair <$> edges g @@ -57,44 +58,14 @@   -instance (Arbitrary v, Arbitrary e, Hashable v, Num v, Ord v)- => Arbitrary (UGraph v e) where-    arbitrary = insertEdges <$> arbitrary <*> pure empty---- | 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 'UGraph of the Erdős–Rényi G(n, p) model-erdosRenyiIO :: Int -> Probability -> IO (UGraph Int ())-erdosRenyiIO n (P p) = go [1..n] p empty-    where-        go :: [Int] -> Float -> UGraph Int () -> IO (UGraph 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 -> UGraph Int () -> (Float, Int) -> UGraph 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]---- | @O(n)@ Remove a vertex from a 'UGraph if present+-- | @O(n)@ Remove a vertex from a 'UGraph' if present -- | Every 'Edge' incident to this vertex is also removed removeVertex :: (Hashable v, Eq v) => v -> UGraph v e -> UGraph v e removeVertex v g = UGraph     $ (\(UGraph g') -> HM.delete v g')     $ foldl' (flip removeEdge) g $ incidentEdges g v --- | @O(log n)@ Insert an undirected 'Edge' into a 'UGraph+-- | @O(log n)@ Insert an undirected 'Edge' into a 'UGraph' -- | The involved vertices are inserted if don't exist. If the graph already -- | contains the Edge, its attribute is updated insertEdge :: (Hashable v, Eq v) => Edge v e -> UGraph v e -> UGraph v e@@ -103,12 +74,12 @@         g' = unUGraph $ insertVertices [v1, v2] g         link fromV toV = HM.adjust (insertLink toV edgeAttr) fromV --- | @O(m*log n)@ Insert many directed 'Edge's into a 'UGraph+-- | @O(m*log n)@ Insert many directed 'Edge's into a 'UGraph' -- | Same rules as 'insertEdge' are applied insertEdges :: (Hashable v, Eq v) => [Edge v e] -> UGraph v e -> UGraph v e insertEdges es g = foldl' (flip insertEdge) g es --- | @O(log n)@ Remove the undirected 'Edge' from a 'UGraph if present+-- | @O(log n)@ Remove the undirected 'Edge' from a 'UGraph' if present -- | The involved vertices are left untouched removeEdge :: (Hashable v, Eq v) => Edge v e -> UGraph v e -> UGraph v e removeEdge = removeEdgePair . toPair@@ -124,7 +95,7 @@         v2Links = HM.delete v1 $ getLinks v2 g         update = HM.adjust . const --- | @O(log n)@ Remove the undirected 'Edge' from a 'UGraph if present+-- | @O(log n)@ Remove the undirected 'Edge' from a 'UGraph' if present -- | The involved vertices are also removed removeEdgeAndVertices :: (Hashable v, Eq v) => Edge v e -> UGraph v e -> UGraph v e removeEdgeAndVertices = removeEdgePairAndVertices . toPair@@ -134,7 +105,7 @@ removeEdgeAndVertices' (v1, v2) g =     removeVertex v2 $ removeVertex v1 $ removeEdgePair (v1, v2) g --- | @O(n*m)@ Retrieve the 'Edge's of a 'UGraph+-- | @O(n*m)@ Retrieve the 'Edge's of a 'UGraph' edges :: forall v e . (Hashable v, Eq v) => UGraph v e -> [Edge v e] edges (UGraph g) = linksToEdges $ zip vs links     where@@ -157,7 +128,7 @@ incidentEdges :: (Hashable v, Eq v) => UGraph v e -> v -> [Edge v e] incidentEdges (UGraph g) v = fmap (uncurry (Edge v)) (HM.toList (getLinks v g)) --- | Tell if two 'UGraph are isomorphic+-- | Tell if two 'UGraph' are isomorphic areIsomorphic :: UGraph v e -> UGraph v' e' -> Bool areIsomorphic = undefined @@ -165,7 +136,7 @@ isomorphism = undefined  --- | The Degree Sequence of a simple 'UGraph is a list of degrees+-- | The Degree Sequence of a simple 'UGraph' is a list of degrees newtype DegreeSequence = DegreeSequence { unDegreeSequence :: [Int]}     deriving (Eq, Ord, Show) @@ -174,7 +145,7 @@ degreeSequence :: [Int] -> DegreeSequence degreeSequence = DegreeSequence . reverse . sort . filter (>0) --- | Get the 'DegreeSequence' of a simple 'UGraph+-- | Get the 'DegreeSequence' of a simple 'UGraph' -- | If the graph is not @simple@ (see 'isSimple') the result is Nothing getDegreeSequence :: (Hashable v, Eq v) => UGraph v e -> Maybe DegreeSequence getDegreeSequence g@@ -182,12 +153,12 @@     | otherwise = Just $ degreeSequence $ degrees g  -- | Tell if a 'DegreeSequence' is a Graphical Sequence--- | A Degree Sequence is a @Graphical Sequence@ if a corresponding 'UGraph for+-- | A Degree Sequence is a @Graphical Sequence@ if a corresponding 'UGraph' for -- | it exists isGraphicalSequence :: DegreeSequence -> Bool isGraphicalSequence = even . length . filter odd . unDegreeSequence --- | Get the corresponding 'UGraph of a 'DegreeSequence'+-- | Get the corresponding 'UGraph' of a 'DegreeSequence' -- | If the 'DegreeSequence' is not graphical (see 'isGraphicalSequence') the -- | result is Nothing fromGraphicalSequence :: DegreeSequence -> Maybe (UGraph Int ())

@@ -12,7 +12,7 @@ import qualified Data.Graph.UGraph as G import           Data.Graph.Types --- | Plot an undirected 'UGraph to a PNG image file+-- | Plot an undirected 'UGraph' to a PNG image file plotIO :: (Show e) => G.UGraph Int e -> FilePath -> IO FilePath plotIO g fp = addExtension (runGraphvizCommand Sfdp $ toDot' g) Png fp