The Algebraic Path Problem Calculator

What is it?

Warshall's algorithm for computing the transitive closure of a Boolean matrix and Floyd-Warshall's algorithm for minimum cost paths are both solutions to the more general Algebraic Path Problem. It describes the closure of a matrix (which may be a representation of a directed graph) using any semiring.

In this application, some algorithms and semirings are implemented which can be used to compute the general task or subproblems (as for example minimum cost paths), respectively. After having selected a particular algorithm and semiring, the user can enter some matrix and compute its closure. Alternatively, all intermediate steps may be computed to have a closer look on the algorithm's behaviour.

The application is based on GTK 2.0 and is supposed to run on all systems having a port of this library although it is only tested on Windows (version 5.1, aka XP) and Solaris (version 9).

AppC is written and published under the GPL. A download link can be found below.

How does it look like?

_{view a larger version of this image}

Where can I get it?

You have the choice to either download the sources and compile AppC on your own or download an executable compiled for Windows.

Windows executable:

• AppC_Windows.zip (size: 110 KB, last updated 17.1.2005)
• You will need GTK.

Source package:

• AppC.tar.gz (size: 60 KB, last updated 17.1.2005)

When having downloaded the source packages, extract the archive and read the files README and INSTALL to get information about the application and how to compile it.

You will need the following programs and libraries to successfully compile and run the application:

• GCC or any other C compiler
• GNU make or any other make tool
• GTK (version 2.0 or higher)