LEMON – a high performance open source C++ graph and network library

Department of Operations Research, Eötvös Loránd University Budapest has been involved in various applied research projects, either as a member of a research consortium or  in a direct collaboration with different companies.

Applied research is unimaginable without using advanced algorithmic methods. In fact, the expected outcome of a typical project is a software that should be appropriate for productions use eventually. As our main research focuses on graphs and network optimization, a good graph library has always been in a constant need for us.

Of course, there has been graph libraries around for many years, both free and commercial ones. However, none of them could meet our requirements. We needed a framework that is comprehensive, reliable and of high performance on one hand, but can be used without restrictions even in commercial applications. In addition, having the source code of the algorithms in hand is an invaluable plus when it comes to fine tuning a solution.

resThe lack of the appropriate toolkit led us starting to work on our own framework some ten years ago, but we went one step further and decided that we would make it available to everyone. Thus,  we initiated a open source project called Library for Efficient Modeling and Optimization in Networks LEMON for short, with the aim of developing a new C++ graph and network library and release it under a permissive open source license which does not only allow, but also encourages commercial use. In 2009, it joined the COIN-OR initiative, a collection of open source Operations Research toolkits.

Over the years, it became the most comprehensive open source library of its kind. Currently, LEMON consists of more that 52.000 lines of highly optimized and well documented lines of source code and mode than 10.000 lines of unit tests. The underlying graph data structures  are the fastest on the market, but very convenient to use at the same time.  You will find an efficient implementation of a large collection of standard graph algorithms, such as shortest paths, minimum cost network flows, graph matchings, connectivity and planarity tests etc. Many of these implementations are the fastest available both amongst  the open source and the commercial alternatives (some comparisons can be found here and here).

LEMON has been used for various academic research, Google scholar show well above 150 citations from a wide field of applications such as telecommunications, transportation, social sciences, image processing, data mining, computer and operations system technologies, chemistry and bio-informatics etc.

But, as I mentioned we also target industrial and commercial application, which is all about reliability and support. We pursue this by rigorously following a strict work-flow of testing, reviewing and documenting of new features and bug fixes. We also support various operation systems (Windows, Linux, OSX, AIX and other Posix systems) and compilers (Gnu C++, Clang, Visual Studio, Intel C++, IBM XL/C++)

As a result, LEMON is indeed finds it application in the industry, we are getting positive feedback from major companies from the telecom, business intelligence, and biochemistry sector.

And do not forget, this is a community project – external contributions are the most welcome. So, if you plan to implement a new graph algorithm or have an idea to improve something that LEMON already has, then why not take some extra effort to submit it for inclusion to LEMON, thus make it available for everyone?

Alpár Jüttner
Department of Operations Research
Eötvös Loránd University

%d bloggers like this: