graphite 0.4.1.0 → 0.4.2.0

raw patch · 6 files changed

+48/−53 lines, 6 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 +16/−19
• src/Data/Graph/Generation.hs +9/−9
• src/Data/Graph/Types.hs +1/−1
• src/Data/Graph/UGraph/DegreeSequence.hs +6/−0
• src/Data/Graph/Visualize.hs +15/−23

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

@@ -53,7 +53,8 @@     removeEdgePair = removeArc'     removeEdgePairAndVertices = removeArcAndVertices' -    isSimple = undefined+    isSimple g = foldl' go True $ vertices g+        where go bool v = bool && (not $ HM.member v $ getLinks v $ unDGraph g)      fromAdjacencyMatrix m         | length m /= length (head m) = Nothing@@ -167,25 +168,25 @@  -- | Indegree of a vertex -- | The number of inbounding 'Arc's to a vertex-vertexIndegree :: DGraph v e -> v -> Int-vertexIndegree = undefined+vertexIndegree :: (Hashable v, Eq v) => DGraph v e -> v -> Int+vertexIndegree g v = length $ filter (\(_, v') -> v == v' ) $ arcs' g  -- | Outdegree of a vertex -- | The number of outbounding 'Arc's from a vertex-vertexOutdegree :: DGraph v e -> v -> Int-vertexOutdegree = undefined+vertexOutdegree :: (Hashable v, Eq v) => DGraph v e -> v -> Int+vertexOutdegree g v = length $ filter (\(v', _) -> v == v' ) $ arcs' g  -- | Indegrees of all the vertices in a 'DGraph'-indegrees :: DGraph v e -> [Int]-indegrees = undefined+indegrees :: (Hashable v, Eq v) => DGraph v e -> [Int]+indegrees g = fmap (vertexIndegree g) $ vertices g  -- | Outdegree of all the vertices in a 'DGraph'-outdegrees :: DGraph v e -> [Int]-outdegrees = undefined+outdegrees :: (Hashable v, Eq v) => DGraph v e -> [Int]+outdegrees g = fmap (vertexOutdegree g) $ vertices g  -- | Tell if a 'DGraph' is balanced -- | A Directed Graph is @balanced@ when its @indegree = outdegree@-isBalanced :: DGraph v e -> Bool+isBalanced :: (Hashable v, Eq v) => DGraph v e -> Bool isBalanced g = sum (indegrees g) == sum (outdegrees g)  -- | Tell if a 'DGraph' is regular@@ -197,19 +198,21 @@  -- | Tell if a vertex is a source -- | A vertex is a @source@ when its @indegree = 0@-isSource :: DGraph v e -> v -> Bool+isSource :: (Hashable v, Eq v) => DGraph v e -> v -> Bool isSource g v = vertexIndegree g v == 0  -- | Tell if a vertex is a sink -- | A vertex is a @sink@ when its @outdegree = 0@-isSink :: DGraph v e -> v -> Bool+isSink :: (Hashable v, Eq v) => DGraph v e -> v -> Bool isSink g v = vertexOutdegree g v == 0  -- | Tell if a vertex is internal -- | A vertex is a @internal@ when its neither a @source@ nor a @sink@-isInternal :: DGraph v e -> v -> Bool+isInternal :: (Hashable v, Eq v) => DGraph v e -> v -> Bool isInternal g v = not $ isSource g v || isSink g v +-- * Transformations+ -- | Get the transpose of a 'DGraph' -- | The @transpose@ of a directed graph is another directed graph where all of -- | its arcs are reversed@@ -222,12 +225,6 @@ toUndirected :: (Hashable v, Eq v) => DGraph v e -> UG.UGraph v e toUndirected g = UG.insertEdges empty (fmap arcToEdge $ arcs g)     where arcToEdge (Arc fromV toV attr) = Edge fromV toV attr---- | Tell if a 'DegreeSequence' is a Directed Graphic--- | A @Directed Graphic@ is a Degree Sequence for wich a 'DGraph' exists--- TODO: Kleitman–Wang | Fulkerson–Chen–Anstee theorem algorithms-isDirectedGraphic :: DegreeSequence -> Bool-isDirectedGraphic = undefined   -- * Lists

@@ -9,17 +9,17 @@ import Data.Graph.Types  -- | Probability value between 0 and 1-newtype Probability = P Float deriving (Eq, Ord, Show)+newtype Probability = P Double deriving (Eq, Ord, Show)  -- | Construct a 'Probability' value-probability :: Float -> Probability+probability :: Double -> 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+-- | Generate a random Erdős–Rényi  G(n, p) model graph+erdosRenyi :: Graph g => Int -> Probability -> IO (g Int ())+erdosRenyi n (P p) = go [1..n] p empty     where-        go :: Graph g => [Int] -> Float -> g Int () -> IO (g Int ())+        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)@@ -28,7 +28,7 @@             let g' = insertVertex g v             go vs pv $! (foldl' (putV pv v flipDir) g' vs') -        putV :: Graph g => Float -> Int -> Bool -> g Int () -> (Float, Int) -> g Int ()+        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@@ -36,6 +36,6 @@  -- | Generate a random square binary matrix -- | Useful for use with 'fromAdjacencyMatrix'-randomMatIO :: Int -> IO [[Int]]-randomMatIO n = replicateM n randRow+randomMat :: Int -> IO [[Int]]+randomMat n = replicateM n randRow     where randRow = replicateM n (randomRIO (0,1)) :: IO [Int]

@@ -102,7 +102,7 @@     removeEdgePairAndVertices :: (Hashable v, Eq v) => g v e -> (v, v) -> g v e      -- | Tell if a graph is simple-    -- | A graph is @simple@ if it has no multiple edges nor loops+    -- | A graph is @simple@ if it has no loops     isSimple :: (Hashable v, Eq v) => g v e -> Bool      -- | Generate a graph of Int vertices from an adjacency

@@ -36,6 +36,12 @@     | otherwise = isGraphicalSequence $ degreeSequence seq'         where seq' = (map (subtract 1) $ take x xs) ++ drop x xs +-- | Tell if a 'DegreeSequence' is a Directed Graphic+-- | A @Directed Graphic@ is a Degree Sequence for wich a 'DGraph' exists+-- TODO: Kleitman–Wang | Fulkerson–Chen–Anstee theorem algorithms+isDirectedGraphic :: DegreeSequence -> Bool+isDirectedGraphic = undefined+ -- | Tell if a 'DegreeSequence' holds the Handshaking lemma, that is, if the -- | number of vertices with odd degree is even holdsHandshakingLemma :: DegreeSequence -> Bool

@@ -1,41 +1,33 @@ module Data.Graph.Visualize-    ( plotUndirectedIO-    , plotUndirectedXdgIO+    ( plotUGraph+    , plotUGraphPng -    , plotDirectedIO-    , plotDirectedXdgIO+    , plotDGraph+    , plotDGraphPng     ) where  import Data.GraphViz import Data.Hashable-import Data.Monoid    ((<>))-import System.Process  import Data.Graph.DGraph import Data.Graph.Types import Data.Graph.UGraph +-- | Plot an undirected 'UGraph'+plotUGraph :: (Show e) => UGraph Int e -> IO ()+plotUGraph g = runGraphvizCanvas Sfdp (toUndirectedDot g) Xlib+ -- | Plot an undirected 'UGraph' to a PNG image file-plotUndirectedIO :: (Show e) => UGraph Int e -> FilePath -> IO FilePath-plotUndirectedIO g fp = addExtension (runGraphvizCommand Sfdp $ toUndirectedDot g) Png fp+plotUGraphPng :: (Show e) => UGraph Int e -> FilePath -> IO FilePath+plotUGraphPng g fp = addExtension (runGraphvizCommand Sfdp $ toUndirectedDot g) Png fp --- | Same as 'plotUndirectedIO' but open the resulting image with /xdg-open/-plotUndirectedXdgIO :: (Show e) => UGraph Int e -> FilePath -> IO ()-plotUndirectedXdgIO g fp = do-    fp' <- plotUndirectedIO g fp-    _ <- system $ "xdg-open " <> fp'-    return ()+-- | Plot a directed 'DGraph'+plotDGraph :: (Show e) => DGraph Int e -> IO ()+plotDGraph g = runGraphvizCanvas Sfdp (toDirectedDot g) Xlib  -- | Plot a directed 'DGraph' to a PNG image file-plotDirectedIO :: (Show e) => DGraph Int e -> FilePath -> IO FilePath-plotDirectedIO g fp = addExtension (runGraphvizCommand Sfdp $ toDirectedDot g) Png fp---- | Same as 'plotDirectedIO' but open the resulting image with /xdg-open/-plotDirectedXdgIO :: (Show e) => DGraph Int e -> FilePath -> IO ()-plotDirectedXdgIO g fp = do-    fp' <- plotDirectedIO g fp-    _ <- system $ "xdg-open " <> fp'-    return ()+plotDGraphPng :: (Show e) => DGraph Int e -> FilePath -> IO FilePath+plotDGraphPng g fp = addExtension (runGraphvizCommand Sfdp $ toDirectedDot g) Png fp  labeledNodes :: (Graph g, Show v) => g v e -> [(v, String)] labeledNodes g = fmap (\v -> (v, show v)) $ vertices g