Math.FiniteCategories.CompositionGraph

A CompositionGraph is the free category generated by a multidigraph quotiented by an equivalence relation on the paths of the graphs. A multidigraph is a directed multigraph which means that edges are oriented and there can be multiple arrows between two objects.

The equivalence relation is given by a map on paths of the graph.

Morphisms from different composition graphs should not be composed or compared, if they are, the behavior is undefined.

When taking subcategories of a composition graph, the composition law might lead to morphisms not existing anymore. It is not a problem because they are equivalent, it is only counterintuitive for human readability.

Types for composition graph morphism

type RawPath a b = [Arrow a b]

A RawPath is a list of arrows, arrows should be compatible.

type Path a b = (a, RawPath a b)

A Path is a RawPath with a source specified.

An empty path is an identity in a free category. Therefore, it is useful to keep the source when the path is empty because there is one identity for each node of the graph. (We need to differentiate identites for each node.)

data CGMorphism a b

The datatype CGMorphism is the type of composition graph morphisms.

It is a path with a composition law, it is necessary to keep the composition law of the composition graph in every morphism of the graph because we need it to compose two morphisms and the morphisms compose independently of the composition graph.

Constructors

CGMorphism

Fields

• path :: Path a b
• compositionLaw :: CompositionLaw a b

Instances

(Eq a, Eq b) => Eq (CGMorphism a b)

Defined in Math.FiniteCategories.CompositionGraph

Methods

(==) :: CGMorphism a b -> CGMorphism a b -> Bool

(/=) :: CGMorphism a b -> CGMorphism a b -> Bool

(Show a, Show b) => Show (CGMorphism a b)

Defined in Math.FiniteCategories.CompositionGraph

Methods

showsPrec :: Int -> CGMorphism a b -> ShowS

show :: CGMorphism a b -> String

showList :: [CGMorphism a b] -> ShowS

(PrettyPrint a, PrettyPrint b, Eq a, Eq b) => PrettyPrint (CGMorphism a b)

Defined in Math.FiniteCategories.CompositionGraph

Methods

pprint :: CGMorphism a b -> String

(Eq a, Eq b) => Morphism (CGMorphism a b) a

Defined in Math.FiniteCategories.CompositionGraph

Methods

(@?) :: CGMorphism a b -> CGMorphism a b -> Maybe (CGMorphism a b)

source :: CGMorphism a b -> a

target :: CGMorphism a b -> a

(Eq a, Eq b) => Category (CompositionGraph a b) (CGMorphism a b) a

Defined in Math.FiniteCategories.CompositionGraph

Methods

identity :: CompositionGraph a b -> a -> CGMorphism a b

ar :: CompositionGraph a b -> a -> a -> Set (CGMorphism a b)

genAr :: CompositionGraph a b -> a -> a -> Set (CGMorphism a b)

decompose :: CompositionGraph a b -> CGMorphism a b -> [CGMorphism a b]

(Eq a, Eq b) => FiniteCategory (CompositionGraph a b) (CGMorphism a b) a

Defined in Math.FiniteCategories.CompositionGraph

Methods

ob :: CompositionGraph a b -> Set a

Functions for composition graph morphism

getLabel :: CGMorphism a b -> Maybe b

Return the label of a CompositionGraph generator.

Composition graph

type CompositionLaw a b = Map (RawPath a b) (RawPath a b)

A CompositionLaw is a Map that maps raw paths to smaller raw paths in order to simplify paths so that they don't compose infinitely many times when there is a cycle.

length (law |!| p) <= length p

data CompositionGraph a b

A CompositionGraph is a graph with a composition law such that the free category generated by the graph quotiented out by the composition law gives a FiniteCategory.

CompositionGraph is private, use the smart constructors compositionGraph or unsafeCompositionGraph to instantiate one.

Instances

(Eq a, Eq b) => Eq (CompositionGraph a b)

Defined in Math.FiniteCategories.CompositionGraph

Methods

(==) :: CompositionGraph a b -> CompositionGraph a b -> Bool

(/=) :: CompositionGraph a b -> CompositionGraph a b -> Bool

(Show a, Show b) => Show (CompositionGraph a b)

Defined in Math.FiniteCategories.CompositionGraph

Methods

showsPrec :: Int -> CompositionGraph a b -> ShowS

show :: CompositionGraph a b -> String

showList :: [CompositionGraph a b] -> ShowS

(PrettyPrint a, PrettyPrint b, Eq a, Eq b) => PrettyPrint (CompositionGraph a b)

Defined in Math.FiniteCategories.CompositionGraph

Methods

pprint :: CompositionGraph a b -> String

(Eq a, Eq b) => Category (CompositionGraph a b) (CGMorphism a b) a

Defined in Math.FiniteCategories.CompositionGraph

Methods

identity :: CompositionGraph a b -> a -> CGMorphism a b

ar :: CompositionGraph a b -> a -> a -> Set (CGMorphism a b)

genAr :: CompositionGraph a b -> a -> a -> Set (CGMorphism a b)

decompose :: CompositionGraph a b -> CGMorphism a b -> [CGMorphism a b]

(Eq a, Eq b) => FiniteCategory (CompositionGraph a b) (CGMorphism a b) a

Defined in Math.FiniteCategories.CompositionGraph

Methods

ob :: CompositionGraph a b -> Set a

support :: CompositionGraph a b -> Graph a b

The generating graph (or support) of the composition graph.

law :: CompositionGraph a b -> CompositionLaw a b

The composition law of the composition graph.

Construction

compositionGraph :: (Eq a, Eq b) => Graph a b -> CompositionLaw a b -> Either (FiniteCategoryError (CGMorphism a b) a) (CompositionGraph a b)

Smart constructor of CompositionGraph.

If the CompositionGraph constructed is valid, return Right the composition graph, otherwise return Left a FiniteCategoryError.

unsafeCompositionGraph :: Graph a b -> CompositionLaw a b -> CompositionGraph a b

Unsafe constructor of CompositionGraph for performance purposes. It does not check the structure of the CompositionGraph.

Use this constructor only if the CompositionGraph is necessarily well formed.

emptyCompositionGraph :: CompositionGraph a b

The empty CompositionGraph.

finiteCategoryToCompositionGraph :: (FiniteCategory c m o, Morphism m o, Eq m, Eq o) => c -> Diagram c m o (CompositionGraph o m) (CGMorphism o m) o

Transforms any FiniteCategory into a CompositionGraph.

The CompositionGraph will take more space in memory compared to the original category because the composition law is stored as a Map.

Returns an isofunctor as a Diagram from the original category to the created CompositionGraph.

If you only want the CompositionGraph, take the tgt of the Diagram.

unsafeReadCGString :: String -> CG

Unsafe version of readCGString which does not check the structure of the result CompositionGraph.

readCGString :: String -> Either (FiniteCategoryError (CGMorphism Text Text) Text) CG

Read a .cg string to create a CompositionGraph.

A .cg string follows the following rules :

1. Every character of a line following a "#" character are ignored.
2. Each line defines either an object, a morphism or a composition law entry.
3. The following strings are reserved : " -","-> "," = ", "<ID>", "<SRC>", "<SRC>", "<TGT>", "</TGT>", " => "
4. To define an object, write a line containing its name.
5. To define an arrow, the syntax "source_object -name_of_morphism-> target_object" is used, where "source_object", "target_object" and "name_of_morphism" should be replaced.
6. 1. If an object mentionned in an arrow does not exist, it is created.
7. 2. The spaces are important.
8. To define a composition law entry, the syntax "source_object1 -name_of_first_morphism-> middle_object -name_of_second_morphism-> target_object1 = source_object2 -name_of_composite_morphism-> target_object2" is used, where "source_object1", "name_of_first_morphism", "middle_object", "name_of_second_morphism", "target_object1", "source_object2", "name_of_composite_morphism", "target_object2" should be replaced.
9. 1 If an object mentionned does not exist, it is created.
10. 2 If a morphism mentionned does not exist, it is created.
11. 3 You can use the tag <ID/> in order to map a morphism to an identity.

unsafeReadCGFile :: String -> IO CG

Unsafe version of readCGFile which does not check the structure of the resulting CompositionGraph.

readCGFile :: String -> IO (Either (FiniteCategoryError (CGMorphism Text Text) Text) CG)

Read a .cg file to create a CompositionGraph.

A .cg file follows the following rules :

1. Every character of a line following a "#" character are ignored.
2. Each line defines either an object, a morphism or a composition law entry.
3. The following strings are reserved : " -","-> "," = ", "<ID>", "<SRC>", "<SRC>", "<TGT>", "</TGT>", " => "
4. To define an object, write a line containing its name.
5. To define an arrow, the syntax "source_object -name_of_morphism-> target_object" is used, where "source_object", "target_object" and "name_of_morphism" should be replaced.
6. 1. If an object mentionned in an arrow does not exist, it is created.
7. 2. The spaces are important.
8. To define a composition law entry, the syntax "source_object1 -name_of_first_morphism-> middle_object -name_of_second_morphism-> target_object1 = source_object2 -name_of_composite_morphism-> target_object2" is used, where "source_object1", "name_of_first_morphism", "middle_object", "name_of_second_morphism", "target_object1", "source_object2", "name_of_composite_morphism", "target_object2" should be replaced.
9. 1 If an object mentionned does not exist, it is created.
10. 2 If a morphism mentionned does not exist, it is created.
11. 3 You can use the tag <ID/> in order to map a morphism to an identity.

Serialization

writeCGString :: (PrettyPrint a, PrettyPrint b, Eq a, Eq b) => CompositionGraph a b -> String

Transform a composition graph into a string following the .cg convention.

writeCGFile :: (PrettyPrint a, PrettyPrint b, Eq a, Eq b) => CompositionGraph a b -> String -> IO ()

Saves a composition graph into a file located at a given path.

Construction of diagrams

unsafeReadCGDString :: String -> CGD

Unsafe version of readCGDString which does not check the structure of the resulting Diagram.

readCGDString :: String -> Either (DiagramError CG (CGMorphism Text Text) Text CG (CGMorphism Text Text) Text) CGD

Read a .cgd string and returns a diagram. A .cgd string obeys the following rules :

1. There is a line "<SRC>" and a line "</SRC>".
2. 1 Between these two lines, the source composition graph is defined as in a cg file.
3. There is a line "<TGT>" and a line "</TGT>".
4. 1 Between these two lines, the target composition graph is defined as in a cg file.
5. Outside of the two previously described sections, you can declare the maps between objects and morphisms.
6. 1 You map an object to another with the following syntax : "object1 => object2".
7. 2 You map a morphism to another with the following syntax : "objSrc1 -arrowSrc1-> objSrc2 => objTgt1 -arrowTgt1-> objTgt2".
8. You don't have to (and you shouldn't) specify maps from identities, nor maps from composite arrows.

unsafeReadCGDFile :: String -> IO CGD

Unsafe version readCGDFile which does not check the structure of the resulting Diagram.

readCGDFile :: String -> IO (Either (DiagramError CG (CGMorphism Text Text) Text CG (CGMorphism Text Text) Text) CGD)

Read a .cgd file and returns a diagram. A .cgd file obeys the following rules :

1. There is a line "<SRC>" and a line "</SRC>".
2. 1 Between these two lines, the source composition graph is defined as in a cg file.
3. There is a line "<TGT>" and a line "</TGT>".
4. 1 Between these two lines, the target composition graph is defined as in a cg file.
5. Outside of the two previously described sections, you can declare the maps between objects and morphisms.
6. 1 You map an object to another with the following syntax : "object1 => object2".
7. 2 You map a morphism to another with the following syntax : "objSrc1 -arrowSrc1-> objSrc2 => objTgt1 -arrowTgt1-> objTgt2".
8. You don't have to (and you shouldn't) specify maps from identities, nor maps from composite arrows.

Serialization of diagrams

writeCGDString :: (PrettyPrint a1, PrettyPrint b1, Eq a1, Eq b1, PrettyPrint a2, PrettyPrint b2, Eq a2, Eq b2) => Diagram (CompositionGraph a1 b1) (CGMorphism a1 b1) a1 (CompositionGraph a2 b2) (CGMorphism a2 b2) a2 -> String

Transform a composition graph diagram into a string following the .cgd convention.

writeCGDFile :: (PrettyPrint a1, PrettyPrint b1, Eq a1, Eq b1, PrettyPrint a2, PrettyPrint b2, Eq a2, Eq b2) => Diagram (CompositionGraph a1 b1) (CGMorphism a1 b1) a1 (CompositionGraph a2 b2) (CGMorphism a2 b2) a2 -> String -> IO ()

Saves a composition graph diagram into a file located at a given path.

Random composition graph

constructRandomCompositionGraph

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

defaultConstructRandomCompositionGraph :: 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].

defaultConstructRandomDiagram :: RandomGen g => g -> (Diagram (CompositionGraph Int Int) (CGMorphism Int Int) Int (CompositionGraph Int Int) (CGMorphism Int Int) Int, g)

Constructs two random composition graphs and choose a random diagram between the two.