University of Dortmund:

The Framework for Implicit Graph Algorithms and Representations by OBDDs - The Figaro - is part of the project Algorithms on Implicit Networks ( 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.


The Figaro


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 (
- Qt 2.x for x >= 3.1 (
- CUDD 2.3.1 (
- KDevelop 2.0.2 or higher (
- LEDA 4.3 or higher (

Contact Details:  
  University of Dortmund, Germany
  Daniel Sawitzki

Copyright © 1998-2007 Algorithmic Solutions Software GmbH. All rights reserved.