**Aptī Algoritmi** is the Latin for *(fit / apt / suitable / fitting / prepared / useful) Algorithms*.

This site hosts implementations of algorithms that are ready for use in software construction.

I am in the process of creating a topic map of algorithms that solve the transitive closure problem. The topic map is a classification of these algorithms and should ideally point to implementations of algorithms. As part of this endeavor, I implement the algorithms that I include in the topic map and publish them here to be accessible for the users of my topic map and others that may want to use these implementations. The aim of the topic map is ultimately to aid developers in finding suitable algorithms when constructing software.

Type the dimension, a comma, and then a continous stream representing the adjacency matrix of the relation: 4,0100001010010000 |

Input Relation: |

0100 |

0010 |

1001 |

0000 |

Transitive Closure of the Relation: |

1111 |

1111 |

1111 |

0000 |

`getRelation`

- Read standard input and return a pointer to a variable of the appropriate data stucture for the algorithm.
`transitiveClosure`

- Takes a pointer to a variable of the appropriate data structure containing the input relation as a parameter and transforms the value of this variable to the transitive closure of the input relation.
`showRelation`

- Takes a pointer to a variable of the appropriate data structure containing a relation as a parameter and print this relation to standard output.

These implementations use square boolean matrices to represent
relations. To do this, a vector of elements is used where each of
these elements represent a row in the matrix. Each algorithm has
a standard implementation named *Std that uses
a `vector< char* >`

to represent the
relations. These implementations only need the standard template
library. Each algorithm also has a second implementation named *Boost
that uses a `vector< dynamic_bitset<> >`

to
represent the relations. The `dynamic_bitset<>`

is defined
in the boost c++ libraries.

- Baker's Algorithm
^{3} - Iterates through the entries in the matrix in row order and uses a
change monitor to know when to stop.

BakerStd.zip (1025 B 2013-12-08 16:07)

BakerBoost.zip (993 B 2013-09-01 18:08) - The Blocked Column Algorithm
^{1, 2} - A variation of Warshall's algorithm: Columns are processed in
blocks while applying loop tiling to minimise cache thrashing. The
elements within the block and within the square section around the diagonal are processed in
column order. After processing the elements in the square section, the
rest of the elements within a block are processed in row order

BlockColStd.zip (1303 B 2014-04-21 17:14)

BlockColBoost.zip (1458 B 2014-04-21 17:05) - The Blocked Row Algorithm
^{1, 2} - A variation of Warren's algorithm: Rows are processed in
blocks while applying loop tiling to minimise cache thrashing. The elements within a block are processed in column order

BlockRowStd.zip (1256 B 2014-01-26 15:59)

BlockRowBoost.zip (1331 B 2014-01-26 15:54) - The Fused Coat Algorithm
- An optimisation of Prosser's algorithm: A loop that multiplies two
matrices and a loop that adds two matrices are fused.

FusedCoatStd.zip (1303 B 2013-12-19 20:26)

FusedCoatBoost.zip (1331 B 2013-12-19 20:11) - Martynyuk's Algorithm
^{4} - Iterates through the entries in the matrix in row order and stop
after
*log*iterations._{2}n

MartynyukStd.zip (1028 B 2013-12-08 16:07)

MartynyukBoost.zip (1004 B 2013-09-02 20:10) - The Monitored Coat Algorithm
- Apply repeated matrix multiplication and uses a
change monitor to know when to stop.

MonCoatStd.zip (1377 B 2013-12-19 20:27)

MonCoatBoost.zip (1433 B 2013-12-19 20:12) - The Neat Coat Algorithm
- An optimisation of the monitored coat algorithm: A loop that multiplies two
matrices and a loop that adds two matrices are fused.

NeatCoatStd.zip (1379 B 2013-12-31 12:11)

NeatCoatBoost.zip (1420 B 2013-12-31 12:28) - Prosser's Algorithm
^{5} - Apply repeated matrix multiplication and stop after
*n - 1*iterations.

ProsserStd.zip (1308 B 2013-12-08 16:08)

ProsserBoost.zip (1299 B 2013-09-02 02:42) - Warren's Algorithm
^{6} - Iterates through the entries in the matrix in row order. Process
entries below the main diagonal in the first pass and those above in
the second pass. It
calculates the transitive closure in two passes.

WarrenStd.zip (2014 B 2014-01-08 19:02)

WarrenBoost.zip (970 B 2014-01-08 19:22) - Warshall's Algorithm
^{7} - Iterates through the entries in the matrix in column order. It calculates the transitive closure in one pass.

WarshallStd.zip (988 B 2013-12-08 16:08)

WarshallBoost.zip (931 B 2013-09-02 17:41)

Compile and run the code using any C++ compiler for example the C++ compiler that can be found in the GNU Compiler Collection on Linux, the C++ compiler that is part of Minimalist GNU for Windows, or the C++ compiler that is included in the Command Line Tools for Xcode on a Mac.

When using the code that relies on boost c++ libraries,
the dynamic bitset
library needs to be installed on your machine. When issuing the compile command, the boost directory has to be in
the search path of your C++ compiler. Assume, for example, that you installed `boost_1_54_0.bz2`

in
the `/usr/local/boost`

directory, you can compile `BakerBoost.cpp`

by issuing the following
command in the directory where `BakerBoost.cpp`

is saved:

`g++ -I /usr/local/boost/boost_1_54_0/boost BakerBoost.cpp`

If `BakerBoost.cpp`

is compiled using the above mentioned command, a compiled version of this program is
saved in the current directory. On Windows it is called `a.exe`

and on Linux and Unix (Mac), it is
called `a.out`

. It can now be executed by typing `a`

in Windows or `./a.out`

in
Linux/Unix.

It should not be too difficult to adapt the code and reuse it in any project that needs it.

If you experience any problems when using the code, feel free to drop me an e-mail. I cannot guarentee that I will be able to assist, but might be able to give guidance in solving your problems. Your queries will help me to compile a troubleshooting guide.

- InputData.zip (1.4 MB 2013-12-08 13:26)

`InputData.zip`

is an archive containing some input files. Each file contains input to the provided
programs to specify the adjacency matrix of a randomly generated relation. It's filename encodes facts about this
relation. The first character is an alphabetical character which is varied to have more than one relation having
the same characteristics. The next four characters is a four digit number specifying the dimension of the
relation. The last two digits is the percentage filled. Thus, `C0600_05.txt`

is input containing the
adjacency matrix of a 600 × 600 relation that has 95% zeros and 5% ones.

These are text files that can be piped as input to a compiled version of each of the downloadable programs. The
following is the command to execute an executable with C0600_05.txt as its input on Windows, when assuming the executable is called `a.exe`

:

`a < C0600_05.txt`

`a.out`

, the command is:
`./a.out < C0600_05.txt`

`generate.cpp`

which you can compile and run to
generate more data.
- Agrawal R and Jagadish HV (1987) Direct
Algorithms for Computing the Transitive Closure of Database
Relations,
*Proceedings of the 13th International Conference on Very Large Data Bases (VLDB'87)*, 255 - 266. - Agrawal R, Dar S and Jagadish HV (1990) Direct
transitive closure algorithms: design and performance
evaluation,
*ACM Transactions on Database Systems (TODS)*, 15(3):427 - 459. - Baker JJ (1962) A note on multiplying Boolean matrices,
*Communications of the ACM*, 5(2):102. - Martynyuk V (1963) The economical construction of a transitive closure of a binary relation,
*USSR Computational Mathematics and Mathematical Physics*, 2(4):817-821. - Prosser RT (1959) Applications of Boolean matrices to the analysis of flow diagrams,
*Proceedings of the Eastern Joint Computer Conference*No.16: 133-138. - Warren HS Jr (1975) A Modification of Warshall's
algorithm for transitive closure of binary
relations,
*Communications of the ACM*, 18(4):218-220. - Warshall S (1962) A Theorem of Boolean Matrices,
*Journal of the ACM*, 9(1):11-12.