fgl-arbitrary-0.2.0.6: QuickCheck support for fgl

Copyright | (c) Ivan Lazar Miljenovic
License | BSD3
Maintainer | Ivan.Miljenovic@gmail.com
Safe Haskell | None
Language | Haskell2010

Data.Graph.Inductive.Arbitrary

Contents

- Explicit graph creation
- Types of graphs
  - Specific graph structures
  - Connected graphs
- Node and edge lists
- Orphan instances

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 :: Type -> Type -> Type) where
  - type BaseGraph (ag :: Type -> Type -> Type) :: Type -> Type -> Type
  - 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 :: Type -> Type -> Type) = GrProxy
- shrinkF :: ArbGraph ag => ag a b -> [ag a b]
- arbitraryGraphBy :: (ArbGraph ag, Arbitrary a, Arbitrary b) => Gen (ag a b)
- newtype NoMultipleEdges (gr :: Type -> Type -> Type) a b = NME {
  - nmeGraph :: gr a b
  }
- newtype NoLoops (gr :: Type -> Type -> Type) a b = NL {
  - looplessGraph :: gr a b
  }
- type SimpleGraph (gr :: Type -> Type -> Type) = NoLoops (NoMultipleEdges gr)
- newtype Undirected (gr :: Type -> Type -> Type) a b = UG {
  - undirGraph :: gr a b
  }
- data Connected (ag :: Type -> Type -> Type) a b = CG {
  - connNode :: Node
  - connArbGraph :: ag a b
  }
- connGraph :: forall (ag :: Type -> Type -> Type) a b. 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 :: Type -> Type -> Type) 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!).

Associated Types

type BaseGraph (ag :: Type -> Type -> Type) :: Type -> Type -> Type Source #

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

Instances details

ArbGraph Gr Source # |

Instance details

Defined in Data.Graph.Inductive.Arbitrary

Associated Types

type BaseGraph Gr |
Instance details Defined in Data.Graph.Inductive.Arbitrary type BaseGraph Gr = Gr

Methods

toBaseGraph :: Gr a b -> BaseGraph Gr a b Source #

fromBaseGraph :: BaseGraph Gr a b -> Gr a b Source #

edgeF :: GrProxy Gr -> [LEdge b] -> [LEdge b] Source #

shrinkFWith :: Gr a b -> [(Node, Gr a b)] Source #

ArbGraph Gr Source # |

Instance details

Defined in Data.Graph.Inductive.Arbitrary

Associated Types

type BaseGraph Gr |
Instance details Defined in Data.Graph.Inductive.Arbitrary type BaseGraph Gr = Gr

Methods

toBaseGraph :: Gr a b -> BaseGraph Gr a b Source #

fromBaseGraph :: BaseGraph Gr a b -> Gr a b Source #

edgeF :: GrProxy Gr -> [LEdge b] -> [LEdge b] Source #

shrinkFWith :: Gr a b -> [(Node, Gr a b)] Source #

ArbGraph gr => ArbGraph (NoLoops gr) Source # |

Instance details

Defined in Data.Graph.Inductive.Arbitrary

Associated Types

type BaseGraph (NoLoops gr) |
Instance details Defined in Data.Graph.Inductive.Arbitrary type BaseGraph (NoLoops gr) = BaseGraph gr

Methods

toBaseGraph :: NoLoops gr a b -> BaseGraph (NoLoops gr) a b Source #

fromBaseGraph :: BaseGraph (NoLoops gr) a b -> NoLoops gr a b Source #

edgeF :: GrProxy (NoLoops gr) -> [LEdge b] -> [LEdge b] Source #

shrinkFWith :: NoLoops gr a b -> [(Node, NoLoops gr a b)] Source #

ArbGraph gr => ArbGraph (NoMultipleEdges gr) Source # |

Instance details

Defined in Data.Graph.Inductive.Arbitrary

Associated Types

type BaseGraph (NoMultipleEdges gr) |
Instance details Defined in Data.Graph.Inductive.Arbitrary type BaseGraph (NoMultipleEdges gr) = BaseGraph gr

Methods

toBaseGraph :: NoMultipleEdges gr a b -> BaseGraph (NoMultipleEdges gr) a b Source #

fromBaseGraph :: BaseGraph (NoMultipleEdges gr) a b -> NoMultipleEdges gr a b Source #

edgeF :: GrProxy (NoMultipleEdges gr) -> [LEdge b] -> [LEdge b] Source #

shrinkFWith :: NoMultipleEdges gr a b -> [(Node, NoMultipleEdges gr a b)] Source #

ArbGraph gr => ArbGraph (Undirected gr) Source # |

Instance details

Defined in Data.Graph.Inductive.Arbitrary

Associated Types

type BaseGraph (Undirected gr) |
Instance details Defined in Data.Graph.Inductive.Arbitrary type BaseGraph (Undirected gr) = BaseGraph gr

Methods

toBaseGraph :: Undirected gr a b -> BaseGraph (Undirected gr) a b Source #

fromBaseGraph :: BaseGraph (Undirected gr) a b -> Undirected gr a b Source #

edgeF :: GrProxy (Undirected gr) -> [LEdge b] -> [LEdge b] Source #

shrinkFWith :: Undirected gr a b -> [(Node, Undirected gr a b)] Source #

data GrProxy (gr :: Type -> Type -> Type) Source #

A simple graph-specific proxy type.

Constructors

GrProxy |

#### Instances

Instances details

Read (GrProxy gr) Source # |
Instance details Defined in Data.Graph.Inductive.Arbitrary Methods readsPrec :: Int -> ReadS (GrProxy gr) Source # readList :: ReadS [GrProxy gr] Source # readPrec :: ReadPrec (GrProxy gr) Source # readListPrec :: ReadPrec [GrProxy gr] Source #
Show (GrProxy gr) Source # |
Instance details Defined in Data.Graph.Inductive.Arbitrary Methods showsPrec :: Int -> GrProxy gr -> ShowS Source # show :: GrProxy gr -> String Source # showList :: [GrProxy gr] -> ShowS Source #
Eq (GrProxy gr) Source # |
Instance details Defined in Data.Graph.Inductive.Arbitrary Methods (==) :: GrProxy gr -> GrProxy gr -> Bool Source # (/=) :: GrProxy gr -> GrProxy gr -> Bool Source #
Ord (GrProxy gr) Source # |

Instance details

Defined in Data.Graph.Inductive.Arbitrary

Methods

compare :: GrProxy gr -> GrProxy gr -> Ordering Source #

(<) :: GrProxy gr -> GrProxy gr -> Bool Source #

(<=) :: GrProxy gr -> GrProxy gr -> Bool Source #

(>) :: GrProxy gr -> GrProxy gr -> Bool Source #

(>=) :: GrProxy gr -> GrProxy gr -> Bool Source #

max :: GrProxy gr -> GrProxy gr -> GrProxy gr Source #

min :: GrProxy gr -> GrProxy gr -> 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 :: (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 :: Type -> Type -> Type) a b Source #

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

Constructors

NME |

Fields

- nmeGraph :: gr a b

#### Instances

Instances details

ArbGraph gr => ArbGraph (NoMultipleEdges gr) Source # |

Instance details

Defined in Data.Graph.Inductive.Arbitrary

Associated Types

type BaseGraph (NoMultipleEdges gr) |
Instance details Defined in Data.Graph.Inductive.Arbitrary type BaseGraph (NoMultipleEdges gr) = BaseGraph gr

Methods

toBaseGraph :: NoMultipleEdges gr a b -> BaseGraph (NoMultipleEdges gr) a b Source #

fromBaseGraph :: BaseGraph (NoMultipleEdges gr) a b -> NoMultipleEdges gr a b Source #

edgeF :: GrProxy (NoMultipleEdges gr) -> [LEdge b] -> [LEdge b] Source #

shrinkFWith :: NoMultipleEdges gr a b -> [(Node, NoMultipleEdges gr a b)] Source #

(ArbGraph gr, Arbitrary a, Arbitrary b) => Arbitrary (NoMultipleEdges gr a b) Source # |
Instance details Defined in Data.Graph.Inductive.Arbitrary Methods arbitrary :: Gen (NoMultipleEdges gr a b) Source # shrink :: NoMultipleEdges gr a b -> [NoMultipleEdges gr a b] Source #
Read (gr a b) => Read (NoMultipleEdges gr a b) Source # |
Instance details Defined in Data.Graph.Inductive.Arbitrary Methods readsPrec :: Int -> ReadS (NoMultipleEdges gr a b) Source # readList :: ReadS [NoMultipleEdges gr a b] Source # readPrec :: ReadPrec (NoMultipleEdges gr a b) Source # readListPrec :: ReadPrec [NoMultipleEdges gr a b] Source #
Show (gr a b) => Show (NoMultipleEdges gr a b) Source # |
Instance details Defined in Data.Graph.Inductive.Arbitrary Methods showsPrec :: Int -> NoMultipleEdges gr a b -> ShowS Source # show :: NoMultipleEdges gr a b -> String Source # showList :: [NoMultipleEdges gr a b] -> ShowS Source #
Eq (gr a b) => Eq (NoMultipleEdges gr a b) Source # |
Instance details Defined in Data.Graph.Inductive.Arbitrary Methods (==) :: NoMultipleEdges gr a b -> NoMultipleEdges gr a b -> Bool Source # (/=) :: NoMultipleEdges gr a b -> NoMultipleEdges gr a b -> Bool Source #
type BaseGraph (NoMultipleEdges gr) Source # |
Instance details Defined in Data.Graph.Inductive.Arbitrary type BaseGraph (NoMultipleEdges gr) = BaseGraph gr

newtype NoLoops (gr :: Type -> Type -> Type) a b Source #

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

Constructors

NL |

Fields

- looplessGraph :: gr a b

#### Instances

Instances details

ArbGraph gr => ArbGraph (NoLoops gr) Source # |

Instance details

Defined in Data.Graph.Inductive.Arbitrary

Associated Types

type BaseGraph (NoLoops gr) |
Instance details Defined in Data.Graph.Inductive.Arbitrary type BaseGraph (NoLoops gr) = BaseGraph gr

Methods

toBaseGraph :: NoLoops gr a b -> BaseGraph (NoLoops gr) a b Source #

fromBaseGraph :: BaseGraph (NoLoops gr) a b -> NoLoops gr a b Source #

edgeF :: GrProxy (NoLoops gr) -> [LEdge b] -> [LEdge b] Source #

shrinkFWith :: NoLoops gr a b -> [(Node, NoLoops gr a b)] Source #

(ArbGraph gr, Arbitrary a, Arbitrary b) => Arbitrary (NoLoops gr a b) Source # |
Instance details Defined in Data.Graph.Inductive.Arbitrary Methods arbitrary :: Gen (NoLoops gr a b) Source # shrink :: NoLoops gr a b -> [NoLoops gr a b] Source #
Read (gr a b) => Read (NoLoops gr a b) Source # |
Instance details Defined in Data.Graph.Inductive.Arbitrary Methods readsPrec :: Int -> ReadS (NoLoops gr a b) Source # readList :: ReadS [NoLoops gr a b] Source # readPrec :: ReadPrec (NoLoops gr a b) Source # readListPrec :: ReadPrec [NoLoops gr a b] Source #
Show (gr a b) => Show (NoLoops gr a b) Source # |
Instance details Defined in Data.Graph.Inductive.Arbitrary Methods showsPrec :: Int -> NoLoops gr a b -> ShowS Source # show :: NoLoops gr a b -> String Source # showList :: [NoLoops gr a b] -> ShowS Source #
Eq (gr a b) => Eq (NoLoops gr a b) Source # |
Instance details Defined in Data.Graph.Inductive.Arbitrary Methods (==) :: NoLoops gr a b -> NoLoops gr a b -> Bool Source # (/=) :: NoLoops gr a b -> NoLoops gr a b -> Bool Source #
type BaseGraph (NoLoops gr) Source # |
Instance details Defined in Data.Graph.Inductive.Arbitrary type BaseGraph (NoLoops gr) = BaseGraph gr

type SimpleGraph (gr :: Type -> Type -> Type) = NoLoops (NoMultipleEdges gr) Source #

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

newtype Undirected (gr :: Type -> Type -> Type) 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

- undirGraph :: gr a b

#### Instances

Instances details

ArbGraph gr => ArbGraph (Undirected gr) Source # |

Instance details

Defined in Data.Graph.Inductive.Arbitrary

Associated Types

type BaseGraph (Undirected gr) |
Instance details Defined in Data.Graph.Inductive.Arbitrary type BaseGraph (Undirected gr) = BaseGraph gr

Methods

toBaseGraph :: Undirected gr a b -> BaseGraph (Undirected gr) a b Source #

fromBaseGraph :: BaseGraph (Undirected gr) a b -> Undirected gr a b Source #

edgeF :: GrProxy (Undirected gr) -> [LEdge b] -> [LEdge b] Source #

shrinkFWith :: Undirected gr a b -> [(Node, Undirected gr a b)] Source #

(ArbGraph gr, Arbitrary a, Arbitrary b) => Arbitrary (Undirected gr a b) Source # |
Instance details Defined in Data.Graph.Inductive.Arbitrary Methods arbitrary :: Gen (Undirected gr a b) Source # shrink :: Undirected gr a b -> [Undirected gr a b] Source #
Read (gr a b) => Read (Undirected gr a b) Source # |
Instance details Defined in Data.Graph.Inductive.Arbitrary Methods readsPrec :: Int -> ReadS (Undirected gr a b) Source # readList :: ReadS [Undirected gr a b] Source # readPrec :: ReadPrec (Undirected gr a b) Source # readListPrec :: ReadPrec [Undirected gr a b] Source #
Show (gr a b) => Show (Undirected gr a b) Source # |
Instance details Defined in Data.Graph.Inductive.Arbitrary Methods showsPrec :: Int -> Undirected gr a b -> ShowS Source # show :: Undirected gr a b -> String Source # showList :: [Undirected gr a b] -> ShowS Source #
Eq (gr a b) => Eq (Undirected gr a b) Source # |
Instance details Defined in Data.Graph.Inductive.Arbitrary Methods (==) :: Undirected gr a b -> Undirected gr a b -> Bool Source # (/=) :: Undirected gr a b -> Undirected gr a b -> Bool Source #
type BaseGraph (Undirected gr) Source # |
Instance details Defined in Data.Graph.Inductive.Arbitrary type BaseGraph (Undirected gr) = BaseGraph gr

## Connected graphs

data Connected (ag :: Type -> Type -> Type) 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

- connNode :: Node
- connArbGraph :: ag a b

#### Instances

Instances details

(ArbGraph ag, Arbitrary a, Arbitrary b) => Arbitrary (Connected ag a b) Source # |
Instance details Defined in Data.Graph.Inductive.Arbitrary Methods arbitrary :: Gen (Connected ag a b) Source # shrink :: Connected ag a b -> [Connected ag a b] Source #
Read (ag a b) => Read (Connected ag a b) Source # |
Instance details Defined in Data.Graph.Inductive.Arbitrary Methods readsPrec :: Int -> ReadS (Connected ag a b) Source # readList :: ReadS [Connected ag a b] Source # readPrec :: ReadPrec (Connected ag a b) Source # readListPrec :: ReadPrec [Connected ag a b] Source #
Show (ag a b) => Show (Connected ag a b) Source # |
Instance details Defined in Data.Graph.Inductive.Arbitrary Methods showsPrec :: Int -> Connected ag a b -> ShowS Source # show :: Connected ag a b -> String Source # showList :: [Connected ag a b] -> ShowS Source #
Eq (ag a b) => Eq (Connected ag a b) Source # |
Instance details Defined in Data.Graph.Inductive.Arbitrary Methods (==) :: Connected ag a b -> Connected ag a b -> Bool Source # (/=) :: Connected ag a b -> Connected ag a b -> Bool Source #

connGraph :: forall (ag :: Type -> Type -> Type) a b. 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

- graphNodes :: [LNode a]
- graphEdges :: [LEdge b]

#### Instances

Instances details

(Arbitrary a, Arbitrary b) => Arbitrary (GraphNodesEdges a b) Source # |
Instance details Defined in Data.Graph.Inductive.Arbitrary Methods arbitrary :: Gen (GraphNodesEdges a b) Source # shrink :: GraphNodesEdges a b -> [GraphNodesEdges a b] Source #
(Read a, Read b) => Read (GraphNodesEdges a b) Source # |
Instance details Defined in Data.Graph.Inductive.Arbitrary Methods readsPrec :: Int -> ReadS (GraphNodesEdges a b) Source # readList :: ReadS [GraphNodesEdges a b] Source # readPrec :: ReadPrec (GraphNodesEdges a b) Source # readListPrec :: ReadPrec [GraphNodesEdges a b] Source #
(Show a, Show b) => Show (GraphNodesEdges a b) Source # |
Instance details Defined in Data.Graph.Inductive.Arbitrary Methods showsPrec :: Int -> GraphNodesEdges a b -> ShowS Source # show :: GraphNodesEdges a b -> String Source # showList :: [GraphNodesEdges a b] -> ShowS Source #
(Eq a, Eq b) => Eq (GraphNodesEdges a b) Source # |
Instance details Defined in Data.Graph.Inductive.Arbitrary Methods (==) :: GraphNodesEdges a b -> GraphNodesEdges a b -> Bool Source # (/=) :: GraphNodesEdges a b -> GraphNodesEdges a b -> Bool Source #
(Ord a, Ord b) => Ord (GraphNodesEdges a b) Source # |

Instance details

Defined in Data.Graph.Inductive.Arbitrary

Methods

compare :: GraphNodesEdges a b -> GraphNodesEdges a b -> Ordering Source #

(<) :: GraphNodesEdges a b -> GraphNodesEdges a b -> Bool Source #

(<=) :: GraphNodesEdges a b -> GraphNodesEdges a b -> Bool Source #

(>) :: GraphNodesEdges a b -> GraphNodesEdges a b -> Bool Source #

(>=) :: GraphNodesEdges a b -> GraphNodesEdges a b -> Bool Source #

max :: GraphNodesEdges a b -> GraphNodesEdges a b -> GraphNodesEdges a b Source #

min :: GraphNodesEdges a b -> GraphNodesEdges a b -> GraphNodesEdges a b Source #

# Orphan instances

(Arbitrary a, Arbitrary b) => Arbitrary (Gr a b) Source # |
Instance details Methods arbitrary :: Gen (Gr a b) Source # shrink :: Gr a b -> [Gr a b] Source #
(Arbitrary a, Arbitrary b) => Arbitrary (Gr a b) Source # |
Instance details Methods arbitrary :: Gen (Gr a b) Source # shrink :: Gr a b -> [Gr a b] Source #