GOBLIN: A Graph Object Library for Network Programming Problems
Content
What is GOBLIN?
GOBLIN is a C++ class library focussed on graph optimization and network
programming problems. It deals with all of the standard graph optimization
problems discussed by textbooks and in courses on combinatorial optimization.
This software package also consists of a shell interpreter which extends the
well-known Tcl/Tk language to graph objects and a graph browser and editor tool.
Executable solvers are available for practical optimization problems. The graph
browser applies for teaching and scientific documentation purposes.
GOBLIN is open source software and licenced by the GNU Lesser Public License
(LGPL). That is, GOBLIN may be downloaded, compiled and used for scientific,
educational and other purposes free of charge. For details, in particular
the statements about redistribution and changes of the source code, observe the
LGPL document which is attached to the package.
The GOBLIN library is outcome of the research project
Balanced Network Flows
which investigates a network flow model for capacitated matching problems:
Efficient matching algorithms often use ordinary flows as a startup solution.
It hence was straight forward to design a library which deals with graph
matching and also with network flows problems, and which allows to combine the
respective problem solving routines to a powerful matching problem solver.
Today, GOBLIN provides strongly polynomial algorithms for the following
graph optimization problems:
- Shortest paths in graphs and digraphs with negative lengths.
- Negative cycles and minimum mean cycles.
- Strong and 2-connected components.
- Minimum spanning trees, arborescences and 1-trees.
- Maximum st-flows, feasible circulations and b-flows.
- Min-cost st-flows, b-flows and circulations.
- Assignment problems of any kind.
- 1-matchings, b-matchings, capacitated b-matchings,
f-factors and degree-constrained subgraphs.
- Directed and undirected Chinese postman problems, T-joins.
The library also includes methods for NP-hard problems, namely TSP, ATSP,
stable sets and graph colouring.
GOBLIN was written and is maintained by Christian Fremuth-Paeger,
co-authored by Bernhard Schmidt. Further contributions are due
to Markus Schwank and Birk Eisermann.
GOBLIN Features
- The gosh interpreter extends the Tcl/Tk scripting language to graph
objects in a natural way.
- The goblet graph browser and editor tool. Graphical front end to the
library.
- An open class hierarchy which strictly separates between abstract classes
(all mathematical algorithms are defined as methods of abstract classes),
implementations (i.e. by incidence lists, adjacency matrices) and logical
views (problem transformations).
- A generic branch and bound module with several applications to graph
optimization.
- Logging and tracing functionality which allows to study the various
algorithms by examples.
- A runtime configuration module controls the selection of
mathemetical methods, logging information, and the tracing of data objects.
- Compile time configuration module for code optimization.
- A file interface which can be easily extended to new problem classes.
- Source code for executable solver programs.
The GOBLET Graph Editor
Build and Installation
The most recent GOBLIN builds can be downloaded as C++
source code. The included Makefile controls the
library build for every UNIX like platform providing a C++ compiler. It is set
up for Linux and gcc but the adaptions to proprietary C++ compilers are simple.
MS Windows users have two additional options: If an Cygwin environment is
already installed or at least, if you are willing to install Cygwin, the binary
distribution goblin.*.cygwin.tbz2 is the right choice. If you
are a typical MS Office user, the setup_goblin.*.exe provides
a minimal Cygwin environment, GOBLIN binaries, shortcuts and an uninstall
procedure. Do not try to run the automatic Windows setup with a concurrent
Cygwin installation!
The reference manual gives some more installation hints
and remarks about known limitations.
UNIX installation using the sources
Supposed, you want to install the GOBLIN Release 2.7 on your UNIX
machine, and Tcl/Tk headers and POSIX threads are installed correctly. The
first step to generate the library, the shell and/or problem solvers is to
unpack the goblin.2.7.tgz file by typing
tar xfz goblin.2.7.tgz
Then change to the extracted GOBLIN root directory. Edit the Makefile
if necessary (and some changes are necessary for platforms other than Linux).
Build the binaries by typing
make
This results in the shell interpreter gosh. You can test your
personal installation by starting the ./goblet graph browser and apply
is the test problems in the samples folder. If everything works fine,
the final system installation is done by the console command
make install
Note that the system installation can be performed by super-users only.
Building only the Library and Problem Solvers
If some libraries are missing in your environment and if you only want to use
the C++ API, link the GOBLIN core library by typing
make goblin
If you want to use GOBLIN executables rather than the API, say the matching
solver, then
make exe pr=optmatch
creates the executable optmatch. The complete list of executable solvers
can be obtained from the folder main_src and the reference manual.
Using Binary Distributions
This is currently supported for Cygwin only. Copy the goblin.*.bz2 file
to the Cygwin (not Windows) root directory /. Start a bash, change
to the root directory and unpack the sources by
tar xfj goblin.*.tbz2
sh goblin_install.sh
As a final step, all GOBLIN related files in the root directory may be deleted.
GOBLIN Setup for MS WINDOWS
Make sure that no concurrent Cygwin installation is present. Then just execute
the setup_goblin.*.exe file. Shortcuts to the graph browser will be
added to the desktop and the start menu.
Remarks
Source code packages are configured for gcc and Tcl/Tk 8.3.
Cygwin Binaries run with Tcl/Tk 8.4.
To compile GOBLIN with Tcl/Tk 8.4 headers, a special define in the
Makefile must activated.
In the testing environment, GOBLET can only be started from the GOBLIN
root directory.
On platforms other than Linux and Cygwin, the makefile must be
configured manually before performing make install.
The source code compiles (at least) with gcc 3.4.1 and earlier versions.
The GOBLET Graph Browser
GOBLIN Documentation
The package comes with a comprehensive LATEX reference manual which describes:
- The GOBLIN class concept.
- The library functions.
- The data structures.
- The file formats.
- The gosh interpreter.
- The solver executables.
- Some experimental results.
Please, if you read this document, and you find any mistakes or omissions,
send us some report. We really depend on user reviews.
Neither the reference manual nor this HTML document apply for a tutorial.
If you have problems to get started, mail your remarks so that I can prepare
an adequate document.
|
Release Notes
Yes, it's true: There is no 1.0 release. Originally, I did not plan to write
any graphical front end for GOBLIN. Due to the fundamental changes between
release 0.99 and the 2.0 package (including the file formats), I decided to
skip the 1.0 label. All introductory statements concern the 2.0 version.
What's new in Release 2.1
- Improvements of the graphical tracing module: GOBLIN stores graph objects
instead of xFig canvases. GOBLET distinguishes between the graph object and
trace objects.
- Import filters for DIMACS problem instances (very simple, but problem
dependant formats) and for the most frequently used TSPLIB formats.
- Explicit implementation of mixed graphs.
- Tree heuristics for the max-cut problem.
What's new in Release 2.2
- Stable release with many bug fixes.
- Export filters for DIMACS problem instances and for the most frequently
used TSPLIB formats. Solutions can be also exported to TSPLIB files.
- Strong improvements of the branch and bound solvers for TSP, independent
node sets and colourings.
- Tree packings for digraphs.
- Subgradient optimization for asymmetric TSP.
What's new in Release 2.3
- Branch and bound for asymmetric TSP.
- Candidate graphs for the weighted matching solver.
- Discrete Steiner trees enumeration.
What's new in Release 2.4
- Some additional basic layout styles (circles, grids, by node colours).
- Local search heuristics for node colourings.
- Approximation methods for planar colouring and edge colouring.
- Graphical tracing of heaps and union-find structures.
- Root, source and sink nodes stored with graph objects.
- Thread support.
- Improved front end.
- Export filter for Tcl library graph objects.
What's new in Release 2.5
- Primal network simplex method.
- Redesign of the logging module.
- GOBLET functionality for searching in log files.
- GOBLET threading is default again. The respective bug has been fixed.
- Single step tracing mode.
- Improved tree layout.
- Internal windowing.
- Many bug fixes.
What's new in Release 2.6
- Revision of the primal network simplex method. The performance has
been improved considerably.
- Revision of the TSP subgradient optimization. Improved numerical
stability, additional confguration parameter.
- Generic interface for LP solvers (Tcl wrapper and C++ API).
Data structures for internal LP solver.
- Export filters for LP, standard MPS, CPLEX MPS and BAS format.
Import filters for MPS/BAS.
- Initial Simplex Code.
- Browser support for linear programs.
- Revision of the makefile with respect to CYGWIN build.
Revision of the solver executables.
- Initial version of a spring embedder.
- Push/Relabel method and node identification algorithm for minimum cut problems.
- Enhanced configuration management for the browser application layer.
- Revision of the GOBLET tracing functionality.
- Support of file compression.
- Revision of the memory management.
- Compatibility with gcc 3.2.x.
- Text display of unembedded graphs.
What's new in Release 2.7
- 2-approximation method for discrete Steiner trees.
- Additional graph composition tools.
- Steinlib import filter.
- Editor mode for node colours.
- Dictionary data structure.
- Support for edge colouring.
- Free style display of arc and node labels.
- GLPK 4.0 plugin.
- Planarity testing and topologic embedding.
- Editor mode for sorting incidence lists.
- Editor support for bigraphs.
- Module and bibliographic database.
- Module dependent timers.
- Browsing facility for modules, authors, timers and references.
- Improved exception handling.
- Explicit generation of Euler cycles.
- Reworked DAG search method: Application to shortest paths and critical
paths.
- Max-Cut branch and bound for small instances.
- Dual T-join method for planar max-cut.
- GRASP heuristic for max-cut.
- st-numbering of 2-connected graphs.
- Canonical ordered partition of 3-connected planar graphs.
- (Convex) straight line drawing of planar graphs.
- Combinatorial embedding and drawing of outerplanar graphs.
- More performant force directed layout.
- Revision of the network simplex code.
- Redesign of the right hand input forms.
- Cleanup of the linear programming stuff.
- Compatibility with Tcl/Tk 8.4 and CYGWIN.
- Explicit code for edge covering problems.
What's new in Release 2.7.2
- Refined tree layout.
- Initial mixed integer programming code.
- Application to the stable set problem.
- Refined node colouring code.
- GOBLET supports asynchronous file I/O.
- Progress bar and estimation of execution times.
- Context menus for the graph display and messenger.
- Compatibility with gcc 3.4.x
- Excess scaling implementation of the max-flow preflow-push method.
- Fundamental algorithms for orthogonal drawing: Kandinski, 4-planar,
4-orthogonal and visibility representation.
The Change log lists all bug fixes.
Plans for the Future
There will be some further work on GOBLIN other than bug fixes and
maintainance. In particular, we plan the following improvements and extensions:
- Branch and bound scheme for Steiner trees.
- Basic branch and bound code for integer programming.
- Some more sophisticated graph layout methods.
- The MKM max-flow method.
Help us to make a decision which step is next.
Call for Co-authors and Contributors
This software is open source and provides a clear design based on C++
object-oriented programming.
Since our man power is restricted, we would like to suggest some fields for
possible contributions:
- Any known algorithm from graph optimization which you are missing.
- Heuristics and branch and bound schemes for NP-hard graph optimization problems.
- Sophisticated graph layout methods.
- Delaunay triangulation.
- Import and export filters for other graph optimization tools.
- Reports of relevant file formats for graph objects.
- Bug reports, user request and reviews of any kind.
These are only suggestions. If you plan a new implementation of such
mathematical algorithms, and you are willing to make your code open source,
then GOBLIN is the right base for your work. Do not hesitate to contact me
for support.
If you have any C based open source code, and a merger seems reasonable to you,
let me know.
Especially, students of the University of Augsburg are welcome to contribute to
GOBLIN in the framework of numerical practica or diploma theses under the
supervison of Bernhard Schmidt. Please contact
Bernhard Schmidt for further information.
Examples of GOBLIN Layouts
This small gallery shows some graph layouts, either of computational
results or of trace objects which have been generated automatically:
Network flows
Matchings
Travelling Salesman
Packings and Partitions
Spanning Trees
Orderings
Problem Transformations
Data Structures
Christian Fremuth-Paeger, October 2005
