Contents - Index

TRANSFORM > SEMIGROUP

PURPOSE Construct the semigroup of a graph, digraph or multirelational graph.

DESCRIPTION The semigroup of a network is an algebraic representation of all compound relations.  

Given a set of adjacency matrices R1,R2,...,Rn of a multirelational graph then the set of all possible Boolean products of pairs of matrices gives all possible relations of length 2.  If any of these products is repeated then they are discarded.  We continue with products of length 3 etc until no new matrices are found.  The set of all matrices constructed in this way together with the operation of Boolean matrix multiplication form a semigroup.

This routine finds all members of the semigroup, or members of the semigroup up to a certain length of product.  In addition the semigroup is specified by a multiplication table.

PARAMETERS
Input dataset:
Name of file containing adjacency matrix or matrices. Data type:  Digraph. Multirelational.

Maximum length of "words": (Default = 9)
The products are called words. The maximum length of products to be considered is known as the word length.

Save elements of semigroup ?: (Default = No)
If only the multiplication table and words are required then it is not necessary to save the matrix elements.YES causes all generated matrices to be saved in a file specified below.

Output semigroup: (Default = 'SEMIGROUP')
Name of file which will contain all compounded relations provided the save elements of semigroup parameter was set to YES.  These are given as a list, each relation is sequentially numbered. This file does not appear in the LOG FILE.

Output multiplication table: (Default = 'MULTABLE')
Name of file which will contain the multiplication table specified below.


LOG FILE Semigroup multiplication table.  

Each row (and column) is labeled with the compound relation number.  The rows also give the word that accounts for the compound.  Hence if row 6 is labeled 1 1 2 1 then relation 6 is the matrix obtained by Boolean matrix multiplication of the original relations numbered 1 1 2 1 in that order.  The value in row i column j is the result of the Boolean matrix multiplication of relation i and relation j.

If the word length is not sufficient to generate all elements of the semigroup then the right multiplication table of the generated elements is displayed.  This table gives the product of the generated elements with the input matrices.

TIMING Algorithm is exponential.

COMMENTS Relatively small datasets can result in large semigroups. 

REFERENCES None.