Skip to content

3. Graphs, items and maps

We are concerned in this chapter with the few ideas on which all the headers of the library are built, and which a reader needs before the data structures of Part II and the algorithms of Part III. A graph is a set of items (nodes, arcs and, if it is undirected, edges), which are handled by small value types, visited by iterators and compared with the constant INVALID. Data are attached to the items only through maps, i.e., objects that associate a value with each item. The requirements on a graph, a map or a heap are written as concept classes, against which a type can be checked at compile time, and the algorithms are classes that follow (with few exceptions) one pattern of construction, execution and query. These ideas come from LEMON, whose design is described in Dezső, Jüttner and Kovács 2011, and abLEMON keeps them unchanged. Section 3.1 gives a first example; sections 3.2 to 3.4 describe the items, the iterators and the maps, section 3.5 the concepts, section 3.6 the algorithm classes, and section 3.7 the tolerances with which the library compares numbers that may carry a rounding error, together with the numeric constants and the traits of the types, while section 3.8 collects the exercises. In all the chapters we write \(D=(V,A)\) for a digraph and \(G=(V,E)\) for an undirected graph, with \(n=|V|\) and \(m=|A|\) (or \(m=|E|\)), and \(\delta^+(v)\) and \(\delta^-(v)\) for the sets of the arcs that leave and enter a node \(v\).

3.1 A first example

We begin with the digraph of Figure 3.1, with four nodes \(s\), \(a\), \(b\), \(t\) and five arcs, each with a cost, on which we want the shortest path from \(s\) to \(t\). A program that computes it goes through the four steps that every use of the library repeats. (i) It builds the structure, here a ListDigraph (chapter 4), which is empty when constructed and grows by addNode() and addArc( s , t ), each of which returns a handle to the new item (section 3.2). (ii) It attaches the costs to the arcs by a map, here a ListDigraph::ArcMap< int >, which holds one int for each arc and is read and written by cost[a] (section 3.4), since an arc has no field that a user could set. (iii) It constructs the algorithm, the class template Dijkstra of chapter 10, on the digraph and on the map, and runs it from the source by run( s ). (iv) It reads the results by queries such as dist( t ) and predNode( v ) (section 3.6), the second of which gives the node that precedes \(v\) on the shortest path found, so that the path is followed backwards from \(t\) to \(s\). The program manual/examples/03-first-program.cc (the test manual_03_first_program) follows these steps, prints the identifiers of the nodes of the path, and checks that the distance of \(t\) is 5. As all the programs of the manual, it is built and run by the tests of the library, while how a user program is built against an installed abLEMON is explained in chapter 2.

Figure 3.1. The digraph of the first example, with the cost of each arc; the arcs of the shortest path from s to t, of cost 5, are in the primary colour.

3.2 Items, identifiers and INVALID

A digraph has two kinds of items, of the types Node and Arc nested in its class. An undirected graph also has the type Edge: each edge \(e\) has two end nodes, u( e ) and v( e ), and it is represented by two arcs of opposite directions, which the graph creates and erases together with the edge. A bipartite graph (BpGraph) is an undirected graph whose nodes are either red or blue, and whose edges join a red node to a blue one; its types RedNode and BlueNode derive from Node. All these types are handles. An object of type Node does not contain a node but identifies one, typically by an integer index, and it is "cheap" to copy, to compare and to store. We remark that a handle is meaningful only together with its graph (the same index may identify another node in another graph), and the graph is therefore passed explicitly to each function that reads the structure, as in g.source( a ) or g.id( v ).

The constant INVALID. In lemon/core.h one finds the empty type Invalid (whose operators ==, != and < find any two of its objects equal) and its only object, INVALID. Indeed, each handle and each iterator converts from INVALID, and comparing an item with INVALID reveals whether it identifies an item at all. In this way an iteration ends (section 3.3), a function such as findArc() of chapter 4 returns the absence of a result, and an algorithm marks a node without a predecessor (e.g., the source of a search has predArc( s ) == INVALID). Also, the handles have the operators ==, != and <, the last of which is an artificial order (unrelated to the order of iteration, and, in the structures of chapter 4, the order of the identifiers) that lets the handles be the keys of ordered containers.

abLEMON

A default-constructed handle (ListDigraph::Node v;) is INVALID in all the graph structures and adaptors of abLEMON, while in LEMON 1.3.1 its index was left indeterminate in most of them (and the maps copied that indeterminate value when they built their default values). Yet, the concepts still say that the default constructor leaves the value undefined; hence, a generic algorithm should assign INVALID explicitly instead of relying on it.

Identifiers. Each item has an integer identifier, g.id( item ), which is unique among the items of its kind in the graph and does not change while the item exists, while g.nodeFromId( i ), g.arcFromId( i ) and g.edgeFromId( i ) give the item back, and g.maxNodeId(), g.maxArcId() and g.maxEdgeId() give an upper bound on the identifiers in use. Identifiers are the indices of the vectors that store the items and the values of the maps, and they are not necessarily contiguous: a ListDigraph, e.g., keeps the identifiers of the erased nodes on a free list and gives them to the next nodes added. An erased node may thus become valid again, and the structures that allow erasing (the List ones, and the Smart ones through their snapshots), as well as StaticGraph and FullBpGraph, have the function valid( item ), which returns whether a handle identifies an item of the graph at present. In fact, a bipartite graph also numbers the red and the blue nodes separately. Thus, g.id( RedNode ) is the index of a node among the red ones (bounded by g.maxRedId()), and it usually differs from g.id( Node ) of the same node. Finally, the generic forms g.maxId( Node() ) and g.fromId( i , Node() ), with a dummy item that selects the kind, serve the templates that work on any kind of item.

Edges and arcs. Each edge has an inherent orientation, from u( e ) to v( e ), given by the order in which its end nodes were passed to addEdge( u , v ). Of the two arcs of an edge, the forward one goes from u( e ) to v( e ) and the backward one from v( e ) to u( e ). These arcs are g.direct( e , true ) and g.direct( e , false ), while g.direct( e , w ) is the arc of \(e\) whose source is the node w. Also, g.direction( a ) is true for a forward arc and g.oppositeArc( a ) is the other arc of the same edge. An Arc converts to the Edge it represents (so that an edge map can be read with an arc as its key), and g.oppositeNode( w , e ) is the end of \(e\) other than w. In the undirected structures of chapter 4 (the list, smart, static and implicit graphs, and the edge sets) the edge of identifier \(i\) is represented by the arcs of identifiers \(2i+1\) (forward) and \(2i\) (backward), as Figure 3.2 shows. Since the adaptors of chapter 5 number their arcs in other ways, a program should usually use direct() and direction() instead of this arithmetic. A loop, i.e., an edge with \(u(e)=v(e)\), also has two arcs, each of which leaves and enters the same node.

Figure 3.2. An edge e of a ListGraph, with its inherent orientation from u(e) to v(e), and the two arcs that represent it, with their identifiers.

In a bipartite graph the inherent orientation of each edge goes from its red end to its blue end, which g.redNode( e ) and g.blueNode( e ) return, while g.red( v ) and g.blue( v ) give the colour of a node and g.asRedNode( v ) converts a Node to a RedNode (returning INVALID if the node is blue). Its variant g.asRedNodeUnsafe( v ) omits the check, which makes it somewhat faster, but it is correct only on red nodes and on INVALID; the functions of the blue nodes are symmetric. Since an undirected graph is also a digraph (with two arcs for each edge), any algorithm written for digraphs runs on it. Furthermore, the function undirected( g ) of lemon/core.h returns whether the type of g is undirected; its value is selected at compile time from the tag UndirectedTag that the undirected structures define.

3.3 Iterators and ranges

Items are visited by iterators, which are nested classes of the graph. NodeIt, ArcIt and EdgeIt visit all the nodes, arcs and edges; OutArcIt and InArcIt visit the arcs that leave and enter a node, IncEdgeIt the edges incident to a node, and, in a bipartite graph, RedNodeIt and BlueNodeIt the nodes of one colour. An iterator derives from the handle of the items it visits; hence, it is used wherever a handle is expected, with no dereferencing, and the usual loop is

for( ListDigraph::OutArcIt a( g , v ) ; a != INVALID ; ++a )
 total += cost[ a ];

in which the iterator is constructed on the graph (and on the node, for the iterators of incident items), advanced by ++, and compared with INVALID, which it becomes after the last item. Each iterator also has a constructor from the graph and an item, which continues the iteration from that item.

We call base node of an incidence iterator it the node on which it was constructed. Then g.baseNode( it ) is the base node and g.runningNode( it ) the other end of the current item: for OutArcIt they are the source and the target of the arc, for InArcIt the target and the source, and for IncEdgeIt the node of the iterator and the opposite end of the edge. In an undirected graph OutArcIt and InArcIt visit the arcs of the incident edges in the two directions, whereas IncEdgeIt visits the edges. A loop is visited twice by the first two, once for each of its arcs, and also twice by IncEdgeIt in ListGraph and SmartGraph. Note that the order of iteration is not specified by the concepts, and it differs between the structures (e.g., ListDigraph, SmartDigraph and the static structures visit their nodes from the last added, or the one of largest index, to the first); a program should not depend on it.

For the range-based for of C++11, the graphs also have functions that return a range of the same items, since a range is easier to pass to a loop or to an algorithm than a pair of iterators. These are g.nodes(), g.arcs(), g.edges(), g.outArcs( v ), g.inArcs( v ), g.incEdges( v ) and, in a bipartite graph, g.redNodes() and g.blueNodes(), so that one may write for (auto a : g.outArcs( v )). A range holds a pair of wrapped iterators (LemonRangeWrapper1 and LemonRangeWrapper2 of lemon/bits/stl_iterators.h), which define the member types of an input iterator, a dereference that returns the item, and a postfix ++; hence, the algorithms of the standard library that read an input range (e.g., std::count_if or std::copy) work on them too.

abLEMON

The ranges come from the repository of LEMON after its release 1.3.1, and they are distributed for the first time in abLEMON. Their iterators define the member types of an input iterator directly, instead of deriving them from std::iterator, which C++17 deprecated.

Writing the names of the nested types becomes tedious in a function that uses several of them, and lemon/core.h has macros that define them in the current scope. DIGRAPH_TYPEDEFS( Digraph ) defines Node, NodeIt, Arc, ArcIt, InArcIt and OutArcIt, with the maps BoolNodeMap, IntNodeMap, DoubleNodeMap, BoolArcMap, IntArcMap and DoubleArcMap of that type. GRAPH_TYPEDEFS( Graph ) adds Edge, EdgeIt, IncEdgeIt and the three edge maps BoolEdgeMap, IntEdgeMap and DoubleEdgeMap, and BPGRAPH_TYPEDEFS( BpGraph ) adds RedNode, RedNodeIt, BlueNode, BlueNodeIt and their maps (BoolRedNodeMap and so on). Inside a template, where the graph type is a dependent name, one writes TEMPLATE_DIGRAPH_TYPEDEFS( GR ) (and its counterparts TEMPLATE_GRAPH_TYPEDEFS and TEMPLATE_BPGRAPH_TYPEDEFS), which inserts the keywords typename and template that the compiler then requires. In abLEMON the types defined by these macros are marked as possibly unused by the macro LEMON_UNUSED_TYPEDEF (with GCC and Clang, the attribute unused; empty with the other compilers); hence, a function that uses only some of them compiles without warnings. LEMON 1.3.1 turned the warning on unused local typedefs off by a pragma, for the whole compilation of the user.

3.4 Maps

A graph stores its structure and no other datum. A cost, a capacity, a flow, a label or the distance computed by an algorithm is kept in a map. This is an object that has the types Key and Value and that offers operator[]( key ) to read a value, set( key , value ) to write one, or both (the concepts that make this precise are given in chapter 6, together with the maps of lemon/maps.h). Each graph structure provides the standard maps of its items, namely NodeMap< V >, ArcMap< V >, EdgeMap< V > and, in a bipartite graph, RedNodeMap< V > and BlueNodeMap< V >. Such a map stores a value of type V for each item of the graph on which it is constructed, in a vector indexed by the identifiers, and map[item] reads and writes it in \(O(1)\) time. Furthermore, the map follows the changes of the graph, since the graph informs its maps of each item added or erased (cf. appendix A): a map constructed on g gets a slot for each item added to g afterwards, whose value is V() (not the value given to the constructor), and it drops the slot of each item erased. Of the two constructors, NodeMap( g ) value-initializes the values and NodeMap( g , value ) sets them all to value; we remark that the standard maps can be neither copied nor assigned, and the values of one map are copied into another by mapCopy() of chapter 6.

An algorithm reads and writes its data through maps whose types are template parameters; hence, any object with the right interface may be passed in place of a standard map, which is often (but not always) the most convenient choice. A length equal for all the arcs may be a ConstMap, and a cost may be computed on the fly from two other maps by an arithmetic adaptor (e.g., their difference). Also, a result may go to a map of the caller or to a NullMap, which discards what is written to it. The program manual/examples/03-items-maps.cc (the test manual_03_items_maps) checks the statements of sections 3.2 to 3.4 on a ListGraph. These are the two arcs of an edge and their directions, the default-constructed INVALID, the iterators and the ranges, the value V() that a map gives to an edge added after it, the reuse of an identifier after an erasure, and a function template whose graph type is checked against the concept of undirected graphs (section 3.5).

3.5 Concepts and their checking

A function template of the library (an algorithm, a map adaptor, a copy function) accepts any type that offers the operations it uses. These operations are written down, once for each kind of object, as a concept class in lemon/concepts/. A concept class is an archetype, which declares with empty bodies the types and the functions that the concept requires (e.g., concepts::Digraph declares Node, Arc, the iterators, source(), target(), id() and the maps); hence, a template that compiles with the archetype uses only what the concept guarantees. Each concept class also contains a nested template Constraints< T >, whose member function constraints() exercises those operations on a candidate type T. Those of the graphs (concepts::Digraph, concepts::Graph and concepts::BpGraph, with the components of which they are made) are described in chapter 4. Those of the maps are in chapter 6, those of the heaps in chapter 7, and the others (paths, maximum flows, minimum cost flows, minimum mean cycles) in the chapters of their families.

Checking is done by two function templates of lemon/concept_check.h. A call checkConcept< Concept , T >() takes the address of Concept::Constraints< T >::constraints, which forces the compiler to instantiate that function. If T lacks one of the operations the concept requires, the compilation fails with an error that names it; at run time the call does nothing. Its older form function_requires< C >() does the same for a class C whose member constraints() is to be instantiated (a form that is now rarely used). Both are empty when NDEBUG is defined (i.e., in an optimized build without assertions, where they check nothing), and in a build without NDEBUG they cost only compilation time. In the library, the tests check each graph structure, map and heap against its concept (e.g., test/digraph_test.cc calls checkConcept< Digraph , ListDigraph >()), and a user who writes a new structure checks it in the same way (appendix A). A generic function may also call checkConcept on its template parameters, as the function incidentWeight() of manual/examples/03-items-maps.cc does, in which case a wrong argument is reported where the function is called instead of deep inside its body. Finally, the object ignore_unused_variable_warning, called with any arguments, silences the warnings on the variables that a function constraints() declares and does not use.

abLEMON

ignore_unused_variable_warning is an object of a class with a variadic operator(), instead of a set of overloaded functions as in LEMON 1.3.1. Hence, an unqualified call to a function of the same name of another library is no longer made ambiguous by argument-dependent lookup on the types of lemon.

3.6 The algorithm classes

Most algorithms of the library are class templates that share one pattern, which we describe here on Dijkstra (of lemon/dijkstra.h, cf. chapter 10), while the chapters of Part III give the template parameters, the defaults and the queries of each class, and they say where a class departs from the pattern.

Template parameters and traits. The first parameters of the class are the types of its input; thus, Dijkstra< GR , LEN , TR > takes the type GR of the digraph (by default ListDigraph) and the type LEN of the map of the lengths (by default GR::ArcMap< int >). Its last parameter TR is a traits class, by default DijkstraDefaultTraits< GR , LEN >. It defines the other types used by the algorithm (the heap with its cross reference map, the maps of the predecessors, of the distances and of the processed nodes, the operations on the lengths), each with a static function that creates an object of that type; the lengths have the type LEN::Value, and the default heap is a BinHeap on them.

Named template parameters. We remark that a traits class is rarely written by hand, since each of its types can be replaced by a named template parameter. This is a nested template of the algorithm class, whose member Create is the class with that type replaced. For instance, Dijkstra< GR , LEN >::SetDistMap< M >::Create is a Dijkstra that writes the distances into a map of type M, which the caller passes by distMap( m ), and SetHeap< H , CR > replaces the heap and its cross reference map (cf. chapter 7), while SetOperationTraits< T > replaces the operations on the lengths. Named parameters can be chained, as in SetPredMap< P >::Create::SetDistMap< M >::Create. A type replaced in this way is not created by the algorithm (its creating function only asserts), and the caller must give the object before the first run; the variants SetStandardHeap< H > and SetStandardProcessedMap instead let the algorithm create the new type itself.

Execution. A constructor takes the input objects (here the digraph and the length map) by reference, and they must outlive the algorithm, while the maps that the algorithm writes are created by it at the first run, unless the caller has given them by the setter functions predMap(), distMap(), processedMap() and heap() (which takes the heap and its cross reference map). Each setter returns a reference to the algorithm, so that the calls can be chained, and lengthMap() and operationTraits() replace the input in the same way. The simplest way to execute the algorithm is run( s ), which computes the shortest paths from s to all the nodes reachable from it, while run( s , t ) stops as soon as t is processed and returns whether t is reachable. For a finer control, run( s ) is the sequence init(), addSource( s ), start() of Algorithm 3.1, and these functions may also be called one by one. Thus, init() resets the data of the nodes, and addSource( s , d ) adds a source with the initial distance d (zero by default); one may give several sources, a node already in the heap keeps the smaller of its two distances, and a node already processed is left alone. Then start() runs the search until the heap is empty, start( t ) stops when t is processed, and start( nm ) stops at the first node v with nm[v] true that reaches the top of the heap, which it processes and returns (or INVALID if there is none). Between these calls, processNextNode() performs one step and returns the node it processed, nextNode() gives the node that the next step will process (INVALID if the heap is empty), and emptyQueue() and queueSize() describe the heap.

Algorithm 3.1 (The run of an algorithm class, on Dijkstra).

run(s):
 1  init()                     pred[v] = INVALID, processed[v] = false and
                               the state of v PRE_HEAP for every node v
 2  addSource(s, 0)            push s with priority 0
 3  start():
 4    while not emptyQueue()
 5      v = processNextNode():  pop the node v of least priority p,
 6                              dist[v] = p, processed[v] = true;
 7                              for each arc a = (v, w) of delta+(v):
 8                                push w with p + len[a] if w is PRE_HEAP,
 9                                or decrease it to p + len[a] if w is in
10                                the heap with a larger priority;
11                                then pred[w] = a

With nonnegative lengths, the priority of each node when it leaves the heap is its distance from the sources, and the arcs pred form a forest of shortest paths; this correctness of Algorithm 3.1 is Theorem 10.2 of chapter 10; the same theorem bounds the run by \(n\) pushes and pops and \(m\) decreases of a priority, whose cost depends on the heap (chapter 7). Since the nodes leave the heap in nondecreasing order of distance, run( s , t ) and start( t ) give the distance of t as soon as t has left it.

Queries. After a run the results are read by query functions, named after the objects of the problem: dist( v ), predArc( v ), predNode( v ) and path( t ) for the shortest paths, currentDist( v ) for the priority of a node still in the heap, reached( v ) and processed( v ) for the state of a node, and distMap() and predMap() for the maps. A query is meaningful only after a run that reached the node (and, for dist( v ), that processed it): this is its precondition, stated in the documentation of each function, and its value remains available until the next init().

Function-type interface. Some algorithms (among them bfs(), dfs() and dijkstra()) also have a function that returns a "wizard" object, on which the optional outputs are given by name before the run, as in

bool found = dijkstra( g , length ).distMap( d ).path( p ).run( s , t );

which writes the distances into d and the path from s to t into p. Such a wizard constructs the algorithm for the run, together with the maps that were not given, and destroys them afterwards. It is rather convenient in simple cases, whereas the class gives access to the intermediate state and to repeated runs. The program manual/examples/03-algorithm-pattern.cc (the test manual_03_algorithm_pattern) goes through the pattern on a SmartDigraph. It uses the named parameter SetDistMap, the separate steps init(), addSource() and start( t ), a run with two sources at different initial distances, the queries on a node that is not reachable, and the function-type interface.

3.7 Tolerances and numeric traits

An algorithm that works on floating-point data compares numbers that may carry a rounding error, and a test such as x == 0 or a < b then gives an answer that depends on the last bits of the operands. In lemon/tolerance.h the class template Tolerance< T >, whose type Value is T, collects the comparisons that the algorithms need. Each of them returns true only if the relation holds surely, i.e., even allowing for an error up to a threshold \(\varepsilon\ge 0\), as follows:

\[ \begin{array}{ll} \texttt{less(a, b)}: & a+\varepsilon<b,\\ \texttt{different(a, b)}: & \texttt{less(a, b)} \lor \texttt{less(b, a)},\\ \texttt{positive(a)}: & \varepsilon<a,\\ \texttt{negative(a)}: & a<-\varepsilon,\\ \texttt{nonZero(a)}: & \texttt{positive(a)} \lor \texttt{negative(a)}, \end{array} \tag{3.1} \]

where the sum \(a+\varepsilon\) is the one computed in the type T, while zero() returns 0. Its general version is meant for exact types (the integers, or a rational type), and its functions are static and compare exactly, i.e., as in (3.1) with \(\varepsilon=0\). Instead, the specializations for float, double and long double hold an \(\varepsilon\) in each object. It is set by the constructor (as in Tolerance< double > tol( 1e-8 )) or by tol.epsilon( e ), and read by tol.epsilon(); its default is \(10^{-4}\), \(10^{-10}\) and \(10^{-14}\), respectively (the last one being the double value \(10^{-14}\), widened, as lemon/base.cc defines it). The static functions defaultEpsilon() and defaultEpsilon( e ) read and change the default for the objects constructed afterwards, everywhere in the program. Any other type gets the general template, and a user who works with another inexact type writes a specialization with the same functions. The comparisons (3.1) have the following properties, which the algorithms rely on when they sort or compare values under a tolerance.

Lemma 3.1. Let \(\varepsilon\ge 0\), let the operands be numbers of T other than NaN, and let \(a\approx b\) mean that different( a , b ) is false. Then (i) less is irreflexive and transitive, i.e., a strict partial order, also when \(a+\varepsilon\) is rounded; (ii) \(\approx\) is reflexive and symmetric; (iii) for \(\varepsilon=0\), \(a\approx b\) holds if and only if \(a=b\); (iv) for \(\varepsilon>0\) and in exact arithmetic, \(\approx\) is not transitive, and \(a\approx b\) holds if and only if \(|a-b|\le\varepsilon\).

Proof. Let \(\mathrm{fl}(x)\) be the rounding of \(x\) to T, which is monotone and leaves the numbers of T unchanged. (i) Since \(a+\varepsilon\ge a\), one has \(\mathrm{fl}(a+\varepsilon)\ge\mathrm{fl}(a)=a\), and therefore \(\mathrm{fl}(a+\varepsilon)<a\) never holds. If \(\mathrm{fl}(a+\varepsilon)<b\) and \(\mathrm{fl}(b+\varepsilon)<c\), then \(\mathrm{fl}(a+\varepsilon)<b\le\mathrm{fl}(b+\varepsilon)<c\) by the same argument on \(b\), i.e., less( a , c ). (ii) different( a , a ) is less( a , a ), which is false by (i), and different is symmetric by its definition. (iii) With \(\varepsilon=0\), different( a , b ) is \(a\ne b\) in the general template, and \(a<b\) or \(b<a\) in the specializations (since then \(\mathrm{fl}(a+0)=a\)), which for numbers other than NaN is again \(a\ne b\). (iv) In exact arithmetic different( a , b ) is \(a+\varepsilon<b\) or \(b+\varepsilon<a\), i.e., \(|a-b|>\varepsilon\). Hence, \(a=0\), \(b=\varepsilon\) and \(c=2\varepsilon\) give \(a\approx b\) and \(b\approx c\), but not \(a\approx c\). \(\square\)

We stress that the threshold is absolute, i.e., \(\varepsilon\) in (3.1) does not scale with the operands; hence, Tolerance< double > finds \(10^{20}\) and \(10^{20}+10^5\) surely different (although their relative gap is \(10^{-15}\)), and \(10^{-12}\) and \(2\cdot10^{-11}\) equal (although one is 20 times the other). Its default suits, therefore, data of "moderate" magnitude, and the algorithms that take a Tolerance (the maximum flow and minimum cut algorithms, among others) have a function tolerance() by which the caller sets one that fits the scale of the data. On the other hand, the minimum cost flow algorithms keep tolerances of a different kind, which are relative to the data unless the caller sets them (cf. chapter 13). The program manual/examples/03-tolerance.cc (the test manual_03_tolerance) checks the exact comparisons of the general template, the default thresholds, the two examples above of the absolute threshold, and the function countNodes() discussed at the end of the section.

Numeric constants. The "small" header lemon/math.h includes <cmath> and defines, in the namespace lemon, the constants E, LOG2E, LOG10E, LN2, LN10, PI, PI_2, PI_4, SQRT2 and SQRT1_2, as long double values written with 35 significant digits. It also defines isNaN( v ), which tests v != v on a double, and round( r ), which rounds a double to the nearest integer with the halves away from zero, i.e., \(\lfloor r+1/2\rfloor\) for \(r>0\) and \(\lceil r-1/2\rceil\) otherwise. In abLEMON the constants (and the object ignore_unused_variable_warning of section 3.5) are declared by the macro LEMON_CONSTANT of lemon/config.h, i.e., inline constexpr from C++17 on and const before, so that the C++20 module lemon can export them.

Traits of graphs and maps. A user rarely includes lemon/bits/traits.h directly; it holds the templates by which the library selects an implementation at compile time from the properties of a type. Thus, ItemSetTraits< GR , Item > gives, for a graph type and a kind of item, the iterator (ItemIt), the map template (Map< V >::Type) and the notifier of the items, and a template can be written once for nodes, arcs and edges. Also, MapTraits< M > gives whether a map is a reference map and which types its operator[] returns (chapter 6), and MatrixMapTraits< M > does the same for the maps with two keys. Other templates detect the tags that a structure may define (NodeNumTagIndicator< GR > and its siblings, whose member value is true when the tag is there). Among these tags, NodeNumTag, ArcNumTag and EdgeNumTag mean that the structure counts its items in \(O(1)\) time, FindArcTag and FindEdgeTag that it finds the arc between two nodes directly, BuildTag that it is built in one call from another graph, and UndirectedTag that it is undirected. Typically, a counting function of lemon/core.h is selected by these tags; indeed, countNodes( g ) calls g.nodeNum() on a structure with NodeNumTag, in \(O(1)\) time, and scans the nodes with NodeIt otherwise, in \(O(n)\) time, and the other utilities of chapter 4 (countArcs(), findArc(), the copies) are selected in the same way, by enable_if on the tag.

3.8 Exercises

Exercise 3.1. Write a variant of the first example that prints the nodes of the shortest path from \(s\) to \(t\) in the order in which the path visits them, by dijkstra.path( t ) and the path utilities of chapter 8 instead of a loop on predNode(). (The program manual/examples/03-first-program.cc gives the distance against which to check the result.)

Exercise 3.2. Write a function template that, for any undirected graph g and edge map w, returns the edge of largest weight incident to a node (or INVALID if the node is isolated), and check its graph type by checkConcept; call it on a ListGraph and on a SmartGraph. (The function incidentWeight() of manual/examples/03-items-maps.cc is a model.)

Exercise 3.3. Build a ListGraph with a loop and two parallel edges, and count, for one of their end nodes, the items visited by OutArcIt, InArcIt and IncEdgeIt. Explain the counts by the representation of Figure 3.2. (The test test/graph_test.cc checks the degrees of such graphs.)

Exercise 3.4. By Lemma 3.1, the equality under a tolerance is not transitive. Discuss what this implies for an algorithm that groups values by equality, and show that grouping the sorted values by cutting where two consecutive ones are different() gives groups that do not depend on the order of the input, although two values of one group may be different. (The program manual/examples/03-tolerance.cc checks the threshold.)

Exercise 3.5. Replace the length map of the program of section 3.6 by a map of type ConstMap< SmartDigraph::Arc , double > with value 1 (cf. chapter 6), so that Dijkstra computes the number of arcs of the shortest paths, and check the result against a breadth-first search (chapter 9). (The test test/bfs_test.cc shows the breadth-first search.)