GOBLIN Graph Library

GOBLIN is a C++ class library focussed on graph optimization and network programming problems. GOBLIN Graph Library 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.

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.

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.

What is new in this release:

• This release addresses perfect graphs: a linear test for chordality and co-chordality has been added.
• Constructors for permutation, threshold, and interval graphs are also available.
• BFS, the max-flow code, and non-weighted matching code have been revised, and now operate on the node color register (integer) instead of the node distance labels.

What is new in version 2.8 Beta 26:

• The Tcl API has been completely revised to conform with the method names in the C++ core library.
• Tcl commands now consistently support optional parameters.
• The HTML reference now covers all graph methods in the Tcl API.
• A constructor method for k-ary (cyclic) butterfly graphs has been added.

What is new in version 2.8 Beta 24:

• Moebius ladders and lattices
• Manipulate the node or arc index order
• Revision of the split graph constructor
• Graph objects composed from other graph objects do not inherit label format strings
• Elimination of the controller layout model
• Explicit bounding box determination
• Convex drawings are not scaled correctly
• SetCapacity() fails on graphs with layout points
• Facet composition
• Missing check for log view initialization
• Tcl interface cleanup and documentation
• Cleanup of access to global variables
• Support for invisible edge segments
• Display grid lines in xFig dependent figures
• Cleanup of inline methods
• Elimination of custom RTTI functionality
• Arc and node deletions may invert the order of bend nodes
• Torus maps
• Generalized Petersen graphs
• Generalized Kneser Graphs
• Improved drawing of triangular graphs