Skip to content

1. Introduction

We are concerned with abLEMON, a C++ template library of graphs and of the algorithms of network optimization built on them. It provides the structures that represent directed, undirected and bipartite graphs, the maps that attach data to their nodes, arcs and edges, the heaps and the other auxiliary structures that the algorithms need, and the algorithms themselves (searches, shortest paths, spanning trees, maximum and minimum cost flows, minimum cuts and mean cycles, matchings, connectivity, planarity and isomorphism, heuristics for the travelling salesman and the maximum clique, and an interface to LP and MIP solvers). abLEMON is a maintained fork of LEMON, the Library for Efficient Modeling and Optimization in Networks of the Egerváry Research Group of the Eötvös Loránd University of Budapest (Dezső, Jüttner and Kovács 2011), which has had no release since 1.3.1 (2014). It starts from the last revision of the Mercurial repository of LEMON, whose history it keeps, and it keeps its headers (lemon/) and its namespace (lemon); hence, a program written for LEMON usually compiles with abLEMON unchanged.

This manual describes the library as it is implemented in abLEMON 1.9.0. Each public class of lemon/ is described in the chapter of its family, with the theory that one needs to choose among the algorithms and to read their results, and the statements on costs, defaults and behavior have been checked against the code. The manual is a companion to the reference documentation that Doxygen produces from the headers (https://dmeoli.github.io/abLEMON/), which gives each member with its exact signature. We give instead the problem that each class solves, the conditions it maintains, how the classes are meant to be combined, and the pseudocode of each algorithm with the proofs of its properties; the programs that use the classes are not printed in the chapters, but kept in manual/examples/, where each is compiled and run as a test of the library (cf. chapter 2) that checks what the chapter states. We assume that the reader writes C++ and knows the basic notions of graph theory and of linear programming. The network optimization that a chapter needs is recalled in it, with references to the textbook of Ahuja, Magnanti and Orlin (1993) and to the papers of each algorithm.

1.1 What abLEMON changes

The differences from LEMON 1.3.1 fall into four groups, which NEWS lists release by release and which the chapters mark with a note "abLEMON" where they apply. The first group is portability: the library compiles without warnings from C++11 to C++23 with GCC, Clang, AppleClang and MSVC. For instance, the allocators go through std::allocator_traits, since C++20 removed the members of std::allocator that ArrayMap and ListPath called; also, each header is self-contained, and the headers survive the macros min and max of <windows.h>. The second group is correctness. Several defects of the algorithms and of the data structures are fixed, most of them with a test that failed before the fix (e.g., RadixHeap mixed the items of adjacent boxes, BinomialHeap truncated fractional priorities, and Circulation read past its storage on an empty digraph), and the items of the graphs are INVALID when they are default-constructed.

The third group concerns the minimum cost flow algorithms (chapter 13 and chapter 14). These solve problems with floating-point data, under tolerances relative to the data, and they certify an infeasible or unbounded answer (with a set of nodes whose supply exceeds what can leave it, or with a cycle of negative cost and infinite capacity). Furthermore, they give the \(k\) most violated such sets, and two further classes give the \(k\) best integer flows and the \(k\) best extreme flows; alternative optimal potentials are also available. The fourth group is a set of new algorithms and structures, i.e., HopcroftKarp and MinCostAssignment for bipartite matching (chapter 17), BidirDijkstra and AStar for the shortest path between two nodes (chapter 10), TomitaSekiMc for the exact maximum clique (chapter 19), and StaticGraph, the undirected counterpart of StaticDigraph (chapter 4). Also, with CMake 3.28 and Clang 16 or MSVC 19.34, the library may be built as the C++20 module lemon (whose interface is lemon/lemon.cppm, cf. §2.3).

1.2 How the manual is organized

Part I gives what one needs before anything else: the installation (chapter 2) and the model of the library (chapter 3). In this model graphs have nodes and arcs that are handles, data are attached to them by maps, concepts state what an algorithm requires of the types it is given, and algorithms are classes that are configured, run and then queried. Part II describes the data structures, i.e., the graphs, the adaptors that present a graph as another one without copying it, the maps, the heaps, the paths and the auxiliary structures. Part III describes the algorithms, family by family: each chapter states the problem, the optimality conditions and the complexity of each algorithm, gives its pseudocode with the theorems on its correctness and its complexity, compares the variants that the library offers, names the programs and the tests that check it, and ends with exercises. Part IV covers the formats of input and output (LGF, DIMACS, nauty, PostScript) and the tools of tools/. Appendix A explains how a new graph, map or heap is written so that the algorithms accept it, while Appendices Y and Z hold the glossary and the bibliography.

A reader who only needs one algorithm may read chapter 3 and then the chapter of that algorithm, since the chapters of Part III are meant to be read independently of each other. They refer to each other where one algorithm uses another one; e.g., the certificates of chapter 14 rest on the maximum flows of chapter 12. Table 1.1 gives the chapter where each header of lemon/ is described (the internal headers of lemon/bits/ only where a user meets them). In it, core.h holds the items of the graphs, the basic utilities and the common definitions, and is included by all the other headers; config.h and export.h, instead, are written by CMake when the library is configured (cf. §2.4), the latter by its module GenerateExportHeader, with the macro LEMON_DATA that marks the data a DLL exports, and lemon.cppm is the interface of the C++20 module (cf. §2.3).

Table 1.1. The headers of lemon/ by chapter.

Chapter Headers
2 config.h, lemon.cppm
3 core.h (items), concept_check.h, tolerance.h, math.h, bits/traits.h
4 list_graph.h, smart_graph.h, static_graph.h, compact_graph.h, full_graph.h, grid_graph.h, hypercube_graph.h, edge_set.h, core.h (utilities), concepts/digraph.h, concepts/graph.h, concepts/bpgraph.h, concepts/graph_components.h
5 adaptors.h
6 maps.h, concepts/maps.h
7 bin_heap.h, quad_heap.h, dheap.h, fib_heap.h, pairing_heap.h, binomial_heap.h, radix_heap.h, bucket_heap.h, concepts/heap.h
8 path.h, concepts/path.h, unionfind.h, elevator.h, dim2.h, radix_sort.h, random.h, counter.h, time_measure.h, color.h, error.h, assert.h, arg_parser.h
9 bfs.h, dfs.h, max_cardinality_search.h
10 dijkstra.h, bidir_dijkstra.h, astar.h, bellman_ford.h, suurballe.h
11 kruskal.h, min_cost_arborescence.h
12 preflow.h, edmonds_karp.h, circulation.h, concepts/max_flow.h
13 network_simplex.h, cost_scaling.h, capacity_scaling.h, cycle_canceling.h, concepts/min_cost_flow.h
14 k_best_flows.h, k_best_extreme_flows.h
15 hao_orlin.h, nagamochi_ibaraki.h, gomory_hu.h
16 karp_mmc.h, hartmann_orlin_mmc.h, howard_mmc.h, concepts/min_mean_cycle.h
17 matching.h, bipartite_matching.h, fractional_matching.h
18 connectivity.h, euler.h, planarity.h, vf2.h, vf2pp.h
19 nearest_neighbor_tsp.h, greedy_tsp.h, insertion_tsp.h, christofides_tsp.h, opt2_tsp.h, grosso_locatelli_pullan_mc.h, tomita_seki_mc.h
20 lp_base.h, lp.h, lp_skeleton.h, glpk.h, clp.h, cbc.h, cplex.h, soplex.h
21 lgf_reader.h, lgf_writer.h, dimacs.h, nauty_reader.h, graph_to_eps.h
A bits/graph_extender.h, bits/alteration_notifier.h

1.3 Conventions

Class names, members and code are set in monospace. A class is named without the namespace lemon, and a member is written as Class::member() when the class is not clear from the context. A graph has \(n\) nodes and \(m\) arcs (or edges), while \(C\) and \(U\) denote the largest absolute value of a cost and of a capacity when the data are integer. The complexities are those of the implementation, and the chapters say so when they differ from the bounds of the literature. Sections, figures, tables, algorithms, lemmas, theorems and exercises are numbered by chapter (lemmas and theorems with separate counters), and a proof ends with \(\square\). A program is named by the file of manual/examples/ that holds it, and therefore by the test manual_<name> that runs it (the hyphens of the name becoming underscores).