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
- 9. Graph search
- 10. Shortest paths
- 11. Spanning trees and arborescences
- 12. Maximum flows and circulations
- 13. Minimum cost flows
- 14. Certificates and the k best flows
- 15. Minimum cuts
- 16. Minimum mean cycles
- 17. Matchings
- 18. Connectivity, planarity, isomorphism
- 19. Travelling salesman and maximum clique
- 20. The LP and MIP interface
Part IV: Input, output and tools
Part V: Appendices