LEMON (C++ library)

LEMON is an open source graph library written in C++ language. It is quite a useful tool for solving optimization problems. This means that LEMON can be a basis for applications solving different kind of optimization problems and also a starting point for implementing new algorithms in the area of theoretical research and applications, as well. It provides a set of easy-to-use implementation of common data structures and algorithms in the area of optimization. It is a particularly advantageous toolkit to implement optimization algorithms for design problems of telecommunication networks.

LEMON is an open source software library. This kind of software development has major advantages both for the users and for the developing team itself.The users of an open source package get a higher grade of flexibility. They can clearly see the power and the limitations of the package, for they get direct access to the source code. Since the users also have right to freely modify the code, it can be easily customized to meet the arising special requirements.As the open source makes it easy for researchers and software developers to implement their new ideas based on the package developers can expect to get useful feedback, improvements from them, as well as implementations of new algorithms or data structures.

Use of LEMON is free in commercial or non-commercial applications under very permissive license terms.

Design

A very important design requirement of the interface of data structures and algorithms is genericity. This basically achieved by separation of data structures and algorithms. Clearly the main difficulty in this approach is to make this without any loss of performance and usability. However, once these problems are overcome, this separation gives a huge advantage in flexibility for the user by making it possible to choose the most appropriate data structures or just to adapt an algorithm for an already existing data structure.

Since one can make the most of the advantages of “generic programming” only in the presence of the full source code; that is why commercial packages give very limited support for this programming style, and that is why LEMON is a suppletory product.

Generative programming is achieved in C++ by using templates. For example most of the algorithms implemented in LEMON do not fix the type of the graph it works on, but only asserts that it fulfills a certain graph-concept, i.e. only the interface of the graph is fixed. So the type of the graph appears as a template parameter of the algorithm class.Since the abuse of too many template parameters can result in a flexible but very hard-to-use tool in practice, it is necessary to determine in advance the midway between ease of usage and genericity.

The most important classes in LEMON are the graph classes. An instance of a graph class is the representation of the mathematical graph. It holds the topology and every structural information of the graph. The structural manipulations are also provided by the graph object. There is no universal graph class instead different classes are implemented for different purposes. They can differ in many ways, but all have to satisfy one or more graph concepts which are standardized interfaces to work with the rest of the library. One main advantage of the templates are, that you can write your own graph classes. As long as they provide the interface a concept is defining all the LEMON algorithms and classes will work with it properly - no representation or implementation is written into stone.

Algorithms

In LEMON the following algorithm-groups are present:
* Graph Search
* Shortest Path algorithms
* Maximum Flow algorithms
* Minimum Cost Flow algorithms
* Minimum Cut algorithms
* Connectivity and other graph properties
* Matching algorithms
* Minimum Spanning Tree algorithms
* Auxiliary algorithms
* Approximation algorithms

Many industrially motivated optimization tasks involves in solving computationally hard (NP-hard) problems. In this case, the generic optimization (meta)heuristics are of great importance. LEMON contains some metaheuristic optimization tools.

Linear Programming is the most powerful tool to solve network related optimization problems. Therefore - for a package like LEMON, it is crucial to provide a comfortable and efficient way to create and solve linear programming problem instances.

Linear programming is a central tool not only in optimization, but also in economy, biology, chemistry etc. To satisfy this demand there are several commercial and non-commercial solver packages having been developed for many years. A uniform and comfortable-to-use interface to the most important of these solvers is implemented in LEMON. The advantage of this approach is twofold. Firstly the C++ interface of LEMON is more comfortable than the solvers' native interface. Secondly, changing the underlying solver in a certain software using LEMON's LP interface needs zero effort. So, for example, one may try his idea using a free solver, demonstrate its usability for a customer and if it works well, but the performance should be improved, then one may decide to purchase and use a better commercial solver.

Additional tools

LEMON has its own graph storing format, the so called Lemon Graph Format. It enables one to store graphs and additional maps (i.e. functions on the nodes or edges) in a flexible and efficient way.

LEMON includes general EPS drawing methods and special graph exporting tools.

For testing purpose simple tools for measuring the performance of algorithms are present in LEMON. With them it is possible to compare different implementations of the same problem.

External links

LEMON webpage:
* [https://lemon.cs.elte.hu Lemon site]

Other graph libraries:
* [http://www.boost.org/ Boost]
* [http://www.mpi-inf.mpg.de/LEDA/leda.html Leda]
* [http://www.math.uni-augsburg.de/~fremuth/goblin.html Goblin]
* [http://www.infosun.fim.uni-passau.de/GTL/ GTL]