LEMON

LEMON (Library for Efficient Modeling and Optimization in Networks) is an open-source C++ template library for graphs, networks, and combinatorial optimization. It was launched in 2003 by the Egerváry Research Group on Combinatorial Optimization (EGRES) in the Department of Operations Research at Eötvös Loránd University (ELTE) in Budapest, Hungary, and in 2009 became part of the COIN-OR (Computational Infrastructure for Operations Research) initiative. It is distributed under the permissive Boost Software License; the last stable release, 1.3.1, dates from July 2014, and the project is developed primarily as C++ header code with a Mercurial/Trac-hosted repository.

Rather than a single graph object, LEMON supplies a family of template-based graph structures that share standardized C++ "concepts," so algorithms are written against an abstract interface and can run on any conforming type. Directed graphs use classes such as ListDigraph (mutable), SmartDigraph (memory-lean), and StaticDigraph (immutable, cache-efficient), with undirected counterparts, plus special structures like grid and full graphs. Data is attached through node, arc, and edge "maps" rather than being baked into vertices. On top of these it provides a large algorithm catalog: BFS/DFS, Dijkstra and Bellman-Ford shortest paths, maximum flow (Preflow), minimum-cost flow (network simplex, cost-scaling), matching, minimum spanning tree, and connectivity, along with a uniform high-level wrapper over LP/MIP solvers including GLPK, CLP/CBC, CPLEX, and SoPlex. Its minimum-cost-flow implementations are widely cited as among the fastest available.

For persistence and interchange LEMON defines its own LEMON Graph Format (LEMON, LGF), a column-oriented plain-text format. Sections begin with an @-prefixed header: @nodes and @arcs (also spellable @edges) list one entity per line as whitespace-separated tokens (plain or double-quoted), where the mandatory "label" column identifies nodes and the first two arc tokens are source and target labels; an optional @attributes section stores scalar or graph-wide metadata. DigraphReader/DigraphWriter and GraphReader/GraphWriter classes serialize maps to and from this format, and bundled command-line tools convert between LGF and DIMACS.

In the graph-data and format-conversion landscape LEMON occupies the same performance-oriented C++ niche as Boost Graph Lib (the Boost Graph Library) and OGDF, and is a lower-level, optimization-focused alternative to general-purpose libraries such as igraph, NetworkX, and graph-tool. Its main limitations are practical: LGF is understood almost exclusively within the LEMON ecosystem, so interchange with formats like GraphML or GML requires external converters; the C++ template design imposes a steep learning curve; and active upstream development has been largely dormant since the mid-2010s, though the code remains stable and in production use.