Small Graph Library (SmaGL)

• References
• Projects
  • Weltgeld
  • SmaGL

Description

The Small Graph Library allows to create directed graphs that have a cost and capacity associated whith each edge. Several graph algorithms like push-relabel for finding the maximum flow from a source to a sink and breadth-first search are readily available.
The main goal is a small memory footprint while maintaining reasonable speed and stability.

News

09.Feb. 2001: LEDA is no longer available through the Max-Planck Institut für Informatik, Saarbrücken but solely through AS. As far as I can tell right now there is no free license available anymore.

04.July 2000: I decided to offer two versions of SmaGL from now on: A stable version with an even minor version number, currently v0.2.0, and a development version indicated by an odd minor version number, currently v0.3.3.

05.May 2000: SmaGL 0.3.3 available for download

• Several changes in the maximum flow algorithm. Now usese the correct distance label for the source. Previously it was possible that there were unsaturated paths left. Implemented global updates as suggested by A.V. Goldberg.

26.Apr.2000: SmaGL 0.3.2 available for download

• Mainly added some more documentation
• Started working on file parser.

19.Apr.2000: maxflow is now SmaGL.(Small Graph Library)

• Again some bug fixes and code clean up.
• The actual implementation of the Graph is now available in libgraph.a.

11.Apr.2000: Finally the next release of Maxflow (maxflow-0.3).

• Vertices are now objects that can have additional properties.
• Some bug fixes.

01.Nov.1999: First release of Maxflow. (maxflow-0.1)

Implemented Features

It is already possible to create a graph. The bfs and the push-relabel algorithm for maximum flow seem to work.
API | Documentation

Planned Features

v.0.3

• Highest label with gap relabeling algorithm for maximum flow problem.
• File i/o of graph to different file formats

v.0.5

• Separate graph data structure and algorithms
• Parallel implementation of maximum flow algorithm
• Simple graphical interface for loading graph and applying of algorithms

More features

• Several different graph creation methods to represent physical systems.
• Implementation of a convex min-cost algorithm.
• Interface well with Vizarcs (Visulization and Remote Control System) for large scale calculation.
• Use XML based file format for graph storage similar to GML
• Import/Export filter for GML
• Use of templates for data types
• Connectivity algorithms
• Distributed algorithms for push-relabel and others
• ...

Motivation

In recent years graphs have been used to represent physical system like the "Random Field Ising Model" (RFIM) or "Directed Polymers in Random Media" (DPRM). Algorithms from combinatorial optimization (maximum flow, shortest path, ...) allow ground state calculation in polynomial time. Other methods known to physicist often involve an exponential increase in computation time.

Download

Stable branch

• SmaGL v. 0.2.0

Development branch

• SmaGL v. 0.3.3
• SmaGL v. 0.3.2
• SmaGL v. 0.3.1
• maxflow-0.3.tar.gz
• maxflow-0.1.tar.gz

The Competition

Maybe you cannot wait until Maxflow is far enough for serious scientific use. In that case have a look at some of these programs.

• LEDA, a library of data types and algorithm