graphite 0.4.0.0 → 0.4.1.0

raw patch · 8 files changed

+172/−47 lines, 8 filesdep +bytestringdep +cassavadep +vectorPVP: major bump suggested

API removals or changes: PVP suggests a major version bump

Dependencies added: bytestring, cassava, vector

API changes (from Hackage documentation)

Files

• README.md +14/−1
• graphite.cabal +9/−3
• src/Data/Graph/DGraph.hs +24/−2
• src/Data/Graph/Morphisms.hs +24/−0
• src/Data/Graph/Read.hs +32/−0
• src/Data/Graph/Types.hs +0/−5
• src/Data/Graph/UGraph.hs +21/−36
• src/Data/Graph/UGraph/DegreeSequence.hs +48/−0

@@ -1,3 +1,16 @@+![Graphite Logo](./logo/logo.png)++[![](https://img.shields.io/hackage/v/graphite.svg)](https://hackage.haskell.org/package/graphite)+![Hackage-Deps](https://img.shields.io/hackage-deps/v/graphite.svg)+ # graphite -An experimental Haskell graph library+Represent, analyze and visualize graphs & networks.+++# Current state++Most of what you'll find here are *undefined* functions, sort of like a wish+list to be eventually fulfilled.++The basic graph types `UGraph` and `DGraph` could already be used if desired.

@@ -1,5 +1,5 @@ name:                graphite-version:             0.4.0.0+version:             0.4.1.0 synopsis:            Graphs and networks library description:         Represent, analyze and visualize graphs homepage:            https://github.com/alx741/graphite#readme@@ -16,19 +16,25 @@ library   hs-source-dirs:      src   exposed-modules:     Data.Graph.Types-                     , Data.Graph.UGraph+                     , Data.Graph.Connectivity                      , Data.Graph.DGraph                      , Data.Graph.Generation+                     , Data.Graph.Morphisms+                     , Data.Graph.Read+                     , Data.Graph.UGraph+                     , Data.Graph.UGraph.DegreeSequence                      , Data.Graph.Visualize-                     , Data.Graph.Connectivity   build-depends:       base >= 4.7 && < 5                      , hashable+                     , vector                      , containers                      , unordered-containers+                     , bytestring                      , random                      , process                      , graphviz                      , QuickCheck+                     , cassava   ghc-options:         -Wall   default-language:    Haskell2010 

@@ -8,14 +8,25 @@ import           Data.Hashable import qualified Data.HashMap.Lazy as HM import           Test.QuickCheck+import           Text.Read  import           Data.Graph.Types import qualified Data.Graph.UGraph as UG  -- | Directed Graph of Vertices in /v/ and Arcs with attributes in /e/ newtype DGraph v e = DGraph { unDGraph :: HM.HashMap v (Links v e) }-    deriving (Eq, Show)+    deriving (Eq) +instance (Hashable v, Eq v, Show v, Show e) => Show (DGraph v e) where+    showsPrec d m = showParen (d > 10) $+        showString "fromList " . shows (toList m)++instance (Hashable v, Eq v, Read v, Read e) => Read (DGraph v e) where+    readPrec = parens $ prec 10 $ do+        Ident "fromList" <- lexP+        xs <- readPrec+        return (fromList xs)+ instance Graph DGraph where     empty = DGraph HM.empty     order (DGraph g) = HM.size g@@ -43,7 +54,6 @@     removeEdgePairAndVertices = removeArcAndVertices'      isSimple = undefined-    isRegular = undefined      fromAdjacencyMatrix m         | length m /= length (head m) = Nothing@@ -218,3 +228,15 @@ -- TODO: Kleitman–Wang | Fulkerson–Chen–Anstee theorem algorithms isDirectedGraphic :: DegreeSequence -> Bool isDirectedGraphic = undefined+++-- * Lists++-- | Convert a 'DGraph' to a list of 'Arc's+-- | Same as 'arcs'+toList :: (Hashable v, Eq v) => DGraph v e -> [Arc v e]+toList = arcs++-- | Construct a 'DGraph' from a list of 'Arc's+fromList :: (Hashable v, Eq v) => [Arc v e] -> DGraph v e+fromList = insertArcs empty

@@ -0,0 +1,24 @@+module Data.Graph.Morphisms where++import Data.Graph.DGraph+import Data.Graph.Types+import Data.Graph.UGraph++-- | Tell if two graphs are isomorphic+-- TODO: check first: same number of vertices, same number of edges+areIsomorphic :: Graph g => g v e -> g v' e' -> Bool+areIsomorphic = undefined++isomorphism :: Graph g => g v e -> g v' e' -> (v -> v')+isomorphism = undefined++-- | Tell if a 'UGraph' is regular+-- | An undirected graph is @regular@ if each vertex has the same degree+isURegular :: UGraph v e -> Bool+isURegular = undefined++-- | Tell if a 'DGraph' is regular+-- | A directed graph is @regular@ if each vertex has the same indigree and |+-- | outdegree+isDRegular :: DGraph v e -> Bool+isDRegular = undefined

@@ -0,0 +1,32 @@+{-# LANGUAGE ScopedTypeVariables #-}++module Data.Graph.Read where++import Data.ByteString.Lazy as BS+import Data.Csv             as CSV+import Data.Hashable+import Data.Vector          as V hiding (fromList)++import Data.Graph.Types+import Data.Graph.UGraph++-- | Read a 'UGraph' from a CSV file+-- | The line "1,2,3,4" translates to the list of edges+-- | "(1 <-> 2), (1 <-> 3), (1 <-> 4)"+csvToUGraph :: (Hashable v, Eq v, FromField v)+    => FilePath+    -> IO (Either String (UGraph v ()))+csvToUGraph fp = do+    content <- BS.readFile fp+    let dec = decode NoHeader content+    case dec of+        Left err  -> return $ Left err+        Right vec -> return $ Right $ fromList $ toEdges $ V.toList vec++    where+        toEdges :: [[v]] -> [Edge v ()]+        toEdges ns = Prelude.concat $ fmap nodeEdges ns++        nodeEdges :: [v] -> [Edge v ()]+        nodeEdges []     = []+        nodeEdges (n:ns) = fmap (\n' -> Edge n n' ()) ns

@@ -105,11 +105,6 @@     -- | A graph is @simple@ if it has no multiple edges nor loops     isSimple :: (Hashable v, Eq v) => g v e -> Bool -    -- | Tell if a graph is regular-    -- | A graph is @regular@ when all of its vertices have the same-    -- | number of adjacent vertices-    isRegular :: g v e -> Bool-     -- | Generate a graph of Int vertices from an adjacency     -- | square matrix     fromAdjacencyMatrix :: [[Int]] -> Maybe (g Int ())

@@ -4,18 +4,29 @@  module Data.Graph.UGraph where -import Data.List (foldl', reverse, sort)+import Data.List (foldl')  import           Data.Hashable import qualified Data.HashMap.Lazy as HM import           Test.QuickCheck+import           Text.Read  import Data.Graph.Types  -- | Undirected Graph of Vertices in /v/ and Edges with attributes in /e/ newtype UGraph v e = UGraph { unUGraph :: HM.HashMap v (Links v e) }-    deriving (Eq, Show)+    deriving (Eq) +instance (Hashable v, Eq v, Show v, Show e) => Show (UGraph v e) where+    showsPrec d m = showParen (d > 10) $+        showString "fromList " . shows (toList m)++instance (Hashable v, Eq v, Read v, Read e) => Read (UGraph v e) where+    readPrec = parens $ prec 10 $ do+        Ident "fromList" <- lexP+        xs <- readPrec+        return (fromList xs)+ instance (Arbitrary v, Arbitrary e, Hashable v, Num v, Ord v)  => Arbitrary (UGraph v e) where     arbitrary = insertEdges <$> pure empty <*> arbitrary@@ -43,8 +54,6 @@     isSimple g = foldl' go True $ vertices g         where go bool v = bool && (not $ HM.member v $ getLinks v $ unUGraph g) -    isRegular = undefined-     fromAdjacencyMatrix m         | length m /= length (head m) = Nothing         | otherwise = Just $ insertEdges empty (foldl' genEdges [] labeledM)@@ -130,38 +139,14 @@ 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-areIsomorphic :: UGraph v e -> UGraph v' e' -> Bool-areIsomorphic = undefined -isomorphism :: UGraph v e -> UGraph v' e' -> (v -> v')-isomorphism = undefined----- | The Degree Sequence of a simple 'UGraph' 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 '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-    | (not . isSimple) g = Nothing-    | otherwise = Just $ degreeSequence $ degrees g+-- * Lists --- | Tell if a 'DegreeSequence' is a Graphical Sequence--- | A Degree Sequence is a @Graphical Sequence@ if a corresponding 'UGraph' for--- | it exists-isGraphicalSequence :: DegreeSequence -> Bool-isGraphicalSequence = even . length . filter odd . unDegreeSequence+-- | Convert a 'UGraph' to a list of 'Edge's+-- | Same as 'edges'+toList :: (Hashable v, Eq v) => UGraph v e -> [Edge v e]+toList = edges --- | Get the corresponding 'UGraph' of a 'DegreeSequence'--- | If the 'DegreeSequence' is not graphical (see 'isGraphicalSequence') the--- | result is Nothing-fromGraphicalSequence :: DegreeSequence -> Maybe (UGraph Int ())-fromGraphicalSequence = undefined+-- | Construct a 'UGraph' from a list of 'Edge's+fromList :: (Hashable v, Eq v) => [Edge v e] -> UGraph v e+fromList = insertEdges empty

@@ -0,0 +1,48 @@+module Data.Graph.UGraph.DegreeSequence where++import Data.List (reverse, sort)++import Data.Hashable++import Data.Graph.Types+import Data.Graph.UGraph++-- | The Degree Sequence of a simple 'UGraph' is a list of degrees of vertices+-- | in a graph+-- | Use 'degreeSequence' to construct a valid Degree Sequence+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 '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+    | (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 'UGraph' for+-- | it exists.+-- | Use the Havel-Hakimi algorithm+isGraphicalSequence :: DegreeSequence -> Bool+isGraphicalSequence (DegreeSequence []) = True+isGraphicalSequence (DegreeSequence (x:xs))+    | x > length xs = False+    | otherwise = isGraphicalSequence $ degreeSequence seq'+        where seq' = (map (subtract 1) $ take x xs) ++ drop x xs++-- | Tell if a 'DegreeSequence' holds the Handshaking lemma, that is, if the+-- | number of vertices with odd degree is even+holdsHandshakingLemma :: DegreeSequence -> Bool+holdsHandshakingLemma = even . length . filter odd . unDegreeSequence++-- | Get the corresponding 'UGraph' of a 'DegreeSequence'+-- | If the 'DegreeSequence' is not graphical (see 'isGraphicalSequence') the+-- | result is Nothing+fromGraphicalSequence :: DegreeSequence -> Maybe (UGraph Int ())+fromGraphicalSequence = undefined