graph-generators 0.1.0.0 → 0.1.1.0

raw patch · 4 files changed

+153/−138 lines, 4 filesPVP: major bump suggested

API removals or changes: PVP suggests a major version bump

API changes (from Hackage documentation)

Files

• Data/Graph/Generators/Regular.hs +143/−0
• Data/Graph/Generators/Simple.hs +0/−133
• GraphGeneratorsTest.hs +8/−3
• graph-generators.cabal +2/−2

@@ -0,0 +1,143 @@+{-# LANGUAGE Safe #-}++{-+    Graph generators for simple parametric, regular graphs.++    Built using NetworkX 1.8.1, see <http://networkx.github.io/documentation/latest/reference/generators.html NetworkX Generators>+-}+module Data.Graph.Generators.Regular (+        completeGraph,+        completeGraphWithSelfloops,+        completeBipartiteGraph,+        emptyGraph,+        barbellGraph,+        generalizedBarbellGraph,+        cycleGraph,+        lineGraph+    ) where++import Data.Graph.Generators++{-+    Generate a completely connected graph with n nodes.++    The generated graph contains node labels [0..n-1]++    In contrast to 'completeGraphWithSelfloops' this function+    does not generate self-loops.++    Contains only one edge between two connected nodes,+    use 'Data.Graph.Inductive.Basic.undir' to make it+    quasi-undirected. The generated edge (i,j) satisfied @i < j@.+-}+completeGraph :: Int -- ^ The number of nodes in the graph+              -> GraphInfo -- ^ The resulting complete graph+completeGraph n =+    let allNodes = [0..n-1]+        allEdges = [(i,j) | i <- allNodes,j <- allNodes, i < j]+    in GraphInfo n allEdges++{-+    Variant of 'completeGraph' generating self-loops.++    The generated edge (i,j) satisfied @i <= j@.++    See 'completeGraph' for a more detailed behaviour description+-}+completeGraphWithSelfloops :: Int -- ^ The number of nodes in the graph+                         -> GraphInfo -- ^ The resulting complete graph+completeGraphWithSelfloops n =+    let allNodes = [0..n-1]+        allEdges = [(i, j) | i <- allNodes, j <- allNodes, i <= j]+    in GraphInfo n allEdges++{-+    Generate the complete bipartite graph with n1 nodes in+    the first partition and n2 nodes in the second partition.++    Each node in the first partition is connected to each node+    in the second partition.++    The first partition nodes are identified by [0..n1-1]+    while the nodes in the second partition are identified+    by [n1..n1+n2-1]++    Use 'Data.Graph.Inductive.Basic.undir' to also add edges+    from the second partition to the first partition.+-}+completeBipartiteGraph :: Int -- ^ The number of nodes in the first partition+                       -> Int -- ^ The number of nodes in the second partition+                       -> GraphInfo -- ^ The resulting graph+completeBipartiteGraph n1 n2 =+    let nodesP1 = [0..n1-1]+        nodesP2 = [n1..n1+n2-1]+        allEdges = [(i, j) | i <- nodesP1, j <- nodesP2]+    in GraphInfo (n1+n2) allEdges++{-+    Generates the empty graph with n nodes and zero edges.++    The nodes are labelled [0..n-1]+-}+emptyGraph :: Int -> GraphInfo+emptyGraph n = GraphInfo n []++{-+    Generate the barbell graph, consisting of two complete subgraphs+    connected by a single path.++    In contrast to 'generalizedBarbellGraph', this function always+    generates identically-sized bells. Therefore this is a special+    case of 'generalizedBarbellGraph'+-}+barbellGraph :: Int -- ^ The number of nodes in the complete bells+             -> Int -- ^ The number of nodes in the path,+                    --   i.e the number of nodes outside the bells+             -> GraphInfo -- ^ The resulting barbell graph+barbellGraph n np = generalizedBarbellGraph n np n++{-+    Generate the barbell graph, consisting of two complete subgraphs+    connected by a single path.++    Self-loops are not generated.++    The nodes in the first bell are identified by [0..n1-1]+    The nodes in the path are identified by [n1..n1+np-1]+    The nodes in the second bell are identified by [n1+np..n1+np+n2-1]++    The path only contains edges +-}+generalizedBarbellGraph :: Int -- ^ The number of nodes in the first bell+                        -> Int -- ^ The number of nodes in the path, i.e.+                               --   the number of nodes outside the bells+                        -> Int -- ^ The number of nodes in the second bell+                        -> GraphInfo -- ^ The resulting barbell graph+generalizedBarbellGraph n1 np n2 =+    let nodesP1 = [0..n1-1]+        nodesPath = [n1..n1+np-1]+        nodesP2 = [n1+np..n1+np+n2-1]+        edgesP1 = [(i, j) | i <- nodesP1, j <- nodesP1, i /= 2]+        edgesPath = [(i, i+1) | i <- [n1+np..n1+np+n2]]+        edgesP2 = [(i, j) | i <- nodesP2, j <- nodesP2]+    in GraphInfo (n1+np+n2) (edgesP1 ++ edgesPath ++ edgesP2)++{-+    Generate the cycle graph of size n.++    Edges are created from lower node IDs to higher node IDs.+-}+cycleGraph :: Int -- ^ n: Number of nodes in the circle+           -> GraphInfo -- ^ The circular graph with n nodes.+cycleGraph n =+    let edges = (n-1, 0) : [(i, i+1) | i <- [0..n-2]]+    in GraphInfo n edges++{-+    Generate the line graph of size n+-}+lineGraph :: Int -- ^ n: Number of nodes+          -> GraphInfo+lineGraph n =+    let edges = [(i, i+1) | i <- [0..n-2]]+    in GraphInfo n edges

@@ -1,133 +0,0 @@-{-# LANGUAGE Safe #-}--{--    Graph generators for simple parametric graphs.--    Built using NetworkX 1.8.1, see <http://networkx.github.io/documentation/latest/reference/generators.html NetworkX Generators>--}-module Data.Graph.Generators.Simple (-        completeGraph,-        completeGraphWithSelfloops,-        completeBipartiteGraph,-        emptyGraph,-        barbellGraph,-        generalizedBarbellGraph,-        cycleGraph-    ) where--import Data.Graph.Generators--{--    Generate a completely connected graph with n nodes.--    The generated graph contains node labels [0..n-1]--    In contrast to 'completeGraphWithSelfloops' this function-    does not generate self-loops.--    Contains only one edge between two connected nodes,-    use 'Data.Graph.Inductive.Basic.undir' to make it-    quasi-undirected. The generated edge (i,j) satisfied @i < j@.--}-completeGraph :: Int -- ^ The number of nodes in the graph-              -> GraphInfo -- ^ The resulting complete graph-completeGraph n =-    let allNodes = [0..n-1]-        allEdges = [(i,j) | i <- allNodes,j <- allNodes, i < j]-    in GraphInfo n allEdges--{--    Variant of 'completeGraph' generating self-loops.--    The generated edge (i,j) satisfied @i <= j@.--    See 'completeGraph' for a more detailed behaviour description--}-completeGraphWithSelfloops :: Int -- ^ The number of nodes in the graph-                         -> GraphInfo -- ^ The resulting complete graph-completeGraphWithSelfloops n =-    let allNodes = [0..n-1]-        allEdges = [(i, j) | i <- allNodes, j <- allNodes, i <= j]-    in GraphInfo n allEdges--{--    Generate the complete bipartite graph with n1 nodes in-    the first partition and n2 nodes in the second partition.--    Each node in the first partition is connected to each node-    in the second partition.--    The first partition nodes are identified by [0..n1-1]-    while the nodes in the second partition are identified-    by [n1..n1+n2-1]--    Use 'Data.Graph.Inductive.Basic.undir' to also add edges-    from the second partition to the first partition.--}-completeBipartiteGraph :: Int -- ^ The number of nodes in the first partition-                       -> Int -- ^ The number of nodes in the second partition-                       -> GraphInfo -- ^ The resulting graph-completeBipartiteGraph n1 n2 =-    let nodesP1 = [0..n1-1]-        nodesP2 = [n1..n1+n2-1]-        allEdges = [(i, j) | i <- nodesP1, j <- nodesP2]-    in GraphInfo (n1+n2) allEdges--{--    Generates the empty graph with n nodes and zero edges.--    The nodes are labelled [0..n-1]--}-emptyGraph :: Int -> GraphInfo-emptyGraph n = GraphInfo n []--{--    Generate the barbell graph, consisting of two complete subgraphs-    connected by a single path.--    In contrast to 'generalizedBarbellGraph', this function always-    generates identically-sized bells. Therefore this is a special-    case of 'generalizedBarbellGraph'--}-barbellGraph :: Int -- ^ The number of nodes in the complete bells-             -> Int -- ^ The number of nodes in the path,-                    --   i.e the number of nodes outside the bells-             -> GraphInfo -- ^ The resulting barbell graph-barbellGraph n np = generalizedBarbellGraph n np n--{--    Generate the barbell graph, consisting of two complete subgraphs-    connected by a single path.--    Self-loops are not generated.--    The nodes in the first bell are identified by [0..n1-1]-    The nodes in the path are identified by [n1..n1+np-1]-    The nodes in the second bell are identified by [n1+np..n1+np+n2-1]--    The path only contains edges --}-generalizedBarbellGraph :: Int -- ^ The number of nodes in the first bell-                        -> Int -- ^ The number of nodes in the path, i.e.-                               --   the number of nodes outside the bells-                        -> Int -- ^ The number of nodes in the second bell-                        -> GraphInfo -- ^ The resulting barbell graph-generalizedBarbellGraph n1 np n2 =-    let nodesP1 = [0..n1-1]-        nodesPath = [n1..n1+np-1]-        nodesP2 = [n1+np..n1+np+n2-1]-        edgesP1 = [(i, j) | i <- nodesP1, j <- nodesP1, i /= 2]-        edgesPath = [(i, i+1) | i <- [n1+np..n1+np+n2]]-        edgesP2 = [(i, j) | i <- nodesP2, j <- nodesP2]-    in GraphInfo (n1+np+n2) (edgesP1 ++ edgesPath ++ edgesP2)--{--    Generate the cycle graph of size n.--    Edges are created from lower node IDs to higher node IDs.--}-cycleGraph :: Int -- ^ n: Number of nodes in the circle-           -> GraphInfo -- ^ The circular graph with n nodes.-cycleGraph n =-    let edges = (n-1, 0) : [(i, i+1) | i <- [0..n-2]]-    in GraphInfo n edges

@@ -3,7 +3,7 @@ import Control.Exception (evaluate) import Control.Monad import Data.Graph.Generators.Classic-import Data.Graph.Generators.Simple+import Data.Graph.Generators.Regular import Data.Graph.Generators.Random.ErdosRenyi import Data.Graph.Generators.Random.BarabasiAlbert import Data.Graph.Generators@@ -38,10 +38,15 @@         truncatedCubeGraph `shouldSatisfy` checkGraphInfo         truncatedTetrahedronGraph `shouldSatisfy` checkGraphInfo         tutteGraph `shouldSatisfy` checkGraphInfo-  describe "Simple graphs" $ do+  describe "Complete graphs" $ do     it "should pass the integrity checks" $ do-        forM_ [0..10] $ \n -> +        forM_ [0..10] $ \n ->             completeGraph n `shouldSatisfy` checkGraphInfo+    --it "should have n^2/2 edges" $ do+  describe "Regular graphs" $ do+    it "should pass the integrity checks" $ do+        forM_ [0..25] $ \n -> +            lineGraph n `shouldSatisfy` checkGraphInfo   describe "Erdös Renyi random graphs" $ do     it "should pass the integrity checks" $ do         forM_ [0..20] $ \n -> do

@@ -1,5 +1,5 @@ name:                graph-generators-version:             0.1.0.0+version:             0.1.1.0 synopsis:            Functions for generating structured or random FGL graphs description:         Generators for graphs.                      Supports classic (constant-sized) graphs, deterministic Generators@@ -30,7 +30,7 @@ library   exposed-modules: Data.Graph.Generators,                    Data.Graph.Generators.Classic,-                   Data.Graph.Generators.Simple,+                   Data.Graph.Generators.Regular,                    Data.Graph.Generators.FGL,                    Data.Graph.Generators.Random.ErdosRenyi,                    Data.Graph.Generators.Random.BarabasiAlbert