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

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

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.

Return Just the label of a CompositionGraph non identity generator, Nothing if the morphism is not a non identity generator.

Unsafe version of getLabel. Throws an error if a problem happens.

Return Just a morphism with a given label. If several morphisms share the same label, returns the first one found. O(n)

Return a morphism with a given label. If several morphisms share the same label, returns the first one found. If no one was found throws an error. O(n)

Return Just the Arrow of a CompositionGraph non identity generator, Nothing if the morphism is not a non identity generator.

Given a composition graph, transform an Arrow into a CGMorphism if this CGMorphism is in the composition graph, return Nothing otherwise. O(e)

Unsafe version of cgmorphismToArrow.

Unsafe version of arrowToCGMorphism. O(1)

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

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.

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

The composition law of the composition graph.

Smart constructor of CompositionGraph.

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

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.

The empty CompositionGraph.

Transforms any FiniteCategory into a CompositionGraph.

The two functions given allow to modify nodes and edges label. The two functions given should be injective, it is your responsability to ensure it.

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.

Specialized finiteCategoryToCompositionGraph with two identities.

Transforms an arbitrary Diagram into a Diagram of CompositionGraphs. See finiteCategoryToCompositionGraph.

Specialized diagramToDiagramOfCompositionGraphs with four identities.

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

Read a .cg string to create a CompositionGraph.

A .cg string follows the following rules :

0. Every character of a line following a "#" character are ignored.
1. Each line defines either an object, a morphism or a composition law entry.
2. The following strings are reserved : " -","-> "," = ", "<ID>", "<ID>", "<SRC>", "<SRC>", "<TGT>", "</TGT>", " => "
3. To define an object, write a line containing its name.
4. 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.
4. 1. If an object mentionned in an arrow does not exist, it is created.
4. 2. The spaces are important.
5. 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.
5. 1 If an object mentionned does not exist, it is created.
5. 2 If a morphism mentionned does not exist, it is created.
5. 3 You can use the tag <ID/> or <ID> in order to map a morphism to an identity.

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

Read a .cg file to create a CompositionGraph.

A .cg file follows the following rules :

0. Every character of a line following a "#" character are ignored.
1. Each line defines either an object, a morphism or a composition law entry.
2. The following strings are reserved : " -","-> "," = ", "<ID>", "<ID>", "<SRC>", "<SRC>", "<TGT>", "</TGT>", " => "
3. To define an object, write a line containing its name.
4. 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.
4. 1. If an object mentionned in an arrow does not exist, it is created.
4. 2. The spaces are important.
5. 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.
5. 1 If an object mentionned does not exist, it is created.
5. 2 If a morphism mentionned does not exist, it is created.
5. 3 You can use the tag <ID/> or <ID> in order to map a morphism to an identity.

Map a function on objects of the CompositionGraph.

Map a function on objects of the CompositionGraph, return the diagram from the original CompositionGraph to the new one.

Map a function on arrows of the CompositionGraph.

Map a function on arrows of the CompositionGraph, return the diagram from the original CompositionGraph to the new one.

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

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

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

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>".
1. 1 Between these two lines, the source composition graph is defined as in a cg file.
2. There is a line "<TGT>" and a line "</TGT>".
2. 1 Between these two lines, the target composition graph is defined as in a cg file.
3. After the two previously described sections, you can declare the maps between objects and morphisms.
3. 1 You map an object to another with the following syntax : "object1 => object2".
3. 2 You map a morphism to another with the following syntax : "objSrc1 -arrowSrc1-> objSrc2 => objTgt1 -arrowTgt1-> objTgt2".
3. 3 You can map a morphism to an identity with the following syntax : "objSrc1 -arrowSrc1-> objSrc2 => ID", note however that the source of the morphism objSrc1 should be mapped to an object AFTER this declaration in order to identify which identity it is mapped to. So a complete example would be "objSrc1 -arrowSrc1-> objSrc2 => IDnobjSrc1 => objTgt1"
4. You don't have to (and you shouldn't) specify maps from identities, nor maps from composite arrows.

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

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

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

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

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

Creates a random composition graph with default random values.

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

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