| Copyright | (c) Ivan Lazar Miljenovic |
|---|---|
| License | BSD3 |
| Maintainer | Ivan.Miljenovic@gmail.com |
| Safe Haskell | None |
| Language | Haskell2010 |
Data.Graph.Inductive.Arbitrary
Description
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.
Synopsis
- 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!).
Methods
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.
Instances
data GrProxy (gr :: * -> * -> *) Source #
A simple graph-specific proxy type.
Constructors
| GrProxy |
Instances
| Eq (GrProxy gr) Source # | |
| Ord (GrProxy gr) Source # | |
| Read (GrProxy gr) Source # | |
Defined in Data.Graph.Inductive.Arbitrary | |
| Show (GrProxy gr) Source # | |
shrinkF :: ArbGraph ag => ag a b -> [ag a b] Source #
In most cases, for an instance of ArbGraph the Arbitrary
instance definition will/can have shrink = shrinkF.
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).
Instances
newtype NoLoops gr a b Source #
A newtype wrapper to generate a graph without loops (multiple edges allowed).
Constructors
| NL | |
Fields
| |
Instances
| ArbGraph gr => ArbGraph (NoLoops gr) Source # | |
Defined in Data.Graph.Inductive.Arbitrary | |
| Eq (gr a b) => Eq (NoLoops gr a b) Source # | |
| Read (gr a b) => Read (NoLoops gr a b) Source # | |
Defined in Data.Graph.Inductive.Arbitrary | |
| Show (gr a b) => Show (NoLoops gr a b) Source # | |
| (ArbGraph gr, Arbitrary a, Arbitrary b) => Arbitrary (NoLoops gr a b) Source # | |
| type BaseGraph (NoLoops gr) Source # | |
Defined in Data.Graph.Inductive.Arbitrary | |
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.
Constructors
| UG | |
Fields
| |
Instances
Connected graphs
data Connected ag a b Source #
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.
Constructors
| CG | |
Fields
| |
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.
Constructors
| GNEs | |
Fields
| |