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|
|Transitive Closure of the Relation:|
|Algorithms using square boolean matrices|
|BakerStd||Iterates through the entries in the marix in row order and uses a change monitor to know when to stop.||C++||STL||BakerStd.zip||1025 B||2013-12-08 16:07|
|BakerBoost||C++||boost||BakerBoost.zip||993 B||2013-09-01 18:08|
|MartynyukStd||Iterates through the entries in the marix in row order and stop after log2n iterations||C++||STL||MartynyukStd.zip||1028 B||2013-12-08 16:07|
|MartynyukBoost||C++||boost||MartynyukBoost.zip||1004 B||2013-09-02 20:10|
|ProsserStd||Apply repeated marix multiplication and stop after n iterations||C++||STL||ProsserStd.zip||1308 B||2013-12-08 16:08|
|ProsserBoost||C++||boost||ProsserBoost.zip||1.3 KB||2013-09-02 02:42|
|WarshallStd||Iterates through the entries in the marix in column order. It calculates the transitive closure in one pass.||C++||STL||WarshallStd.zip||988 B||2013-12-08 16:08|
|WarshallBoost||C++||boost||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
/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
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
a.out. It can now be executed by typing
a in Windows or
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 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 < C0600_05.txt
a.out, the command is:
./a.out < C0600_05.txt
generate.cppwhich you can compile and run to generate more data.