fgl-arbitrary 0.1.0.0 → 0.2.0.0

raw patch · 3 files changed

+96/−42 lines, 3 filesdep ~fglPVP ok

version bump matches the API change (PVP)

Dependency ranges changed: fgl

API changes (from Hackage documentation)

Files

• ChangeLog +16/−0
• Data/Graph/Inductive/Arbitrary.hs +72/−38
• fgl-arbitrary.cabal +8/−4

@@ -0,0 +1,16 @@+0.2.0.0+-------++* Properly set the version of fgl required: it needs some of the newer+  functions present in 5.5.2.0 (which was not yet released when+  version 0.1.0.0 of this library was released).++* Allow partial application of the `SimpleGraph` type.++* The `Connected` wrapper has changed, and the constructor is now+  exported.++0.1.0.0+-------++* Initial release

@@ -1,4 +1,4 @@-{-# LANGUAGE FlexibleContexts, ScopedTypeVariables, TypeFamilies #-}+{-# LANGUAGE CPP, FlexibleContexts, ScopedTypeVariables, TypeFamilies #-} {-# OPTIONS_GHC -fno-warn-orphans #-} {- |    Module      : Data.Graph.Inductive.Arbitrary@@ -10,14 +10,26 @@ This module provides default definitions for use with QuickCheck's 'Arbitrary' class. +Both "Data.Graph.Inductive.Tree"- and+"Data.Graph.Inductive.PatriciaTree"-based graph implementations have+'Arbitrary' instances.  In most cases, this is all you will need.++If, however, you want to create arbitrary custom graph-like data+structures, then you will probably want to do some custom processing+from an arbitrary 'GraphNodesEdges' value, either directly or with a+custom 'ArbGraph' instance.+  -} module Data.Graph.Inductive.Arbitrary-       ( arbitraryGraph+       ( -- * Explicit graph creation+         -- $explicit+         arbitraryGraph        , arbitraryGraphWith        , shrinkGraph        , shrinkGraphWith          -- * Types of graphs        , ArbGraph(..)+       , GrProxy(..)        , shrinkF        , arbitraryGraphBy          -- ** Specific graph structures@@ -26,7 +38,7 @@        , SimpleGraph        , Undirected(..)          -- ** Connected graphs-       , Connected+       , Connected(..)        , connGraph          -- * Node and edge lists        , arbitraryNodes@@ -43,14 +55,16 @@  import Test.QuickCheck (Arbitrary (..), Gen, elements, listOf) -import           Control.Applicative (liftA3, (<*>))-import           Control.Arrow       (second)-import           Data.Function       (on)-import           Data.Functor        ((<$>))-import           Data.List           (deleteBy, groupBy, sortBy)-import           Data.Map            (Map)-import qualified Data.Map            as M+import Control.Applicative (liftA3)+import Control.Arrow       (second)+import Data.Function       (on)+import Data.List           (deleteBy, groupBy, sortBy)+import Data.Maybe          (mapMaybe) +#if __GLASGOW_HASKELL__ < 710+import Control.Applicative ((<$>), (<*>))+#endif+ -- -----------------------------------------------------------------------------  -- | Generally a list of labelled nodes.@@ -70,7 +84,7 @@ -- --   If any specific structure (no multiple edges, no loops, etc.) is --   required then you will need to post-process this after generating---   it.+--   it, or else create a new instance of 'ArbGraph'. data GraphNodesEdges a b = GNEs { graphNodes :: [LNode a]                                 , graphEdges :: [LEdge b]                                 }@@ -97,6 +111,10 @@ -- --   Typically, you would only use this for the 'toBaseGraph' function --   or if you wanted to make a custom graph wrapper.+--+--   The intent of this class is to simplify defining and using+--   different wrappers on top of graphs (e.g. you may wish to have an+--   'Undirected' graph, or one with 'NoLoops', or possibly both!). class (DynGraph (BaseGraph ag)) => ArbGraph ag where   type BaseGraph ag :: * -> * -> * @@ -106,12 +124,14 @@    -- | Any manipulation of edges that should be done to satisfy the   --   requirements of the specified wrapper.-  edgeF :: Proxy ag -> [LEdge b] -> [LEdge b]+  edgeF :: GrProxy ag -> [LEdge b] -> [LEdge b]    -- | Shrinking function (assuming only one node is removed at a   --   time) which also returns the node that is removed.   shrinkFWith :: ag a b -> [(Node, ag a b)] +-- | In most cases, for an instance of 'ArbGraph' the 'Arbitrary'+--   instance definition will\/can have @shrink = shrinkF@. shrinkF :: (ArbGraph ag) => ag a b -> [ag a b] shrinkF = map snd . shrinkFWith @@ -135,11 +155,20 @@    shrinkFWith = shrinkGraphWith -data Proxy (gr :: * -> * -> *) = Proxy-                                 deriving (Eq, Ord, Show, Read)+-- | A simple graph-specific proxy type.+data GrProxy (gr :: * -> * -> *) = GrProxy+  deriving (Eq, Ord, Show, Read)  -- ----------------------------------------------------------------------------- +{- $explicit++If you wish to explicitly create a generated graph value (rather than+using the 'Arbitrary' class) then you will want to use these+functions.++-}+ -- | Generate an arbitrary graph.  Multiple edges are allowed. arbitraryGraph :: (Graph gr, Arbitrary a, Arbitrary b) => Gen (gr a b) arbitraryGraph = arbitraryGraphWith id@@ -157,7 +186,7 @@ arbitraryGraphBy :: forall ag a b. (ArbGraph ag, Arbitrary a, Arbitrary b)                     => Gen (ag a b) arbitraryGraphBy = fromBaseGraph-                   <$> arbitraryGraphWith (edgeF (Proxy :: Proxy ag))+                   <$> arbitraryGraphWith (edgeF (GrProxy :: GrProxy ag))  -- Ensure we have a list of unique Node values; this will also sort -- the list, but that shouldn't matter.@@ -173,6 +202,7 @@ shrinkGraph :: (Graph gr) => gr a b -> [gr a b] shrinkGraph = map snd . shrinkGraphWith +-- | As with 'shrinkGraph', but also return the node that was deleted. shrinkGraphWith :: (Graph gr) => gr a b -> [(Node, gr a b)] shrinkGraphWith gr = case nodes gr of                        -- Need to have at least 2 nodes before we delete one!@@ -200,7 +230,7 @@   toBaseGraph = toBaseGraph. nmeGraph   fromBaseGraph = NME . fromBaseGraph -  edgeF _ = uniqBy toEdge . edgeF (Proxy :: Proxy gr)+  edgeF _ = uniqBy toEdge . edgeF (GrProxy :: GrProxy gr)    shrinkFWith = map (second NME) . shrinkFWith . nmeGraph @@ -220,7 +250,7 @@   toBaseGraph = toBaseGraph . looplessGraph   fromBaseGraph = NL . fromBaseGraph -  edgeF _ = filter notLoop . edgeF (Proxy :: Proxy gr)+  edgeF _ = filter notLoop . edgeF (GrProxy :: GrProxy gr)    shrinkFWith = map (second NL) . shrinkFWith . looplessGraph @@ -234,7 +264,7 @@  -- | A wrapper to generate a graph without multiple edges and --   no loops.-type SimpleGraph gr a b = NoLoops (NoMultipleEdges gr) a b+type SimpleGraph gr = NoLoops (NoMultipleEdges gr)  -- | A newtype wrapper such that each (non-loop) edge also has its --   reverse in the graph.@@ -253,7 +283,7 @@   toBaseGraph = toBaseGraph . undirGraph   fromBaseGraph = UG . fromBaseGraph -  edgeF _ = undirect . edgeF (Proxy :: Proxy gr)+  edgeF _ = undirect . edgeF (GrProxy :: GrProxy gr)    shrinkFWith = map (second UG) . shrinkFWith . undirGraph @@ -273,11 +303,14 @@  -- | A brute-force approach to generating connected graphs. --+--   The resultant graph (obtained with 'connGraph') will /never/ be+--   empty: it will, at the very least, contain an additional+--   connected node (obtained with 'connNode').+-- --   Note that this is /not/ an instance of 'ArbGraph' as it is not --   possible to arbitrarily layer a transformer on top of this.-data Connected ag a b = CG { origGraph :: ag a b-                           , connNode  :: LNode a-                           , connEdges :: Map Node [LEdge b]+data Connected ag a b = CG { connNode     :: Node+                           , connArbGraph :: ag a b                            }                         deriving (Eq, Show, Read) @@ -289,10 +322,12 @@ toConnGraph :: forall ag a b. (ArbGraph ag, Arbitrary a, Arbitrary b)                => ag a b -> Gen (Connected ag a b) toConnGraph ag = do a <- arbitrary-                    eM <- M.fromList <$> mapM mkE ws-                    return $ CG { origGraph = ag-                                , connNode  = (v, a)-                                , connEdges = eM+                    ces <- concat <$> mapM mkE ws+                    return $ CG { connNode     = v+                                , connArbGraph = fromBaseGraph+                                                 . insEdges ces+                                                 . insNode (v,a)+                                                 $ g                                 }   where     g = toBaseGraph ag@@ -302,23 +337,22 @@     ws = nodes g      mkE w = do b <- arbitrary-               return (w, edgeF p [(v,w,b)])+               return (edgeF p [(v,w,b)]) -    p :: Proxy ag-    p = Proxy+    p :: GrProxy ag+    p = GrProxy  shrinkConnGraph :: (ArbGraph ag) => Connected ag a b -> [Connected ag a b]-shrinkConnGraph cg = map go (shrinkFWith (origGraph cg))+shrinkConnGraph cg = mapMaybe keepConn . shrinkFWith $ g   where-    go (w,ag') = cg { origGraph = ag'-                    , connEdges = M.delete w (connEdges cg)-                    }+    v = connNode cg+    g = connArbGraph cg +    keepConn (w,sgs) | v == w    = Nothing+                     | otherwise = Just (cg { connArbGraph = sgs })++-- | The underlying graph represented by this 'Connected' value. connGraph :: (ArbGraph ag) => Connected ag a b -> BaseGraph ag a b-connGraph cg = insEdges les . insNode lv $ g-  where-    g = toBaseGraph (origGraph cg)-    lv = connNode cg-    les = concat . M.elems $ connEdges cg+connGraph = toBaseGraph . connArbGraph  -- -----------------------------------------------------------------------------

@@ -1,9 +1,13 @@ name:                fgl-arbitrary-version:             0.1.0.0+version:             0.2.0.0 synopsis:            QuickCheck support for fgl description:   Provides Arbitrary instances for fgl graphs (to avoid adding a-  QuickCheck dependency for fgl)+  QuickCheck dependency for fgl whilst still making the instances+  available to others).+  .+  Also available are non-fgl-specific functions for generating+  graph-like data structures. license:             BSD3 license-file:        LICENSE author:              Ivan Lazar Miljenovic@@ -12,6 +16,7 @@ category:            Testing, Graphs build-type:          Simple cabal-version:       >=1.10+extra-source-files:  ChangeLog  source-repository head     type:         git@@ -23,8 +28,7 @@   -- other-modules:   -- other-extensions:   build-depends:       base < 5-                     , containers-                     , fgl < 6+                     , fgl >= 5.5.2.0 && < 6                      , QuickCheck >= 2.3 && < 2.9   -- hs-source-dirs:   default-language:    Haskell2010