The Framework for Implicit
Graph Algorithms and Representations
by OBDDs - The Figaro - is
part of the project Algorithms on Implicit Networks (http://ls2-www.cs.uni-dortmund.de/spp1126)
and concerned with efficient algorithms for problems on implicitly, in particular
by OBDDs represented networks. These are heuristics for large and structured
networks, where traditional algorithms cannot be applied.
The software package The Figaro consists of three layers:
The first layer is a general experiment environment, containing interfaces for
generator and algorithms plugins. This way, the generation of test data and
the execution and parametrization of algorithms can be automized through a graphical
user interface. The second layer of Figaro is a library with useful classes
for graph and OBDD manipulation. Here, L E D A comes into play. At last a third
part of the package contains a variety of generators plugins for the generation
of both explicit and implicit graphs as well as algorithm plugins for network
conversion and explicit and implicit flow maximization.
L E D A data structures are mainly used for the representation
and input/output of explicit (adjacency list based) graphs. Furthermore, its
flow maximization and flow verification algorithms are used by plugins. In addition,
the random generator and some basic data structures are used.
So far Figaro has been tested on Linux only. In order
to compile the package, the following software is required:
- gcc 2.95.x for x >= 3 (http://www.gnu.org)
- Qt 2.x for x >= 3.1 (http://www.trolltech.org)
- CUDD 2.3.1 (http://vlsi.colorado.edu)
- KDevelop 2.0.2 or higher (http://www.kdevelop.org)
- LEDA 4.3 or higher (http://www.algorithmic-solutions.com)
| Contact Details: |
|
| |
University of Dortmund, Germany |
| |
Daniel Sawitzki |
| |
daniel.sawitzki@cs.uni-dortmund.de |
| |
http://thefigaro.sourceforge.net |
|
