Copyright | (c) Ivan Lazar Miljenovic |
---|---|
License | BSD3 |
Maintainer | Ivan.Miljenovic@gmail.com |
Safe Haskell | None |
Language | Haskell2010 |
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.
- arbitraryGraph :: (Graph gr, Arbitrary a, Arbitrary b) => Gen (gr a b)
- arbitraryGraphWith :: (Graph gr, Arbitrary a, Arbitrary b) => ([LEdge b] -> [LEdge b]) -> Gen (gr a b)
- shrinkGraph :: Graph gr => gr a b -> [gr a b]
- shrinkGraphWith :: Graph gr => gr a b -> [(Node, gr a b)]
- class DynGraph (BaseGraph ag) => ArbGraph ag where
- type BaseGraph ag :: * -> * -> *
- toBaseGraph :: ag a b -> BaseGraph ag a b
- fromBaseGraph :: BaseGraph ag a b -> ag a b
- edgeF :: GrProxy ag -> [LEdge b] -> [LEdge b]
- shrinkFWith :: ag a b -> [(Node, ag a b)]
- data GrProxy gr = GrProxy
- shrinkF :: ArbGraph ag => ag a b -> [ag a b]
- arbitraryGraphBy :: forall ag a b. (ArbGraph ag, Arbitrary a, Arbitrary b) => Gen (ag a b)
- newtype NoMultipleEdges gr a b = NME {
- nmeGraph :: gr a b
- newtype NoLoops gr a b = NL {
- looplessGraph :: gr a b
- type SimpleGraph gr = NoLoops (NoMultipleEdges gr)
- newtype Undirected gr a b = UG {
- undirGraph :: gr a b
- data Connected ag a b = CG {
- connNode :: Node
- connArbGraph :: ag a b
- connGraph :: ArbGraph ag => Connected ag a b -> BaseGraph ag a b
- arbitraryNodes :: Arbitrary a => Gen [LNode a]
- arbitraryEdges :: Arbitrary b => [LNode a] -> Gen [LEdge b]
- data GraphNodesEdges a b = GNEs {
- graphNodes :: [LNode a]
- graphEdges :: [LEdge b]
Explicit graph creation
If you wish to explicitly create a generated graph value (rather than
using the Arbitrary
class) then you will want to use these
functions.
arbitraryGraph :: (Graph gr, Arbitrary a, Arbitrary b) => Gen (gr a b) Source
Generate an arbitrary graph. Multiple edges are allowed.
arbitraryGraphWith :: (Graph gr, Arbitrary a, Arbitrary b) => ([LEdge b] -> [LEdge b]) -> Gen (gr a b) Source
Generate an arbitrary graph, using the specified function to manipulate the generated list of edges (e.g. remove multiple edges).
shrinkGraph :: Graph gr => gr a b -> [gr a b] Source
For a graph with at least two nodes, return every possible way of deleting a single node (i.e. will never shrink to an empty graph).
shrinkGraphWith :: Graph gr => gr a b -> [(Node, gr a b)] Source
As with shrinkGraph
, but also return the node that was deleted.
Types of graphs
class DynGraph (BaseGraph ag) => ArbGraph ag where Source
Representation of generating arbitrary graph structures.
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!).
toBaseGraph :: ag a b -> BaseGraph ag a b Source
fromBaseGraph :: BaseGraph ag a b -> ag a b Source
edgeF :: GrProxy ag -> [LEdge b] -> [LEdge b] Source
Any manipulation of edges that should be done to satisfy the requirements of the specified wrapper.
shrinkFWith :: ag a b -> [(Node, ag a b)] Source
Shrinking function (assuming only one node is removed at a time) which also returns the node that is removed.
A simple graph-specific proxy type.
arbitraryGraphBy :: forall ag a b. (ArbGraph ag, Arbitrary a, Arbitrary b) => Gen (ag a b) Source
Generate an instance of ArbGraph
using the class methods.
Specific graph structures
newtype NoMultipleEdges gr a b Source
A newtype wrapper to generate a graph without multiple edges (loops allowed).
ArbGraph gr => ArbGraph (NoMultipleEdges gr) | |
Eq (gr a b) => Eq (NoMultipleEdges gr a b) | |
Read (gr a b) => Read (NoMultipleEdges gr a b) | |
Show (gr a b) => Show (NoMultipleEdges gr a b) | |
(ArbGraph gr, Arbitrary a, Arbitrary b) => Arbitrary (NoMultipleEdges gr a b) | |
type BaseGraph (NoMultipleEdges gr) = BaseGraph gr |
A newtype wrapper to generate a graph without loops (multiple edges allowed).
NL | |
|
type SimpleGraph gr = NoLoops (NoMultipleEdges gr) Source
A wrapper to generate a graph without multiple edges and no loops.
newtype Undirected gr a b Source
A newtype wrapper such that each (non-loop) edge also has its reverse in the graph.
Note that there is no way to guarantee this after any additional edges are added or removed.
You should also apply this wrapper after NoMultipleEdges
or
else the wrong reverse edge might be removed.
UG | |
|
ArbGraph gr => ArbGraph (Undirected gr) | |
Eq (gr a b) => Eq (Undirected gr a b) | |
Read (gr a b) => Read (Undirected gr a b) | |
Show (gr a b) => Show (Undirected gr a b) | |
(ArbGraph gr, Arbitrary a, Arbitrary b) => Arbitrary (Undirected gr a b) | |
type BaseGraph (Undirected gr) = BaseGraph gr |
Connected graphs
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.
CG | |
|
connGraph :: ArbGraph ag => Connected ag a b -> BaseGraph ag a b Source
The underlying graph represented by this Connected
value.
Node and edge lists
arbitraryNodes :: Arbitrary a => Gen [LNode a] Source
Generally a list of labelled nodes.
arbitraryEdges :: Arbitrary b => [LNode a] -> Gen [LEdge b] Source
Given a specified list of nodes, generate a list of edges.
data GraphNodesEdges a b Source
Defined so as to be able to generate valid arbitrary
node and
edge lists.
If any specific structure (no multiple edges, no loops, etc.) is
required then you will need to post-process this after generating
it, or else create a new instance of ArbGraph
.
GNEs | |
|
(Eq a, Eq b) => Eq (GraphNodesEdges a b) | |
(Ord a, Ord b) => Ord (GraphNodesEdges a b) | |
(Read a, Read b) => Read (GraphNodesEdges a b) | |
(Show a, Show b) => Show (GraphNodesEdges a b) | |
(Arbitrary a, Arbitrary b) => Arbitrary (GraphNodesEdges a b) |