Modulefgl-arbitrary-0.2.0.6Haskell2010

Data.Graph.Inductive.Arbitrary

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.

7 types
1 class
9 values

Packagefgl-arbitrary-0.2.0.6
Exports17
LanguageHaskell2010
LicenceBSD-3-Clause
SourceArbitrary.hs

Explicit graph creation

4 declarations

If you wish to explicitly create a generated graph value (rather than using the Arbitrary class) then you will want to use these functions.

valuearbitraryGraph :: (Graph gr, Arbitrary a, Arbitrary b) => Gen (gr a b)

Generate an arbitrary graph. Multiple edges are allowed.

valuearbitraryGraphWith

:: (Graph gr, Arbitrary a, Arbitrary b)
=> [LEdge b] -> [LEdge b]
-> Gen (gr a b)

Generate an arbitrary graph, using the specified function to manipulate the generated list of edges (e.g. remove multiple edges).

valueshrinkGraph :: Graph gr => gr a b -> [gr a b]

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).

valueshrinkGraphWith :: Graph gr => gr a b -> [(Node, gr a b)]

As with shrinkGraph, but also return the node that was deleted.

Types of graphs

4 declarations

classclass DynGraph (BaseGraph ag) => ArbGraph (ag :: Type -> Type -> Type) where

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!).

Associated types

type family BaseGraph (ag :: Type -> Type -> Type) :: Type -> Type -> Type

Methods

toBaseGraph :: ag a b -> BaseGraph ag a b
fromBaseGraph :: BaseGraph ag a b -> ag a b
edgeF :: GrProxy ag -> [LEdge b] -> [LEdge b]
Any manipulation of edges that should be done to satisfy the requirements of the specified wrapper.
shrinkFWith :: ag a b -> [(Node, ag a b)]
Shrinking function (assuming only one node is removed at a time) which also returns the node that is removed.

Instances5ArbGraph

ArbGraph GrDefined in fgl-arbitrary-0.2.0.6 · Data.Graph.Inductive.Arbitrary
ArbGraph GrDefined in fgl-arbitrary-0.2.0.6 · Data.Graph.Inductive.Arbitrary
ArbGraph gr => ArbGraph (NoLoops gr)Defined in fgl-arbitrary-0.2.0.6 · Data.Graph.Inductive.Arbitrary
ArbGraph gr => ArbGraph (NoMultipleEdges gr)Defined in fgl-arbitrary-0.2.0.6 · Data.Graph.Inductive.Arbitrary
ArbGraph gr => ArbGraph (Undirected gr)Defined in fgl-arbitrary-0.2.0.6 · Data.Graph.Inductive.Arbitrary

datadata GrProxy (gr :: Type -> Type -> Type)

A simple graph-specific proxy type.

GrProxy

Instances4Eq, Ord, Read, Show

Eq (GrProxy gr)Defined in fgl-arbitrary-0.2.0.6 · Data.Graph.Inductive.Arbitrary
Ord (GrProxy gr)Defined in fgl-arbitrary-0.2.0.6 · Data.Graph.Inductive.Arbitrary
Read (GrProxy gr)Defined in fgl-arbitrary-0.2.0.6 · Data.Graph.Inductive.Arbitrary
Show (GrProxy gr)Defined in fgl-arbitrary-0.2.0.6 · Data.Graph.Inductive.Arbitrary

valueshrinkF :: ArbGraph ag => ag a b -> [ag a b]

In most cases, for an instance of ArbGraph the Arbitrary instance definition will/can have shrink = shrinkF.

valuearbitraryGraphBy :: (ArbGraph ag, Arbitrary a, Arbitrary b) => Gen (ag a b)

Generate an instance of ArbGraph using the class methods.

Specific graph structures

newtypenewtype NoMultipleEdges (gr :: Type -> Type -> Type) a b

A newtype wrapper to generate a graph without multiple edges (loops allowed).

Constructors

NME
- nmeGraph :: gr a b

Instances6ArbGraph, Eq, Read, Show, Arbitrary, BaseGraph

ArbGraph gr => ArbGraph (NoMultipleEdges gr)Defined in fgl-arbitrary-0.2.0.6 · Data.Graph.Inductive.Arbitrary
Eq (gr a b) => Eq (NoMultipleEdges gr a b)Defined in fgl-arbitrary-0.2.0.6 · Data.Graph.Inductive.Arbitrary
Read (gr a b) => Read (NoMultipleEdges gr a b)Defined in fgl-arbitrary-0.2.0.6 · Data.Graph.Inductive.Arbitrary
Show (gr a b) => Show (NoMultipleEdges gr a b)Defined in fgl-arbitrary-0.2.0.6 · Data.Graph.Inductive.Arbitrary
(ArbGraph gr, Arbitrary a, Arbitrary b) => Arbitrary (NoMultipleEdges gr a b)Defined in fgl-arbitrary-0.2.0.6 · Data.Graph.Inductive.Arbitrary
type BaseGraph (NoMultipleEdges gr) = BaseGraph grDefined in fgl-arbitrary-0.2.0.6 · Data.Graph.Inductive.Arbitrary

newtypenewtype NoLoops (gr :: Type -> Type -> Type) a b

A newtype wrapper to generate a graph without loops (multiple edges allowed).

Constructors

NL
- looplessGraph :: gr a b

Instances6ArbGraph, Eq, Read, Show, Arbitrary, BaseGraph

ArbGraph gr => ArbGraph (NoLoops gr)Defined in fgl-arbitrary-0.2.0.6 · Data.Graph.Inductive.Arbitrary
Eq (gr a b) => Eq (NoLoops gr a b)Defined in fgl-arbitrary-0.2.0.6 · Data.Graph.Inductive.Arbitrary
Read (gr a b) => Read (NoLoops gr a b)Defined in fgl-arbitrary-0.2.0.6 · Data.Graph.Inductive.Arbitrary
Show (gr a b) => Show (NoLoops gr a b)Defined in fgl-arbitrary-0.2.0.6 · Data.Graph.Inductive.Arbitrary
(ArbGraph gr, Arbitrary a, Arbitrary b) => Arbitrary (NoLoops gr a b)Defined in fgl-arbitrary-0.2.0.6 · Data.Graph.Inductive.Arbitrary
type BaseGraph (NoLoops gr) = BaseGraph grDefined in fgl-arbitrary-0.2.0.6 · Data.Graph.Inductive.Arbitrary

typetype SimpleGraph (gr :: Type -> Type -> Type) = NoLoops (NoMultipleEdges gr)

A wrapper to generate a graph without multiple edges and no loops.

newtypenewtype Undirected (gr :: Type -> Type -> Type) a b

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
- undirGraph :: gr a b

Instances6ArbGraph, Eq, Read, Show, Arbitrary, BaseGraph

ArbGraph gr => ArbGraph (Undirected gr)Defined in fgl-arbitrary-0.2.0.6 · Data.Graph.Inductive.Arbitrary
Eq (gr a b) => Eq (Undirected gr a b)Defined in fgl-arbitrary-0.2.0.6 · Data.Graph.Inductive.Arbitrary
Read (gr a b) => Read (Undirected gr a b)Defined in fgl-arbitrary-0.2.0.6 · Data.Graph.Inductive.Arbitrary
Show (gr a b) => Show (Undirected gr a b)Defined in fgl-arbitrary-0.2.0.6 · Data.Graph.Inductive.Arbitrary
(ArbGraph gr, Arbitrary a, Arbitrary b) => Arbitrary (Undirected gr a b)Defined in fgl-arbitrary-0.2.0.6 · Data.Graph.Inductive.Arbitrary
type BaseGraph (Undirected gr) = BaseGraph grDefined in fgl-arbitrary-0.2.0.6 · Data.Graph.Inductive.Arbitrary

Connected graphs

datadata Connected (ag :: Type -> Type -> Type) a b

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
- connNode :: Node
- connArbGraph :: ag a b

Instances4Eq, Read, Show, Arbitrary

Eq (ag a b) => Eq (Connected ag a b)Defined in fgl-arbitrary-0.2.0.6 · Data.Graph.Inductive.Arbitrary
Read (ag a b) => Read (Connected ag a b)Defined in fgl-arbitrary-0.2.0.6 · Data.Graph.Inductive.Arbitrary
Show (ag a b) => Show (Connected ag a b)Defined in fgl-arbitrary-0.2.0.6 · Data.Graph.Inductive.Arbitrary
(ArbGraph ag, Arbitrary a, Arbitrary b) => Arbitrary (Connected ag a b)Defined in fgl-arbitrary-0.2.0.6 · Data.Graph.Inductive.Arbitrary

valueconnGraph :: ArbGraph ag => Connected ag a b -> BaseGraph ag a b

The underlying graph represented by this Connected value.

Node and edge lists

3 declarations

valuearbitraryNodes :: Arbitrary a => Gen [LNode a]

Generally a list of labelled nodes.

valuearbitraryEdges :: Arbitrary b => [LNode a] -> Gen [LEdge b]

Given a specified list of nodes, generate a list of edges.

datadata GraphNodesEdges a b

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
- graphNodes :: [LNode a]
- graphEdges :: [LEdge b]

Instances5Eq, Ord, Read, Show, Arbitrary

(Eq a, Eq b) => Eq (GraphNodesEdges a b)Defined in fgl-arbitrary-0.2.0.6 · Data.Graph.Inductive.Arbitrary
(Ord a, Ord b) => Ord (GraphNodesEdges a b)Defined in fgl-arbitrary-0.2.0.6 · Data.Graph.Inductive.Arbitrary
(Read a, Read b) => Read (GraphNodesEdges a b)Defined in fgl-arbitrary-0.2.0.6 · Data.Graph.Inductive.Arbitrary
(Show a, Show b) => Show (GraphNodesEdges a b)Defined in fgl-arbitrary-0.2.0.6 · Data.Graph.Inductive.Arbitrary
(Arbitrary a, Arbitrary b) => Arbitrary (GraphNodesEdges a b)Defined in fgl-arbitrary-0.2.0.6 · Data.Graph.Inductive.Arbitrary

Orphan instances

2 instances

(Arbitrary a, Arbitrary b) => Arbitrary (Gr a b)
(Arbitrary a, Arbitrary b) => Arbitrary (Gr a b)