RandomCompositionGraph.RandomCompositionGraph

This module provide functions to generate randomly composition graphs. It is an easy and fast way to generate a lot of finite categories. It can be used to test functions, to generate examples or to test hypothesis.

Documentation

mkRandomCompositionGraph

Arguments

:: RandomGen g

=> Int

Number of arrows of the random composition graph.

-> Int

Number of monoidification attempts, a bigger number will produce more morphisms that will compose but the function will be slower.

-> Int

Perseverance : how much we pursure an attempt far away to find a law that works, a bigger number will make the attemps more successful, but slower. (When in doubt put 4.)

-> g

Random generator.

-> (CompositionGraph Int Int, g)

Generates a random composition graph.

We use the fact that a category is a generalized monoid.

We try to create a composition law of a monoid greedily.

To get a category, we begin with a category with all arrows seperated and not composing with each other. It is equivalent to the monoid with an empty composition law.

Then, a monoidification attempt is the following algorihm :

1. Pick two objects, merge them.
2. While there are composite morphisms, try to merge them with generating arrows.
3. If it fails, don't change the composition graph.
4. Else return the new composition graph

A monoidification attempt takes a valid category and outputs a valid category, furthermore, the number of arrows is constant and the number of objects is decreasing (not strictly).

defaultMkRandomCompositionGraph :: RandomGen g => g -> (CompositionGraph Int Int, g)

Creates a random composition graph with default random values.

The number of arrows will be in the interval [1, 20].