Skip to content

abLEMON — A User Manual

For abLEMON 1.9.0 (November 2026).

Abstract

abLEMON is a C++ template library of graphs, maps, heaps and network optimization algorithms, maintained as a fork of LEMON 1.3.1, whose headers and namespace it keeps. This manual describes the library as it is implemented, family by family: the graph structures and the adaptors that present a graph as another, the maps through which data are attached to nodes, arcs and edges, the heaps and the other auxiliary structures, and the algorithms for graph search, shortest paths, spanning trees, maximum and minimum cost flows (with the certificates of infeasibility and unboundedness and the \(k\) best flows that abLEMON adds), minimum cuts, minimum mean cycles, matchings, connectivity, planarity and isomorphism, the heuristics for the travelling salesman and the maximum clique, and the interface to LP and MIP solvers. For each algorithm the manual states the problem it solves, the conditions it maintains, its complexity as implemented and the choices it leaves to the user, gives its pseudocode, and proves its correctness and its complexity; programs that show each class at work are distributed with the manual and run as tests of the library. Yet, it does not replace the reference documentation, which lists every member with its exact signature, and to which the chapters refer when a detail is not worth repeating.

Conventions

The headings carry the numbers of the manual, and sections, figures, tables, algorithms, theorems, lemmas and exercises are numbered by chapter. The programs named by the chapters are the files of manual/examples/, each of which is a test of the library (ctest -R manual_). A note headed "abLEMON" marks what abLEMON adds to LEMON 1.3.1, or where its behavior differs from it; the rest of the library behaves as in LEMON. Citations refer to the bibliography (Appendix Z), and the terms defined in the chapters are collected in the glossary (Appendix Y).

Contents

Part I: Foundations

Part II: Data structures

Part III: Algorithms

Part IV: Input, output and tools

Part V: Appendices