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.
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.
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
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
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:
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.)