graphite 0.9.5.0 → 0.9.5.1

raw patch · 10 files changed

+312/−170 lines, 10 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/Connectivity.hs +40/−34
• src/Data/Graph/DGraph.hs +89/−38
• src/Data/Graph/Generation.hs +10/−3
• src/Data/Graph/Morphisms.hs +5/−3
• src/Data/Graph/Read.hs +16/−4
• src/Data/Graph/Types.hs +69/−44
• src/Data/Graph/UGraph.hs +34/−14
• src/Data/Graph/UGraph/DegreeSequence.hs +33/−16
• src/Data/Graph/Visualize.hs +15/−13

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

@@ -1,4 +1,4 @@--- | For Connectivity analisis purposes a 'DGraph' can be converted into a+-- | For Connectivity analysis purposes a 'DGraph' can be converted into a -- | 'UGraph' using 'toUndirected'  {-# LANGUAGE ScopedTypeVariables #-}@@ -15,8 +15,9 @@ import Data.Graph.UGraph  -- | Tell if two vertices of a graph are connected--- | Two vertices are @connected@ if it exists a path between them--- | The order of the vertices is relevant when the graph is directed+--+-- Two vertices are @connected@ if it exists a path between them. The order of+-- the vertices is relevant when the graph is directed areConnected :: forall g v e . (Graph g, Hashable v, Eq v, Ord v)  => g v e  -> v@@ -36,22 +37,23 @@                 || search vs banned' v'             where banned' = v `S.insert` banned --- | Tell if two vertices of a 'UGraph' are disconnected--- | Two vertices are @disconnected@ if it doesn't exist a path between them+-- | Opposite of 'areConnected' areDisconnected :: (Graph g, Hashable v, Eq v, Ord v) => g v e -> v -> v -> Bool areDisconnected g fromV toV = not $ areConnected g fromV toV  -- | Tell if a vertex is isolated--- | A vertex is @isolated@ if it has no incidet edges, that is, it has a degree--- | of zero+--+-- A vertex is @isolated@ if it has no incident edges, that is, it has a degree+-- of zero isIsolated :: (Graph g, Hashable v, Eq v) => g v e -> v -> Bool isIsolated g v = vertexDegree g v == 0  -- | Tell if a graph is connected--- | An Undirected Graph is @connected@ when there is a path between every pair--- | of vertices-isConnected :: (Graph g, Hashable v, Eq v, Ord v) => g v e -> Bool+--+-- An undirected graph is @connected@ when there is a path between every pair+-- of vertices -- FIXME: Use a O(n) algorithm+isConnected :: (Graph g, Hashable v, Eq v, Ord v) => g v e -> Bool isConnected g = go vs True     where         vs = vertices g@@ -61,45 +63,49 @@             go vs' $ foldl' (\b v -> b && areConnected g v v') bool vs  -- | Tell if a graph is bridgeless--- | A graph is @bridgeless@ if it has no edges that, when removed, split the--- | graph in two isolated components-isBridgeless :: (Hashable v, Eq v, Ord v) => UGraph v e -> Bool+--+-- A graph is @bridgeless@ if it has no edges that, when removed, split the+-- graph in two isolated components -- FIXME: Use a O(n) algorithm+isBridgeless :: (Hashable v, Eq v, Ord v) => UGraph v e -> Bool isBridgeless g =     foldl' (\b vs -> b && isConnected (removeEdgePair vs g)) True (edgePairs g) --- | Tell if a 'UGraph' is orietable--- | An undirected graph is @orietable@ if it can be converted into a directed--- | graph that is @strongly connected@ (See 'isStronglyConnected')+-- | Tell if a 'UGraph' is orientable+--+-- An undirected graph is @orientable@ if it can be converted into a directed+-- graph that is @strongly connected@ (See 'isStronglyConnected') isOrientable :: (Hashable v, Eq v, Ord v) => UGraph v e -> Bool isOrientable g = isConnected g && isBridgeless g  -- | Tell if a 'DGraph' is weakly connected--- | A Directed Graph is @weakly connected@ if the underlying undirected graph--- | is @connected@+--+-- A directed graph is @weakly connected@ if the underlying undirected graph+-- is @connected@ isWeaklyConnected :: (Hashable v, Eq v, Ord v) => DGraph v e -> Bool isWeaklyConnected = isConnected . toUndirected  -- | Tell if a 'DGraph' is strongly connected--- | A Directed Graph is @strongly connected@ if it contains a directed path--- | on every pair of vertices+--+-- A directed graph is @strongly connected@ if it contains a directed path+-- on every pair of vertices isStronglyConnected :: (Hashable v, Eq v, Ord v) => DGraph v e -> Bool isStronglyConnected = isConnected  -- TODO--- * connected component--- * strong components--- * vertex cut--- * vertex connectivity---     * biconnectivity---     * triconnectivity---     * separable--- * bridge--- * edge-connectivity--- * maximally connected--- * maximally edge-connected--- * super-connectivity--- * hyper-connectivity--- * Menger's theorem+-- connected component+-- strong components+-- vertex cut+-- vertex connectivity+--   biconnectivity+--   triconnectivity+--   separable+-- bridge+-- edge-connectivity+-- maximally connected+-- maximally edge-connected+-- super-connectivity+-- hyper-connectivity+-- Menger's theorem  -- Robin's Theorem: a graph is orientable if it is connected and has no bridges

@@ -2,8 +2,46 @@ {-# LANGUAGE DeriveGeneric       #-} {-# LANGUAGE ScopedTypeVariables #-} -module Data.Graph.DGraph where+module Data.Graph.DGraph+    (+    -- * DGraph data type+    DGraph +    -- * Functions on DGraph+    , insertArc+    , insertArcs+    , removeArc+    , removeArcs+    , removeArcAndVertices+    , arcs+    , containsArc+    , inboundingArcs+    , outboundingArcs+    , incidentArcs+    , vertexIndegree+    , vertexOutdegree+    , indegrees+    , outdegrees+    -- ** Query graph properties and characteristics+    , isSymmetric+    , isOriented+    , isBalanced+    , isRegular+    , isSource+    , isSink+    , isInternal+    -- ** Transformations+    , transpose+    , toUndirected++    -- * List conversions+    , toArcsList+    , fromArcsList++    -- * Pretty printing+    , prettyPrint+    ) where+ import Data.List      (foldl', intersect) import Data.Semigroup import GHC.Generics   (Generic)@@ -139,8 +177,9 @@     arbitrary = insertArcs <$> arbitrary <*> pure empty  -- | Insert a directed 'Arc' into a 'DGraph'--- | The involved vertices are inserted if they don't exist. If the graph--- | already contains the Arc, its attribute is updated+--+-- The involved vertices are inserted if they don't exist. If the graph+-- already contains the Arc, its attribute gets updated insertArc :: (Hashable v, Eq v) => Arc v e -> DGraph v e -> DGraph v e insertArc (Arc fromV toV edgeAttr) g@(DGraph s _)     | containsEdgePair g (fromV, toV) = g@@ -151,8 +190,8 @@ insertArcs :: (Hashable v, Eq v) => [Arc v e] -> DGraph v e -> DGraph v e insertArcs as g = foldl' (flip insertArc) g as --- | Remove the directed 'Arc' from a 'DGraph' if present--- | The involved vertices are left untouched+-- | Remove the directed 'Arc' from a 'DGraph' if present. The involved vertices+-- are left untouched removeArc :: (Hashable v, Eq v) => Arc v e -> DGraph v e -> DGraph v e removeArc = removeEdgePair . toPair @@ -160,8 +199,8 @@ removeArcs :: (Hashable v, Eq v) => [Arc v e] -> DGraph v e -> DGraph v e removeArcs as g = foldl' (flip removeArc) g as --- | Remove the directed 'Arc' from a 'DGraph' if present--- | The involved vertices are also removed+-- | Remove the directed 'Arc' from a 'DGraph' if present. The involved vertices+-- also get removed removeArcAndVertices :: (Hashable v, Eq v) => Arc v e -> DGraph v e -> DGraph v e removeArcAndVertices = removeEdgePairAndVertices . toPair @@ -187,28 +226,21 @@ outboundingArcs g v = filter (\(Arc fromV _ _) -> v == fromV) $ arcs g  -- | Retrieve the incident 'Arc's of a Vertex--- | Both inbounding and outbounding arcs+--+-- The @incident@ arcs of a vertex are all the inbounding and outbounding arcs+-- of the vertex incidentArcs :: (Hashable v, Eq v) => DGraph v e -> v -> [Arc v e] incidentArcs g v = inboundingArcs g v ++ outboundingArcs g v --- | Tell if a 'DGraph' is symmetric--- | All of its 'Arc's are bidirected-isSymmetric :: DGraph v e -> Bool-isSymmetric = undefined---- | Tell if a 'DGraph' is oriented--- | There are none bidirected 'Arc's--- | Note: This is /not/ the opposite of 'isSymmetric'-isOriented :: DGraph v e -> Bool-isOriented = undefined- -- | Indegree of a vertex--- | The number of inbounding 'Arc's to a vertex+--+-- The @indegree@ of a vertex is the number of inbounding 'Arc's to a vertex vertexIndegree :: (Hashable v, Eq v) => DGraph v e -> v -> Int vertexIndegree g v = length $ filter (\(_, v') -> v == v' ) $ edgePairs g  -- | Outdegree of a vertex--- | The number of outbounding 'Arc's from a vertex+--+-- The @outdegree@ of a vertex is the number of outbounding 'Arc's from a vertex vertexOutdegree :: (Hashable v, Eq v) => DGraph v e -> v -> Int vertexOutdegree g v = length $ filter (\(v', _) -> v == v' ) $ edgePairs g @@ -220,53 +252,73 @@ outdegrees :: (Hashable v, Eq v) => DGraph v e -> [Int] outdegrees g = vertexOutdegree g <$> vertices g +-- | Tell if a 'DGraph' is symmetric+--+-- A directed graph is @symmetric@ if all of its 'Arc's are bi-directed+isSymmetric :: DGraph v e -> Bool+isSymmetric = undefined++-- | Tell if a 'DGraph' is oriented+--+-- A directed graph is @oriented@ if there are none bi-directed 'Arc's+--+-- Note: This is /not/ the opposite of 'isSymmetric'+isOriented :: DGraph v e -> Bool+isOriented = undefined+ -- | Tell if a 'DGraph' is balanced--- | A Directed Graph is @balanced@ when its @indegree = outdegree@+--+-- A directed graph is @balanced@ when its @indegree = outdegree@ isBalanced :: (Hashable v, Eq v) => DGraph v e -> Bool isBalanced g = sum (indegrees g) == sum (outdegrees g)  -- | Tell if a 'DGraph' is regular--- | A Directed Graph is @regular@ when all of its vertices have the same number--- | of adjacent vertices AND when the @indegree@ and @outdegree@ of each vertex--- | are equal to each other.+--+-- A directed graph is @regular@ when all of its vertices have the same number+-- of adjacent vertices /AND/ when the @indegree@ and @outdegree@ of each vertex+-- are equal to each other. isRegular :: DGraph v e -> Bool isRegular _ = undefined  -- | Tell if a vertex is a source--- | A vertex is a @source@ when its @indegree = 0@+--+-- A vertex is a @source@ when its @indegree = 0@ 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@+--+-- A vertex is a @sink@ when its @outdegree = 0@ 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@+--+-- A vertex is @internal@ when its neither a @source@ nor a @sink@ 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+--+-- The @transpose@ of a directed graph is another directed graph where all of+-- its arcs are reversed transpose :: (Hashable v, Eq v) => DGraph v e -> DGraph v e transpose g = insertArcs (reverseArc <$> arcs g) empty     where reverseArc (Arc fromV toV attr) = Arc toV fromV attr  -- | Convert a directed 'DGraph' to an undirected 'UGraph' by converting all of--- | its 'Arc's into 'Edge's+-- its 'Arc's into 'Edge's toUndirected :: (Hashable v, Eq v) => DGraph v e -> UG.UGraph v e toUndirected g = UG.insertEdges (arcToEdge <$> arcs g) empty     where arcToEdge (Arc fromV toV attr) = Edge fromV toV attr  --- * Lists---- | Convert a 'DGraph' to a list of 'Arc's--- | Same as 'arcs'+-- | Convert a 'DGraph' to a list of 'Arc's discarding isolated vertices+--+-- Note that because 'toArcsList' discards isolated vertices:+--+-- > fromArcsList . toArcsList /= id toArcsList :: (Hashable v, Eq v) => DGraph v e -> [Arc v e] toArcsList = arcs @@ -275,8 +327,7 @@ fromArcsList as = insertArcs as empty  --- * Pretty printing-+-- | Pretty print a 'DGraph' prettyPrint :: (Hashable v, Eq v, Show v, Show e) => DGraph v e -> String prettyPrint g =     "Isolated Vertices: "

@@ -1,11 +1,17 @@ {-# LANGUAGE ScopedTypeVariables #-}  module Data.Graph.Generation-    ( erdosRenyi+    (+    -- * Erdős–Rényi model+      erdosRenyi     , erdosRenyiU     , erdosRenyiD-    , rndGraph'++    -- * General Random graphs     , rndGraph+    , rndGraph'++    -- * Random adjacency matrix     , rndAdjacencyMatrix     ) where @@ -71,7 +77,8 @@   -- | Generate a random adjacency matrix--- | Useful for use with 'fromAdjacencyMatrix'+--+-- Useful for use with 'fromAdjacencyMatrix' rndAdjacencyMatrix :: Int -> IO [[Int]] rndAdjacencyMatrix n = replicateM n randRow     where randRow = replicateM n (randomRIO (0,1)) :: IO [Int]

@@ -13,12 +13,14 @@ isomorphism = undefined  -- | Tell if a 'UGraph' is regular--- | An undirected graph is @regular@ if each vertex has the same degree+--+-- 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+--+-- A directed graph is @regular@ if each vertex has the same indegree and+-- outdegree isDRegular :: DGraph v e -> Bool isDRegular = undefined

@@ -1,6 +1,11 @@ {-# LANGUAGE ScopedTypeVariables #-} -module Data.Graph.Read where+module Data.Graph.Read+    (+    -- * CSV+      fromCsv+    , fromCsv'+    ) where  import Data.ByteString.Lazy as BS hiding (empty) import Data.Csv             as CSV@@ -9,9 +14,16 @@  import Data.Graph.Types --- | 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)"+-- | Read a graph from a CSV file of adjacency lists+--+-- The CSV lines:+--+-- > "1,2,3,4"+-- > "2,1,4,5"+--+-- produce the graph with this list of edge pairs:+--+-- > [(1, 2), (1, 3), (1, 4), (2, 1), (2, 4), (2, 5)] fromCsv :: Graph g => (Hashable v, Eq v, FromField v)  => FilePath  -> IO (Either String (g v ()))

@@ -2,8 +2,30 @@ {-# LANGUAGE FlexibleInstances   #-} {-# LANGUAGE ScopedTypeVariables #-} -module Data.Graph.Types where+module Data.Graph.Types+    (+    -- * Main Graph type class+    Graph(..) +    -- * Edges type class+    , IsEdge(..)+    -- ** Main IsEdge instances+    , Edge(..)+    , Arc(..)+    -- ** Edges and Arcs constructors+    , (<->)+    , (-->)+    -- ** Edge attributes type clases+    , Weighted(..)+    , Labeled(..)+    -- ** Triple-Edges convenience functions+    , tripleToPair+    , pairToTriple+    , tripleOriginVertex+    , tripleDestVertex+    , tripleAttribute+    ) where+ import Data.List    (foldl') import GHC.Float    (float2Double) import GHC.Generics (Generic)@@ -13,8 +35,8 @@ import Test.QuickCheck  -- | Types that behave like graphs--- |--- | The main 'Graph' instances are 'UGraph' and 'DGraph'. The functions in this+--+-- The main 'Graph' instances are 'UGraph' and 'DGraph'. The functions in this -- class should be used for algorithms that are graph-directionality agnostic, -- otherwise use the more specific ones in 'UGraph' and 'DGraph' class Graph g where@@ -24,17 +46,20 @@     empty :: (Hashable v) => g v e      -- | Retrieve the order of a graph-    -- | The @order@ of a graph is its number of vertices+    --+    -- The @order@ of a graph is its number of vertices     order :: g v e -> Int      -- | Retrieve the size of a graph-    -- | The @size@ of a graph is its number of edges+    --+    -- The @size@ of a graph is its number of edges     size :: (Hashable v, Eq v) => g v e -> Int     size = length . edgePairs      -- | Density of a graph-    -- | The ratio of the number of existing edges in the graph to the number of-    -- | posible edges+    --+    -- The @density@ of a graph is the ratio of the number of existing edges 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@@ -68,11 +93,11 @@     adjacentVertices' :: (Hashable v, Eq v) => g v e -> v -> [(v, v, e)]      -- | Same as 'adjacentVertices' but gives back only those vertices for which-    -- | the connecting edge allows the vertex to be reached.-    -- |-    -- | For an undirected graph this is equivalent to 'adjacentVertices', but-    -- | for the case of a directed graph, the directed arcs will constrain the-    -- | reachability of the adjacent vertices.+    -- the connecting edge allows the vertex to be reached.+    --+    -- For an undirected graph this is equivalent to 'adjacentVertices', but+    -- for the case of a directed graph, the directed arcs will constrain the+    -- reachability of the adjacent vertices.     reachableAdjacentVertices :: (Hashable v, Eq v) => g v e -> v -> [v]     reachableAdjacentVertices g v = tripleDestVertex <$> reachableAdjacentVertices' g v @@ -98,13 +123,12 @@     avgDegree :: (Hashable v, Eq v) => g v e -> Double     avgDegree g = fromIntegral (2 * size g) / fromIntegral (order g) -    -- | Insert a vertex into a graph-    -- | If the graph already contains the vertex leave the graph untouched+    -- | Insert a vertex into a graph. If the graph already contains the vertex+    -- leave it untouched     insertVertex :: (Hashable v, Eq v) => v -> g v e -> g v e -    -- | Insert a many vertices into a graph-    -- | New vertices are inserted and already contained vertices are left-    -- | untouched+    -- | Insert many vertices into a graph. New vertices are inserted and+    -- already contained vertices are left untouched     insertVertices :: (Hashable v, Eq v) => [v] -> g v e -> g v e     insertVertices vs g = foldl' (flip insertVertex) g vs @@ -121,9 +145,9 @@     -- | Get the edge between to vertices if it exists     edgeTriple :: (Hashable v, Eq v) => g v e -> v -> v -> Maybe (v, v, e) -    -- | 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+    -- | Insert an edge into a graph. The involved vertices are inserted if+    -- don't exist. If the graph already contains the edge, its attribute gets+    -- updated     insertEdgeTriple :: (Hashable v, Eq v) => (v, v, e) -> g v e -> g v e      -- | Same as 'insertEdgeTriple' but for multiple edges@@ -131,7 +155,7 @@     insertEdgeTriples es g = foldl' (flip insertEdgeTriple) g es      -- | Same as 'insertEdgeTriple' but insert edge pairs in graphs with-    -- | attributeless edges+    -- attribute less edges     insertEdgePair :: (Hashable v, Eq v) => (v, v) -> g v () -> g v ()     insertEdgePair (v1, v2) = insertEdgeTriple (v1, v2, ()) @@ -139,24 +163,24 @@     insertEdgePairs :: (Hashable v, Eq v) => [(v, v)] -> g v () -> g v ()     insertEdgePairs es g = foldl' (flip insertEdgePair) g es -    -- | Remove a vertex from a graph if present-    -- | Every edge incident to this vertex is also removed+    -- | Remove a vertex from a graph if present. Every edge incident to this+    -- vertex also gets removed     removeVertex :: (Hashable v, Eq v) => v -> g v e -> g v e      -- | Same as 'removeVertex' but for multiple vertices     removeVertices :: (Hashable v, Eq v) => [v] -> g v e -> g v e     removeVertices vs g = foldl' (flip removeVertex) g vs -    -- | Remove an edge from a graph if present-    -- | The involved vertices are left untouched+    -- | Remove an edge from a graph if present. The involved vertices are left+    -- untouched     removeEdgePair :: (Hashable v, Eq v) => (v, v) -> g v e -> g v e -    -- | Same as 'removeEdgePair' but for multple edges+    -- | Same as 'removeEdgePair' but for multiple edges     removeEdgePairs :: (Hashable v, Eq v) => [(v, v)] -> g v e -> g v e     removeEdgePairs es g = foldl' (flip removeEdgePair) g es -    -- | Remove the edge from a graph if present-    -- | The involved vertices are also removed+    -- | Remove the edge from a graph if present. The involved vertices also get+    -- removed     removeEdgePairAndVertices :: (Hashable v, Eq v) => (v, v) -> g v e -> g v e     removeEdgePairAndVertices (v1, v2) g =         removeVertex v2 $ removeVertex v1 $ removeEdgePair (v1, v2) g@@ -166,7 +190,8 @@     isolatedVertices g = filter (\v -> vertexDegree g v == 0) $ vertices g      -- | Tell if a graph is simple-    -- | A graph is @simple@ if it has no loops+    --+    -- A graph is @simple@ if it has no loops     isSimple :: (Hashable v, Eq v) => g v e -> Bool  @@ -181,10 +206,12 @@      -- * Transformations -    -- | Convert a graph to an adjacency list with edge attributes in /e/+    -- | Convert a graph to an adjacency list with vertices in type /v/ and edge+    -- attributes in /e/     toList :: (Hashable v, Eq v) => g v e -> [(v, [(v, e)])] -    -- | Construct a graph from an adjacency list with edge attributes in /e/+    -- | Construct a graph from an adjacency list with vertices in type /v and+    -- edge attributes in /e/     fromList :: (Hashable v, Eq v) => [(v, [(v, e)])] -> g v e     fromList links = go links empty         where@@ -197,18 +224,17 @@                     es      -- TODO: make this [[Bool]]-    -- | Get the adjacency binary matrix representation of a grah+    -- | Get the adjacency binary matrix representation of a graph     toAdjacencyMatrix :: g v e -> [[Int]] -    -- | Generate a graph of Int vertices from an adjacency-    -- | square binary matrix+    -- | Generate a graph of Int vertices from an adjacency square binary matrix     fromAdjacencyMatrix :: [[Int]] -> Maybe (g Int ())    -- | Types that represent edges--- |--- | The main 'IsEdge' instances are 'Edge' for undirected edges and 'Arc' for+--+-- The main 'IsEdge' instances are 'Edge' for undirected edges and 'Arc' for -- directed edges. class IsEdge e where     -- | Retrieve the origin vertex of the edge@@ -229,7 +255,7 @@     fromPair :: (v, v) -> e v ()      -- | Convert an edge to a triple, where the 3rd element it's the edge-    -- | attribute+    -- attribute     toTriple :: e v a -> (v, v, a)      -- | Convert a triple to an edge@@ -239,7 +265,8 @@     -- * Properties      -- | Tell if an edge is a loop-    -- | An edge forms a @loop@ if both of its ends point to the same vertex+    --+    -- An edge forms a @loop@ if both of its ends point to the same vertex     isLoop :: (Eq v) => e v a -> Bool  @@ -252,11 +279,11 @@ data Arc v e = Arc v v e     deriving (Show, Read, Ord, Generic) --- | Construct an attributeless undirected 'Edge' between two vertices+-- | Construct an attribute less undirected 'Edge' between two vertices (<->) :: (Hashable v) => v -> v -> Edge v () (<->) v1 v2 = Edge v1 v2 () --- | Construct an attributeless directed 'Arc' between two vertices+-- | Construct an attribute less directed 'Arc' between two vertices (-->) :: (Hashable v) => v -> v -> Arc v () (-->) v1 v2 = Arc v1 v2 () @@ -328,7 +355,7 @@     where vert = getPositive <$> arbitrary  -- | Two 'Edge's are equal if they point to the same vertices, regardless of the--- | direction+-- direction instance (Eq v, Eq a) => Eq (Edge v a) where     (Edge v1 v2 a) == (Edge v1' v2' a') =         (a == a')@@ -336,12 +363,10 @@         || (v1 == v2' && v2 == v1')  -- | Two 'Arc's are equal if they point to the same vertices, and the directions--- | are the same+-- are the same instance (Eq v, Eq a) => Eq (Arc v a) where     (Arc v1 v2 a) == (Arc v1' v2' a') = (a == a') && (v1 == v1' && v2 == v2') ---- * Triples convenience functions  -- | Convert a triple to a pair by ignoring the third element tripleToPair :: (a, b, c) -> (a, b)

@@ -4,8 +4,29 @@ {-# LANGUAGE TypeSynonymInstances #-} {-# LANGUAGE ViewPatterns         #-} -module Data.Graph.UGraph where+module Data.Graph.UGraph+    (+    -- * UGraph data type+    UGraph +    -- * Functions on UGraph+    , insertEdge+    , insertEdges+    , removeEdge+    , removeEdges+    , removeEdgeAndVertices+    , edges+    , containsEdge+    , incidentEdges++    -- * List conversions+    , toEdgesList+    , fromEdgesList++    -- * Pretty printing+    , prettyPrint+    ) where+ import qualified Data.Foldable  as F (toList) import           Data.List      (foldl', intersect) import           Data.Semigroup@@ -130,8 +151,9 @@   -- | Insert an undirected 'Edge' into a 'UGraph'--- | The involved vertices are inserted if they don't exist. If the graph--- | already contains the Edge, its attribute is updated+--+-- The involved vertices are inserted if they don't exist. If the graph already+-- contains the Edge, its attribute gets updated insertEdge :: (Hashable v, Eq v) => Edge v e -> UGraph v e -> UGraph v e insertEdge (Edge v1 v2 edgeAttr) g@(UGraph s _)     | containsEdgePair g (v1, v2) = g@@ -144,8 +166,8 @@ insertEdges :: (Hashable v, Eq v) => [Edge v e] -> UGraph v e -> UGraph v e insertEdges es g = foldl' (flip insertEdge) g es --- | Remove the undirected 'Edge' from a 'UGraph' if present--- | The involved vertices are left untouched+-- | 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 @@ -153,8 +175,8 @@ removeEdges :: (Hashable v, Eq v) => [Edge v e] -> UGraph v e -> UGraph v e removeEdges es g = foldl' (flip removeEdge) g es --- | Remove the undirected 'Edge' from a 'UGraph' if present--- | The involved vertices are also removed+-- | Remove the undirected 'Edge' from a 'UGraph' if present. The involved+-- vertices also get removed removeEdgeAndVertices :: (Hashable v, Eq v) => Edge v e -> UGraph v e -> UGraph v e removeEdgeAndVertices = removeEdgePairAndVertices . toPair @@ -178,11 +200,10 @@ incidentEdges (UGraph _ g) v = fmap (uncurry (Edge v)) (HM.toList (getLinks v g))  --- * Lists---- | Convert a 'UGraph' to a list of 'Edge's ignoring isolated vertices--- |--- | Note that: fromEdgesList . toEdgesList /= id+-- | Convert a 'UGraph' to a list of 'Edge's discarding isolated vertices+--+-- Note that because 'toEdgesList' discards isolated vertices:+-- > fromEdgesList . toEdgesList /= id toEdgesList :: (Hashable v, Eq v) => UGraph v e -> [Edge v e] toEdgesList = edges @@ -191,8 +212,7 @@ fromEdgesList es = insertEdges es empty  --- * Pretty printing-+-- | Pretty print a 'UGraph' prettyPrint :: (Hashable v, Eq v, Show v, Show e) => UGraph v e -> String prettyPrint g =     "Isolated Vertices: "

@@ -1,5 +1,20 @@-module Data.Graph.UGraph.DegreeSequence where+module Data.Graph.UGraph.DegreeSequence+    (+    DegreeSequence +    -- * Construction+    , degreeSequence+    , getDegreeSequence++    -- * Queries+    , isGraphicalSequence+    , isDirectedGraphic+    , holdsHandshakingLemma++    -- * Graph generation+    , fromGraphicalSequence+    ) where+ import Data.List (reverse, sort)  import Data.Hashable@@ -7,28 +22,29 @@ 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+-- | The Degree Sequence of a simple 'UGraph' is a list of degrees of the+-- vertices in the 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+-- | Construct a 'DegreeSequence' from a list of degrees. Negative degree values+-- get 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+-- | 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+--+-- A Degree Sequence is a @Graphical Sequence@ if a corresponding 'UGraph' for+-- it exists. Uses the Havel-Hakimi algorithm isGraphicalSequence :: DegreeSequence -> Bool isGraphicalSequence (DegreeSequence []) = True isGraphicalSequence (DegreeSequence (x:xs))@@ -37,18 +53,19 @@         where seq' = 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+--+-- A @Directed Graphic@ is a Degree Sequence for which 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+-- 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+-- | 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

@@ -1,13 +1,15 @@ module Data.Graph.Visualize-    ( plotUGraph-    , plotUGraphPng+    (+    -- * Visualize graphs+      plotUGraph     , plotDGraph-    , plotDGraphPng-    , plotUGraphEdgeLabeled-    , plotDGraphEdgeLabeled+    -- ** Render edge attributes+    , plotUGraphEdged+    , plotDGraphEdged -    , labeledNodes-    , labeledEdges+    -- * Render to PNG+    , plotUGraphPng+    , plotDGraphPng     ) where  import Control.Concurrent@@ -27,11 +29,11 @@  -> IO ThreadId plotUGraph g = forkIO $ runGraphvizCanvas Sfdp (toUndirectedDot False g) Xlib --- | Same as 'plotUGraph' but render edge labels-plotUGraphEdgeLabeled :: (Hashable v, Ord v, PrintDot v, Show v, Show e)+-- | Same as 'plotUGraph' but render edge attributes+plotUGraphEdged :: (Hashable v, Ord v, PrintDot v, Show v, Show e)  => UGraph v e  -> IO ThreadId-plotUGraphEdgeLabeled g = forkIO $ runGraphvizCanvas Sfdp (toUndirectedDot True g) Xlib+plotUGraphEdged g = forkIO $ runGraphvizCanvas Sfdp (toUndirectedDot True g) Xlib  -- | Plot an undirected 'UGraph' to a PNG image file plotUGraphPng :: (Hashable v, Ord v, PrintDot v, Show v, Show e)@@ -46,11 +48,11 @@  -> IO ThreadId plotDGraph g = forkIO $ runGraphvizCanvas Sfdp (toDirectedDot False g) Xlib --- | Same as 'plotDGraph' but render edge labels-plotDGraphEdgeLabeled :: (Hashable v, Ord v, PrintDot v, Show v, Show e)+-- | Same as 'plotDGraph' but render edge attributes+plotDGraphEdged :: (Hashable v, Ord v, PrintDot v, Show v, Show e)  => DGraph v e  -> IO ThreadId-plotDGraphEdgeLabeled g = forkIO $ runGraphvizCanvas Sfdp (toDirectedDot True g) Xlib+plotDGraphEdged g = forkIO $ runGraphvizCanvas Sfdp (toDirectedDot True g) Xlib  -- | Plot a directed 'DGraph' to a PNG image file plotDGraphPng :: (Hashable v, Ord v, PrintDot v, Show v, Show e)