8. Paths and auxiliary structures¶
This chapter collects the data structures and the tools that the algorithms of
Part III use internally, and that a program often needs around them. They are
the paths of lemon/path.h (with the concept of lemon/concepts/path.h), the
union-find structures of lemon/unionfind.h, the elevator of
lemon/elevator.h, the plane geometry of lemon/dim2.h and the radix sorts
of lemon/radix_sort.h; then come the random numbers of lemon/random.h, the
counters and timers of lemon/counter.h and lemon/time_measure.h, the
colours of lemon/color.h, and the exceptions, assertions and parser of the
command line of lemon/error.h, lemon/assert.h and lemon/arg_parser.h.
The first three are data structures whose costs matter for the algorithms
built on them, and we give them most of the chapter. We describe the others
rather more briefly, but with all their members, since the reader of a program
that uses them should find each call here.
8.1 Paths¶
A path of a digraph \(G=(N,A)\) is a sequence of arcs \((a_1,\dots,a_k)\) such
that the target of \(a_i\) is the source of \(a_{i+1}\) for \(i=1,\dots,k-1\). Its
length, in the sense of the path classes, is the number \(k\) of its arcs (the
length under a cost map is computed by the user,
cf. §10.1). The four path classes of abLEMON
store the sequence of arcs and no other data, i.e., they do not store the
nodes, they cannot give the source of a path of no arcs, and they do not check
that consecutive arcs are joined (which is left to the function
checkPath()). All four take the digraph type as their only template
parameter GR, and define the types Digraph and Arc.
Their common interface is made of a default constructor, a constructor and an
assignment from a path of any type (both implemented by pathCopy()),
length(), empty() and clear(). The arcs are read by nth( n ) and by
its alias operator[], by front() and back(), and by the iterator
ArcIt, which converts to Arc and runs from the first arc to INVALID;
nthIt( n ) places an ArcIt on the \(n\)-th arc, and arcs() wraps ArcIt
in a range for the range-based for of C++11. The classes differ in how the
arcs are stored, which decides what can be done and at which cost (Table 8.1).
Table 8.1. The path classes of lemon/path.h
and the cost of their operations, for a path of \(k\) arcs ("am." stands for
amortized, "no" for an operation that the class does not have).
| class | storage | nth(i) |
addFront, eraseFront |
addBack, eraseBack |
length() |
other |
|---|---|---|---|---|---|---|
Path |
two vectors | \(O(1)\) | \(O(1)\) am. | \(O(1)\) am. | \(O(1)\) | |
SimplePath |
one vector | \(O(1)\) | no | \(O(1)\) am. | \(O(1)\) | |
ListPath |
doubly linked list | \(O(i)\) | \(O(1)\) | \(O(1)\) | \(O(k)\) | splice, split in \(O(1)\) |
StaticPath |
one array | \(O(1)\) | no | no | \(O(1)\) | read only |
In Path the arcs added at the front are kept in one vector, in reverse
order, and those added at the back in another. When one of the two vectors is
empty and an arc must be erased from its end, half of the other vector is
moved into it. Hence, eraseFront() and eraseBack() cost \(O(1)\) amortized
over any sequence of operations. SimplePath keeps one vector and grows only
at the back, which makes it somewhat faster than Path when the arcs are only
added at the back. A ListPath allocates one node per arc; hence, nth()
walks \(i\) nodes and length() walks the whole list; however, it is the only
class that can be cut and joined in constant time, which is indeed the reason
to prefer it. Its member spliceBack( tpath ) moves all the arcs of tpath
to the back of the path, and spliceFront( tpath ) to its front, leaving
tpath empty; splice( it , tpath ) inserts them before the arc of the
iterator it (at the back if it is INVALID). Conversely,
split( it , tpath ) moves the arcs from it on into tpath, after clearing
it (the clearing being the only part that may cost more than \(O(1)\)). Finally,
a StaticPath is an array of exactly \(k\) arcs, which can only be built from
another path or assigned; it is the most compact of the four, and usually the
one to choose for storing many paths. The bounds of Table 8.1 follow from the
storage, except the amortized one of Path, which needs an argument.
Theorem 8.1. Starting from an empty Path,
any sequence of \(q\) calls of addFront(), addBack(), eraseFront() and
eraseBack() takes \(O(q)\) time.
Proof. Let \(f\) and \(b\) be the numbers of arcs in the vector of the front and in that of the back, and let \(\Phi=|f-b|\), which is 0 at the start and never negative. An addition, or an erasure from a vector that is not empty, takes \(O(1)\) time (amortized over the growth of the vector) and changes \(\Phi\) by at most 1. An erasure from an empty vector, say the front one, with \(b=r\ge 1\) arcs in the other, erases the first arc of the back vector, moves the next \(\lfloor r/2\rfloor\) arcs into the front vector and shifts the remaining \(r-1-\lfloor r/2\rfloor\) down, in \(O(r)\) time; afterwards \(\Phi\le 1\), while it was \(r\) before. Hence, with a suitable constant \(c\), the amortized cost (the actual cost plus \(c\) times the change of \(\Phi\)) of each call is \(O(1)\). The total actual cost is at most the total amortized cost, since \(\Phi\ge 0\) at the end. \(\square\)
We remark that the copy assignment of each path class calls pathCopy(),
which clears the target before reading the source, only when the source is
another path; hence, assigning a path to itself (p = p) leaves it unchanged.
abLEMON
In LEMON 1.3.1 the copy assignment of Path, SimplePath, ListPath
and StaticPath called pathCopy() also on the path itself, which it
emptied. The test path_test assigns each of the four to itself.
The concept concepts::Path of lemon/concepts/path.h states this common
interface (a path type, the copy from another path, length(), empty(),
clear(), ArcIt and arcs()), and the four classes conform to it. A second
concept, concepts::PathDumper, describes the objects that the search
algorithms of chapters 9 and 10 return from their queries path(). A path
dumper has length(), empty() and either an ArcIt or, when its type
RevPathTag is True, a RevArcIt that lists the arcs from the last to the
first. In the library, the dumpers are PredMapPath and PredMatrixMapPath
of lemon/bits/path_dump.h, which follow a map of predecessor arcs back from
a node, and therefore list the arcs in reverse. They are not meant to be kept,
but to be assigned to a path, as in Path<ListDigraph> p = dijkstra.path(t);
(note that an ArcIt built on the temporary that such a conversion creates
would point to a destroyed object).
All constructors and assignments of a path call pathCopy( from , to ). This
function checks at compile time that from is a path dumper, and then chooses
among four ways of copying. If from lists its arcs backwards (RevPathTag),
the arcs are added to the front of to, else to its back; and if to defines
the type BuildTag (as the four classes do), its member build() or
buildRev() fills it in one pass, after reserving the memory, in place of a
sequence of addBack() or addFront(). This choice is made by the helpers
RevPathTagIndicator, BuildTagIndicator, PathCopySelector,
PathCopySelectorForward and PathCopySelectorBackward of the namespace
_path_bits, which are not part of the interface. Also,
copyPath( to , from ) is the same copy with the arguments in the opposite
order, kept only for compatibility with older programs.
Four other utilities read a path together with its digraph. The predicate
checkPath( g , p ) is true if the target of each arc of p is the source of
the next one (an empty path being consistent), and pathSource( g , p ) and
pathTarget( g , p ) return the source of the first arc and the target of the
last one, or INVALID for an empty path. Next, the iterator
PathNodeIt< Path > lists the \(k+1\) nodes of a consistent path from its
source to its target, given the digraph and the path in its constructor; a
third argument gives the node to start from, which is needed only for a path
of no arcs. Also, pathNodes( g , p ) wraps this iterator in a range, and
for (auto u : pathNodes( g , p )) then visits the nodes in order.
abLEMON
The allocator of ListPath constructs and destroys its nodes through
std::allocator_traits, since C++20 removed the members construct() and
destroy() of std::allocator that LEMON 1.3.1 called; the paths
therefore compile from C++11 to C++23. The alias operator[] of nth()
and the ranges of arcs() and pathNodes() come from the development of
LEMON after its release 1.3.1, which did not distribute them.
The program manual/examples/08-paths.cc (the test manual_08_paths) builds
a path at both ends and copies it into the other three classes. Then it splits
and splices a ListPath, lists the nodes of a path, and copies the path
dumper of a search of Dijkstra (cf. §10.2)
into a Path.
8.2 Union-find structures¶
A union-find structure maintains a partition of a finite set of items into classes under two operations: the union of the classes of two items, and the find of the class of an item, whose answer is a representative of the class, the same for all its items. It is the structure behind Kruskal's algorithm (§11.1), where the classes are the components of the forest grown so far, and behind the blossoms of the weighted matching algorithms of chapter 17. Each class is stored as a tree whose root is the representative and whose other items point to their parents. A find walks from the item to the root, and a union makes one root the child of the other. Two rules keep the trees shallow: the union by size puts the root of the tree with fewer items under the root of the other, and the path compression makes the items met during a find point to the root (Figure 8.1).
Lemma 8.1. With the union by size, a tree of \(s\) items has depth at most \(\log_2 s\), whatever finds (with or without compression) are made.
Proof. The compression only shortens paths, and we may ignore it. An item gets deeper only when the root of its tree is put under another root, by a union with a tree at least as large; the tree that contains it then at least doubles. Since a tree has at most \(s\) items, this happens at most \(\log_2 s\) times to each item. \(\square\)
Theorem 8.2. With the union by size and the path compression, any sequence of \(n\) insertions and \(m\ge n\) finds and unions takes \(O(m\,\alpha(m,n))\) time, where \(\alpha\) is the inverse of Ackermann's function, which is at most 4 for any \(n\) that can be stored.
Proof sketch. Each union costs \(O(1)\) after its two finds, and a find costs \(O(1)\) plus the number of items whose parent it changes. One groups the items by the logarithm of the size of their subtree, which by Lemma 8.1 grows along each path to the root, and then the levels into blocks of exponentially growing ranges, as many as the inverse of Ackermann's function allows. A compression changes the parent of an item either for the last time in its block, which is charged to the find (at most \(\alpha(m,n)\) such items per find), or to a parent in a strictly higher level of the same block, which is charged to the item. The charges to the items of each block add up to \(O(m)\) over the blocks. The bound was proved in Tarjan 1975 for the union by rank, and in Tarjan and van Leeuwen 1984, section 3, for the union by size and the other linking rules. A textbook proof, for the union by rank, is in Cormen et al. 2001, §21.4. \(\square\)
In practice, the cost of an operation is usually a small constant, and one may take it as such when choosing an algorithm.
All the classes of lemon/unionfind.h take as template parameter the type
IM of a map from items to integers. The items are the keys of IM
(typically the nodes, arcs or edges of a graph), and the map, given to the
constructor by reference, stores the index of each item in the internal
vectors. From then on the map belongs to the structure: writing into it
corrupts the structure, and each item must be added with insert() before it
is used in another operation.
UnionFind< IM > is the plain structure, with four operations and clear().
Here insert( a ) makes a a singleton class and returns its index, and
find( a ) returns the index of the representative of the class of a, an
integer between 0 and the number of the items inserted, minus one (the index
that insert() returned for that item). A call join( a , b ) returns
false if a and b are already in the same class, and otherwise unites the
two classes and returns true; size( a ) is the number of items of the
class of a. Algorithm 8.1 gives find() and join() as the code has them,
\(\mathit{parent}\) and \(\mathit{size}\) being stored in one vector of integers
(a root holds its size, negated, and any other item the index of its parent);
Lemma 8.1 and Theorem 8.2 apply to it. Note that clear() empties the vector
but leaves the map, whose old values must not be used before the items are
inserted again.
Algorithm 8.1 (Find and union in UnionFind).
find(x):
1 r := x
2 while r is not a root: r := parent(r)
3 while x != r: next := parent(x); parent(x) := r; x := next
4 return r
join(a, b):
1 ra := find(a); rb := find(b)
2 if ra = rb: return false
3 if size(ra) > size(rb): parent(rb) := ra; size(ra) := size(ra) + size(rb)
4 else: parent(ra) := rb; size(rb) := size(rb) + size(ra)
5 return true
Next, UnionFindEnum< IM > adds the enumeration of the classes and of the
items of each class, at the price of some memory and time per operation. Each
class keeps a circular doubly linked list of its items (its private records
ItemT and ClassT), and the classes are linked in a second list; it joins
by size and compresses the paths as UnionFind does. Its classes are
identified by integer ids rather than by representatives. Thus,
insert( item ) makes a new class and returns its id, insert( item , cls )
adds the item to the class cls, find( item ) returns the id of the class
of the item, and join( a , b ) returns the id of the united class, or \(-1\)
if the two items were already together. Also, size( cls ) is the number of
items of a class, and item( cls ) returns one of its items. This structure
can also undo: split( cls ) breaks a class into singletons, and
erase( item ) removes an item from its class, deleting the class if it
becomes empty. Finally, eraseClass( cls ) removes a whole class, and
clear() all of them. Its iterator ClassIt lists the ids of the classes,
and ItemIt, constructed from the structure and a class id, lists the items
of that class; both are compared with INVALID to stop.
Theorem 8.3. In a UnionFindEnum, insert(),
size(), item() and eraseClass() take \(O(1)\) time, find() and join()
the time of the finds of Theorem 8.2 plus \(O(1)\), and split( cls ) and
erase( item ) \(O(s)\), where \(s\) is the size of the class. In an
ExtendFindEnum, all the operations take \(O(1)\) time.
Proof. A join links the two roots and splices the two circular lists, in
\(O(1)\) after the finds. The split walks the list of the class once, making
each item a root of its own class, and the erasure makes the next item of the
list the root and walks the list once to point every other item to it, which
keeps the trees of depth one. The other operations of UnionFindEnum read or
relink a constant number of records. An ExtendFindEnum stores in each item
its class, which never changes; its other operations relink lists.
\(\square\)
We remark that clear() of UnionFindEnum empties the vectors of the items
and of the classes, with their lists of free records, so that the ids of the
classes inserted after it start again from 0.
abLEMON
In LEMON 1.3.1 UnionFindEnum::clear() emptied neither the vector of the
classes nor its list of free records, so that the records of the classes
alive before the call were never reused and the vector grew at each
cycle of insertions and clear(). The test unionfind_test checks the
ids of the classes after a hundred such cycles.
ExtendFindEnum< IM > is the simplification of UnionFindEnum in which the
classes are never united. It has the same two forms of insert(), find(),
item(), erase(), eraseClass(), clear(), ClassIt and ItemIt, and no
join(), a class therefore growing only by insertion; in exchange, find()
reads the class of an item in \(O(1)\) (Theorem 8.3). All three classes define
the types ItemIntMap (that is, IM) and Item.
HeapUnionFind< V , IM , Comp > attaches a priority of type V to each item
and keeps the item of least priority of each class, where Comp (by default
std::less< V >) decides what least means. It is stored as a \((2,16)\)-tree
whose leaves are the items, with a tournament for the minimum on the internal
nodes, i.e., each internal node has between 2 and 16 children (the root
excepted) and stores the least priority of its subtree and its item. Besides
the union, it supports the split of a class into the classes it was made of,
which the blossoms of the weighted matching algorithms need. A call
insert( item , prio ) makes a class of one item and returns its id, and
find( item ) returns the id of the alive class of the item. A call
join( begin , end ) unites the \(k\) classes whose ids are in the range (at
least two) and returns the id of the new class, and split( cls , out )
restores the \(k\) classes of which cls was made, and writes their ids into
the output iterator out.
Theorem 8.4. In a HeapUnionFind, insert()
takes \(O(1)\) time, find() and the changes of a priority \(O(\log n)\), where
\(n\) is the number of the items of the class, and join() and split() of \(k\)
classes \(O(k\log n)\), where \(n\) is the number of the items involved.
Proof sketch. A tree whose internal nodes have at least two children has
height at most \(\log_2 n\). A find walks from the leaf of the item to the root;
a decrease walks up from the leaf while the new priority beats the minimum of
the node, and an increase recomputes the minimum of the at most 16 children of
each ancestor whose minimum was the item; each of them is therefore
\(O(\log n)\). A join hangs the trees of the \(k\) classes on one another, in the
order of the range, under nodes of the right height, and splits a node into
two when it exceeds 16 children. This costs \(O(\log n)\) per class joined; a
split cuts the tree along the paths of the \(k\) subtrees that the join
recorded, and repairs the degrees and the minima along them (the private
members repairLeft() and repairRight()), with the same cost. The bounds
are those of the documentation of the class. The argument is the usual one for
the B-trees and their variants (Cormen et al.
2001, chapter 18). \(\square\)
Priorities are read by operator[]( item ) and written by set(item, prio),
decrease( item , prio ) and increase( item , prio ), the last two
requiring a priority that is not larger, or not smaller, than the present one
(and set() choosing between them); the class defines Value, Item,
ItemIntMap and Compare. The least priority of a class and its item are
given by classPrio( cls ) and classTop( cls ), and classRep( cls ) gives
an item of the class that does not depend on the priorities. Furthermore,
alive( cls ) is true if a class is not nested into another one (only alive
classes are returned by find()), and trivial( cls ) if it holds a single
item directly. Its iterators are ItemIt, which lists the items of a class,
and ClassIt, which lists the alive classes, or, constructed with a class id,
the classes of which cls is made. Finally, the structures ItemT, ClassT,
ItemNode and ClassNode of the header are the internal records of these
classes.
The program manual/examples/08-union-find.cc (the test
manual_08_union_find) computes the components of a small graph with
UnionFind, counting the edges that close a cycle. It also enumerates them
with UnionFindEnum, and follows the minimum of a class of HeapUnionFind
through a join, a decrease and a split.
8.3 The elevator¶
Push-relabel algorithms of maximum flow (Goldberg and Tarjan
1988; see chapter 12) keep a
label on each node, i.e., a lower bound on its distance to the sink in the
residual digraph, and a set of active nodes, those with a positive excess. At
each step they take an active node of highest label (in the variant that we
consider here), push its excess along the admissible arcs, and lift its label
when no arc is admissible. Furthermore, the gap heuristic of Cherkassky and
Goldberg 1997 moves to the
top all the nodes above a level that has become empty, since none of them can
reach the sink any longer. An elevator is the data structure that supports
these operations, each in (amortized) constant time. Two of them are in
lemon/elevator.h, Elevator and LinkedElevator, with the same interface;
Preflow and Circulation take the type of theirs from their traits class
(Elevator by default, another one by the named parameters SetElevator and
SetStandardElevator), and the fractional matchings of chapter 17 use a
LinkedElevator.
Both classes take as template parameters the type GR of the graph and the
type Item of the labelled items (GR::Node, GR::Arc or GR::Edge), and
the labels are the integers from 0 to maxLevel(). Its constructor
Elevator( graph , max_level ) sets the largest label, and
Elevator( graph ) takes it equal to the number of the items of the graph, as
the flow algorithms do. An Elevator stores the items in one array, ordered
by label, with the active items of each level before the inactive ones, and
with two pointers per level, to its first item and to its last active item
(Figure 8.2). Hence, activating, deactivating and lifting by one level are
swaps of two places of the array, and onLevel( l ), emptyLevel( l ),
aboveLevel( l ) and activesOnLevel( l ) are differences of pointers,
computed in \(O(1)\). A LinkedElevator keeps one doubly linked list per level
instead; it needs no array of all the items, but it counts (somewhat slowly)
the items of a level, or above a level, by walking the lists.
The interface of the two classes has four groups of members. First, the
initialization lists the items level by level: initStart() begins it,
initAddItem( i ) puts an item on the current level (level 0 at first),
initNewLevel() passes to the next level, and initFinish() ends it, the
items not listed being put on the top level, all inactive. Afterwards, the
level of an item is read by operator[]( i ) and its state by active( i ),
which activate( i ) and deactivate( i ) change (with the preconditions
that the item is inactive, or active, before the call).
Note that the highest active item, given by highestActive() (or INVALID),
has its level given by highestActiveLevel() (or \(-1\)); it is lifted by one
level by liftHighestActive(), to a given higher level by
liftHighestActive( l ), or to the top level, where it is deactivated, by
liftHighestActiveToTop(). Three similar operations exist for the active item
that activeOn( l ) returns on a given level (INVALID if the level has no
active item, in particular if it is empty), namely liftActiveOn( l ), which
returns the item lifted, liftActiveOn( l , new_level ) and
liftActiveToTop( l ), and lift( i , new_level ) lifts any active item.
Finally, liftToTop( l ) moves all the items on level l and above to the
top level and deactivates them (the gap heuristic), and activeFree( l ) is
true if a level has no active item. Also, dirtyTopButOne( i ) moves an
inactive item from the top level to the level below it without updating the
structure, and the documentation reserves it to those who know what it is for.
The costs of these operations follow from the invariant of the array.
Lemma 8.2. After initFinish() and after each
operation other than dirtyTopButOne(), the array of an Elevator holds the
items in nondecreasing order of level. For each level \(l\), its items occupy
the places from \(\mathit{first}(l)\) to \(\mathit{first}(l+1)-1\), the active
ones before the others, the last active one at \(\mathit{lastActive}(l)\); and
\(\mathit{highest}\) is the highest level with an active item (\(-1\) if none).
Proof. The initialization lists the items level by level and puts the others
on the top level, all inactive. An activation swaps the item with the first
inactive item of its level and increments \(\mathit{lastActive}\), and a
deactivation does the converse. A lift of an active item from level \(l\) to
level \(l'>l\) first moves it to the end of the active part of \(l\). Then, for
each level from \(l\) to \(l'-1\), it moves the last item of that level (after its
active part has been shifted by one place) to the first place of the next one,
shifting the boundary \(\mathit{first}\) of each level crossed by one place to
the left. The item lands in the first place of \(l'\), among the active ones.
liftToTop( l ) relabels all the items from level \(l\) on and moves all the
boundaries of these levels to the first place of \(l\). In each case
\(\mathit{highest}\) is raised to a new active level, or lowered past the levels
left without active items. \(\square\)
Theorem 8.5. In an Elevator, activate(),
deactivate() (apart from the lowering of \(\mathit{highest}\)), the queries
and liftHighestActive() take \(O(1)\) time, a lift from level \(l\) to level
\(l'\) takes \(O(l'-l)\), and liftToTop( l ) takes \(O(k+L)\), where \(k\) is the
number of the items moved and \(L\) the number of levels; the lowering of
\(\mathit{highest}\) costs one step per level passed. In a LinkedElevator, the
activations and the lifts take \(O(1)\) time (apart from the lowering of
\(\mathit{highest}\)), liftToTop( l ) takes \(O(k+L)\) as well, and onLevel(),
aboveLevel() and activesOnLevel() are proportional to the number of the
items they count.
Proof. By Lemma 8.2, each of the first operations swaps two places or reads
two boundaries, and a lift moves one item per level crossed. In a
LinkedElevator, each level is a doubly linked list with the active items at
its front. An activation or a lift relinks one item, and the counts walk the
lists, and liftToTop( l ) walks the list of each level from \(l\) to the one
below the top. \(\square\)
abLEMON
Elevator allocates one place more than the items of the graph, so that
it may be constructed on a graph without items; in LEMON 1.3.1,
Circulation read past its storage on an empty digraph through it.
We remark that the constructor with a given largest label may take a label
smaller than the number of the items, in which case the items not listed by
the initialization stay on the largest level. In a LinkedElevator the items
of the largest level are kept in no list, so that onLevel() and
aboveLevel() count only those below it, as the flow algorithms expect. Also,
liftToTop( l ) of both classes moves all the items from level \(l\) on to the
top level and deactivates them; the gap heuristic calls it on an empty level
\(l\). The two classes define Key (the item) and Value (int), so that they
can be read as maps of the levels.
abLEMON
In LEMON 1.3.1 the constructors with a largest label also took it as the
number of the items, so that Elevator( graph , max_level ) sized its
storage and counted the items correctly only when the two were equal; and
LinkedElevator::lift( i , new_level ) updated the ends of the list of
the new level, where it had to update those of the level that the item
leaves, whenever the item was the first or the last of its list. The test
elevator_test checks both.
abLEMON
In LEMON 1.3.1 liftActiveOn( l ) of both classes was declared to return
an item but returned none, LinkedElevator::activeOn( l ) read the map of
the active items at INVALID on an empty level, and
LinkedElevator::liftToTop( l ) moved only the items of the levels from
\(l+1\) up to the first empty one, leaving them active. The test
elevator_test checks the three, the second with the checks of the
standard library enabled.
8.4 Two-dimensional geometry¶
In lemon/dim2.h, the namespace dim2 holds the plane vectors and boxes that
the drawing function graphToEps() of chapter 21, the planar drawings of
chapter 18 and the generators of geometric instances use. A dim2::Point< T >
is a vector with the public coordinates x and y of type T. It is
constructed from two coordinates (the default constructor value-initializes
them) or converted from a Point of another coordinate type, and it has
size() (always 2), operator[] (0 for x, 1 for y) and normSquare().
Its operators are the sum, the difference and the negation of vectors, the
product by a scalar on either side and the division by a scalar, the scalar
product operator* of two vectors, the comparisons == and !=, and the
forms +=, -=, *= and /=. Free functions makePoint( x , y ),
rot90( p ), rot180( p ) and rot270( p ) (the rotations in the positive
direction) complete it, together with the stream operators, which write
(x,y) and read the same form, with the parentheses and the comma optional.
A dim2::Box< T > is an axis-parallel rectangle, possibly empty. Its default
constructor makes an empty box, while the box of a point, of two corners
(bottom left and top right) or of four sides (left, bottom, right, top) is not
empty. The calls add( p ) and add( box ) enlarge it to contain a point or
another box, operator& intersects two boxes (the result being empty if they
do not overlap), and inside( p ) is true if a point is in the closed box
(never for an empty box); empty() and clear() read and reset the
emptiness. Its corners and sides are read by bottomLeft(), topRight(),
bottomRight(), topLeft(), bottom(), top(), left() and right(), and
set by the members of the same names that take the new value; width() and
height() give the sizes. Values of an empty box are undefined, and the
setters require a box that is not empty; the stream operator >>, which reads
((l,b),(r,t)), gives the box of the two corners, which is not empty (in
LEMON 1.3.1 it set the corners by the setters, and therefore left an empty box
empty; the test dim_test reads one). Finally, the maps XMap and YMap
(read and write) and ConstXMap, ConstYMap and NormSquareMap (read only)
turn a map whose values are points into a map of their coordinates or of their
squared norm, and are made by xMap(), yMap() and normSquareMap().
8.5 Radix sort¶
Both radix sorts of lemon/radix_sort.h sort a range of items by an integer
key, given by a function object or a function functor applied to each item
(the identity if it is omitted). Their time is linear in the number of items
for a fixed size of the keys; hence, they are often worth trying in place of
std::sort when the keys are integers of a few bytes. Its key may be of any
signed or unsigned integer type, and its type is the one that functor
returns.
A call radixSort( first , last , functor ) runs a quicksort whose pivots are
the powers of two. For a signed type, it first separates the items with a
negative key from the others. Then it finds the highest bit \(b\) of the keys of
each part, partitions the part on bit \(b\) by the swaps of the partition of
quicksort, then each half on bit \(b-1\), and so on (Algorithm 8.2). It is not
stable, and it needs bidirectional iterators.
Algorithm 8.2 (Radix sort by bit partitions,
radixSort()).
radixSort(R): R is a range, key(x) an integer
1 split R into R- (key < 0) and R+ (key >= 0) by swaps
2 for each part P in (R-, R+):
3 b := the highest bit in which the keys of P differ from 0 (from 1 in R-)
4 sort(P, b)
sort(P, b):
1 while b >= 0 and P has at least two items:
2 split P into P0 (bit b of the key is 0) and P1 (bit b is 1) by swaps
3 sort(P0, b - 1); P := P1; b := b - 1
Theorem 8.6. radixSort() sorts the range in
nondecreasing order of the keys in \(O(n\,(1+\log_2 c))\) time and with
\(O(1+\log_2 c)\) extra space, where \(n\) is the number of items and \(c\) the
largest absolute value of a key.
Proof. In two's complement, the negative keys precede the nonnegative ones,
and, within each of the two parts, the order of the keys is the order of the
bit strings of their lowest \(b+1\) bits, since all the higher bits are equal
(to 1 in \(R^-\), to 0 in \(R^+\)) by the choice of \(b\) in step 3. The procedure
sort( P , b ) sorts the items of \(P\), whose keys agree on all the bits above
\(b\), by these bit strings: by induction on \(b\), after the split the keys of
\(P_0\) precede those of \(P_1\), and each part is sorted on the lower bits by the
recursive call or by the next round of the loop. Each item takes part in one
split per bit, from \(b\) down, and a split is linear in its range; hence, the
time is \(O(n)\) per bit, and there are at most \(1+\log_2 c\) bits (one more for
the negative keys). The recursion is made only on \(P_0\), with one bit less,
which bounds its depth. \(\square\) A call
stableRadixSort( first , last , functor ) sorts by the bytes of the keys,
from the least significant to the most significant, with one counting pass per
byte. Each pass counts the items of each of the 256 values of the byte,
computes where the items of each value begin, and copies the items in that
order into a second buffer, which keeps the relative order of the items with
the same byte; on a signed type, the last pass puts the negative keys first.
It allocates a buffer of \(2n\) items, into which it copies the range and
between whose two halves the passes alternate.
Theorem 8.7. stableRadixSort() sorts the
range in nondecreasing order of the keys, keeps the relative order of the
items with equal keys, and takes \(O(B\,(n+256))\) time, where \(B\) is the number
of bytes of the type of the key (whatever the largest key).
Proof. A counting pass on byte \(j\) is stable: the items of each value of the byte are copied in the order in which they are read. By induction on \(j\), after the pass on byte \(j\) the items are sorted by their lowest \(j+1\) bytes, read as an unsigned number, with ties in the original order: the pass orders them by byte \(j\), and, being stable, keeps the order of the previous passes among the items with the same byte \(j\). For a signed type, the last pass puts the values 128 to 255 of the top byte, i.e., those of the negative keys in two's complement, before the values 0 to 127, which gives the order of the signed keys. Each pass reads the items twice and the 256 counters once. \(\square\)
We remark that the buffer is a std::vector that holds two constructed copies
of the range, into which the passes copy the items by assignment; hence, the
items need only be copy constructible and copy assignable, as for
std::stable_sort, while radixSort() sorts in place by swaps. Both
functions have overloads for a plain function pointer, and both accept a
lambda. The signed or unsigned version of each is chosen at compile time, from
the type of the key, by the helpers RadixSortSelector and
StableRadixSortSelector of the namespace _radix_sort_bits.
abLEMON
The type of the key is deduced with decltype from the call of functor,
rather than read from its member result_type, which C++20 removed from
the function objects of the standard library; a lambda or any other
callable may therefore be passed, which LEMON 1.3.1 did not accept.
abLEMON
In LEMON 1.3.1 the buffer of stableRadixSort() was raw memory from
std::allocator, into which the items were assigned without being
constructed, so that only the items of a trivially copyable type were
sorted correctly. The test radix_sort_test sorts items that detect an
assignment to storage in which no item was constructed.
abLEMON
In LEMON 1.3.1, radixSort() built the mask of the highest bit as the
int expression 1 << max_digit, which overflowed for the keys of a
64-bit type that use more than 31 bits (and the sort then did not end),
and shifted negative values to the left; the masks are now computed on the
unsigned type of the keys, and the test radix_sort_test sorts keys of 64
bits, the extremes of the type included.
8.6 Random numbers¶
In lemon/random.h, abLEMON implements the Mersenne Twister of Matsumoto and
Nishimura 1998, a generator of
period \(2^{19937}-1\) that is equidistributed in 623 dimensions for 32-bit
numbers. It comes in a 32-bit and a 64-bit version, which give different
sequences from the same seed. A class template _random_bits::Random< Word >
holds the interface, and three types instantiate it: Random32 (the 32-bit
version), Random64 (the 64-bit one) and Random, whose word is
unsigned long, i.e., 64 bits on Linux and macOS and 32 bits on Windows.
Thus, a program that must give the same numbers on all platforms should use
Random32 or Random64. Its global object rnd, of type Random, is the
generator that the library and most programs use; it is constructed with a
fixed seed, and therefore gives the same sequence at each run until it is
seeded again. Other names of the namespace _random_bits are the
implementation: RandomCore holds the state and twists it, and
RealConversion, IntConversion, BoolConversion, Mapping, Masker,
Shifting, ShiftMultiplier, Initializer and BoolProducer turn words
into numbers of a given type.
A generator is seeded by its constructor or by seed(), from one number or
from a range of numbers, each converted to the word of the generator. Without
arguments, seed() takes four words of std::random_device and, if that
fails, calls seedFromTime(), which seeds from the times of
std::chrono::system_clock and of std::chrono::steady_clock; both return
true on success, and seedFromFile() seeds from four words of a file (e.g.,
/dev/urandom). A copy, by construction or by assignment, copies the state,
and the copy then gives the same sequence from that point on. However, the
constructor from a number is a template on the type of the number, which also
matches a generator of the other word size: Random64 r( r32 ) does not copy
r32 but fails to compile, since the state can only be copied between
generators of the same type.
Uniform numbers are given by several members. The call real< T >() returns a
number of type T (double by default) in \([0,1)\), and operator()(),
operator()( b ) and operator()( a , b ) a double in \([0,1)\), \([0,b)\) and
\([a,b)\). The call integer( b ) and its alias operator[]( b ) return an
integer in \(\{0,\dots,b-1\}\), of the type of b, and integer( a , b ) one
in \(\{a,\dots,b-1\}\). Also, integer< T >() and uinteger< T >() return an
integer uniform over the whole range of T, or over its nonnegative part
(int and unsigned int by default), and boolean() returns a fair bit,
taken from a buffer of the bits of one word.
Several other distributions are available (cf. the test
test/random_test.cc). The call boolean( p ) is true with probability
\(p\), and gauss() and gauss( mean , std_dev ) are normal, by the polar form
of the method of Box and Muller 1958
given by Marsaglia and Bray
1964. The call
lognormal( n_mean , n_std_dev ) (or lognormal( pair )) returns the
exponential of a normal variable of the given parameters, and
lognormalMD( mean , std_dev ) a lognormal variable of the given mean and
standard deviation, whose parameters lognormalParamsFromMD() computes. Next
come exponential( lambda ) (of mean \(1/\lambda\), with \(\lambda=1\) by
default), gamma( k ) for an integer shape (a sum of \(k\) exponentials),
gamma( k , theta ) for any positive shape (by rejection),
weibull( k , lambda ), pareto( k , x_min ) and poisson( lambda ); the
last is the method of Knuth
1969. In the plane, disc() is
uniform on the unit disc (by rejection from the square). Next, gauss2()
gives the two normal coordinates of one step of the polar method, and
exponential2() gives the point \((-\ln S/S)\,(V_1,V_2)\) of the same step, a
rotationally symmetric distribution whose distance from the origin is
\(-\ln S/\sqrt S\) with \(S\) uniform on \((0,1)\). The two lemmas below justify
gauss() and poisson(), where \(U_1,U_2,\dots\) are the independent uniform
numbers of \([0,1)\) that real() returns.
Lemma 8.3. Let \(V_1=2U_1-1\) and \(V_2=2U_2-1\) be drawn again until \(S=V_1^2+V_2^2\) is in \((0,1)\), and let \(W=\sqrt{-2\ln S/S}\). Then \(WV_1\) and \(WV_2\) are independent standard normal variables.
Proof. The accepted point \((V_1,V_2)\) is uniform on the punctured unit disc; in polar coordinates \((\sqrt S\cos\Theta,\sqrt S\sin\Theta)\), the angle \(\Theta\) is uniform on \([0,2\pi)\), the area \(\pi S\) of the disc inside the point is uniform, i.e., \(S\) is uniform on \((0,1)\), and the two are independent. The output is \((R\cos\Theta,R\sin\Theta)\) with \(R=\sqrt{-2\ln S}\), and \(P(R>r)=P(S<e^{-r^2/2})=e^{-r^2/2}\). Hence, \(R\) has the density \(re^{-r^2/2}\), and the output has the density \(\frac{1}{2\pi}e^{-(x^2+y^2)/2}\), the product of two standard normal densities. \(\square\)
Thus, the two coordinates of gauss2() are independent, and gauss() returns
the first of them. The case \(S=0\), which has probability \(2^{-2b}\), where \(b\)
is the number of random bits of the double that real() returns, and would
give a NaN, is drawn again by gauss(), gauss2() and exponential2(), as
the lemma requires.
abLEMON
In LEMON 1.3.1 gauss(), gauss2() and exponential2() accepted \(S=0\)
and then returned a NaN; no test checks it, since real() returns 0.5
twice in a row only with probability \(2^{-2b}\).
Lemma 8.4. poisson( lambda ) returns the
least \(k\ge 0\) such that \(U_1\cdots U_{k+1}<e^{-\lambda}\), which is a Poisson
variable of mean \(\lambda\), after \(k+1\) draws; its expected time is therefore
\(O(1+\lambda)\).
Proof. With \(E_i=-\ln U_i\), which are independent exponential variables of mean 1, the condition reads \(E_1+\cdots+E_{k+1}>\lambda\); hence, \(k\) is the number of the points of a Poisson process of unit rate that fall in \([0,\lambda]\), which is a Poisson variable of mean \(\lambda\). The loop draws one number per point and one more. \(\square\)
abLEMON
The packages of abLEMON declare, next to the Boost Software License, the
BSD-3-Clause notice of the Mersenne Twister that the header carries, and
rnd is exported when the library is built as a DLL on Windows.
8.7 Counting and timing¶
In lemon/counter.h, a few classes help to count events in a program under
development, e.g., the operations of an algorithm. A Counter has a title and
an output stream (std::cerr by default); it is changed by ++, --, +=
and -=, read by its conversion to int and reset by reset( c ), and it
prints its title and value when it is destroyed. A Counter::SubCounter,
constructed on a parent counter with a title and a stream, counts in the same
way, prints its value when it is destroyed, and adds it to the parent at that
moment. A Counter::NoSubCounter, instead, prints no report and passes each
change to its parent at once; thus, replacing one with the other turns the
report of a phase on or off without touching the code that counts. Subcounters
can have subcounters, and NoCounter has the interface of Counter but
counts nothing; one can thus compile the counting of a program away by
changing one type.
Time is measured by lemon/time_measure.h. A TimeStamp holds five times,
i.e., the real time, the user and system times of the process and those of its
children; stamp() reads the first of std::chrono::steady_clock and the
second of std::clock(), the processor time of the process (which also counts
the time spent in the system on its behalf), while the other three are zero, as
no standard facility gives them. Its constructor TimeStamp( NULL ) makes a
stamp of the present moment, and the default constructor one of zeros. Stamps
can be added, subtracted and scaled, ellapsed() gives the time passed since
the stamp, and realTime(), userTime(), systemTime(), cUserTime() and
cSystemTime() read the five values. Its stream operator prints
u: ...s , s: ...s , cu: ...s , cs: ...s , real: ...s; after
TimeStamp::format( TimeStamp::SHORT ), a setting global to all stamps, it
prints the real time and its relative difference from the total processor time.
A Timer starts at its construction (unless it is constructed with false),
and is controlled by start(), stop(), halt(), reset() and restart().
It counts the calls of start() and stops only after as many calls of
stop(), which allows one to time a recursive function, while halt() stops
it at once; running() returns the number of calls of stop() still needed.
Its times are read by the same five members as those of a stamp, or by its
conversion to TimeStamp, which printing it uses. A TimeReport is a Timer
that prints a title and its times when it is destroyed (unless
active( false ) has been called), and NoTimeReport is the version that
measures no time. The granularity of the clocks is typically 10 ms (as the
documentation warns), which makes a single measure of a short function rather
unreliable. For a short function,
runningTimeTest( f , min_time , num , full_time ) calls f until the number
of calls reaches a power of two (1, 2, 4, ..., at most \(2^{31}\)) at which the
total real time exceeds min_time seconds (10 by default), and returns the
average time of one call; the number of calls and the total time are written
into the two optional pointers.
8.8 Colors¶
The colours that graphToEps() uses are those of lemon/color.h. A Color
holds three components in \([0,1]\), read and set by red(), green() and
blue(), and set together by set(r, g, b). Fifteen constants are defined in
the library: WHITE, BLACK, RED, GREEN, BLUE, YELLOW, MAGENTA,
CYAN, GREY, DARK_RED, DARK_GREEN, DARK_BLUE, DARK_YELLOW,
DARK_MAGENTA and DARK_CYAN. A Palette is a map from int to Color
that cycles through a list of colours. Its constructor takes have_white
(white first, false by default) and num (the number of colours, \(-1\) by
default), and fills the list with the 26 colours of its default list (27 with
white), cut to num colours or repeated up to them. Then operator[]( i )
and set(i, c) read and write the colour of i modulo size(), and
add( c ) and resize( s ) change the list. Finally, distantColor( c )
returns the corner of the colour cube farthest from c, and distantBW( c )
returns black for a light colour and white for a dark one, by the luminance of
c.
8.9 Errors, assertions and the command line¶
All exceptions of the library derive from Exception (lemon/error.h), a
class derived from std::exception, whose what() returns
"lemon::Exception". An IoError is thrown when a file cannot be read or
written; it carries a message and a file name, set by its constructors or by
message() and file() and read by the members of the same names. A
FormatError is thrown by the readers of chapter 21 when the input is
malformed, and carries a line number too (line(), zero if unknown). The
what() of both composes the message, the file and the line, e.g.,
lemon:FormatError: unknown section (in file 'g.lgf' at line 12). Other
headers derive further exceptions from Exception, e.g., the
ArgParserException described below.
In lemon/assert.h, the macro LEMON_ASSERT( exp , msg ) checks the
preconditions of the library, and the user may use it as well. If exp is
false, it calls a handler with the file, the line, the function, the message
and the text of the expression; the default handler, assert_fail_abort(),
prints them on std::cerr and calls std::abort(). Assertions are enabled by
default, and disabled by LEMON_DISABLE_ASSERTS or by the standard macro
NDEBUG. Moreover, LEMON_ASSERT_ABORT selects the default handler
explicitly, and LEMON_ASSERT_CUSTOM the function named by
LEMON_CUSTOM_ASSERT_HANDLER, which must have the signature of
assert_fail_abort(). Defining both modes, or one of them together with
NDEBUG or LEMON_DISABLE_ASSERTS, is a compilation error, and the mode may
be changed within a translation unit by redefining the macros and including
the header again. Finally, LEMON_DEBUG( exp , msg ) checks the internal
invariants of the algorithms; it works as LEMON_ASSERT, but it is disabled
unless LEMON_ENABLE_DEBUG is defined, since some of its checks are
expensive.
ArgParser (lemon/arg_parser.h) parses the command line of the tools of
chapter 22, and of any program. It is constructed on argc and argv, and
the options are declared without their leading -. Calls of intOption(),
doubleOption(), boolOption() and stringOption() declare an option with a
help string, a default value and a flag that makes it mandatory, and
refOption() declares one whose value is written directly into a variable of
the program. In the same way, other( name , help ) documents the arguments
that are not options, synonym( syn , opt ) adds another name of an option,
and optionGroup( group , opt ) puts options into a group, for which
onlyOneGroup( group ) and mandatoryGroup( group ) require at most one, or
at least one, of its options. All these calls return the parser, and can
therefore be chained.
Then parse(), or its synonym run(), reads the arguments. An argument that
starts with - (and is not - alone) must be a declared option; a bool
option is set to true by its presence, and any other option takes the next
argument as its value, which must be read in full as a number for a numeric
option. Other arguments are collected in files(). Afterwards,
given( name ) is true if an option appeared, and operator[]( name )
returns its value through the proxy RefType, which converts to int,
double, bool or std::string after checking the type of the option with
LEMON_ASSERT (an integer option also converts to double); commandName()
returns argv[0]. Options -help, --help and -h print a summary of the
options. On a request of help, an unknown option, a missing or malformed
value, or a violated condition on the mandatory options and groups, the parser
prints a message and calls exit( 1 ). If throwOnProblems() has been
called, it throws instead an ArgParserException, whose reason() is HELP,
UNKNOWN_OPT or INVALID_OPT. Its records GroupData and OtherArg of the
header hold the groups and the help of the other arguments.
The program manual/examples/08-utilities.cc (the test
manual_08_utilities) uses an elevator, the two radix sorts, two generators
seeded alike and a box, a counter that writes into a string, a timer, and a
parser of a command line given as an array, and checks the result of each.
8.10 Exercises¶
Exercise 8.1. Show that, if an erasure from an
empty end of a Path moved all the arcs of the other vector instead of half
of them, a sequence of \(q\) calls made of \(q/2\) calls of addBack() followed
by alternate calls of eraseFront() and eraseBack() would take
\(\Theta(q^2)\) time, and explain which step of the proof of Theorem 8.1 fails.
(The test test/path_test.cc checks the four path classes.)
Exercise 8.2. Write a function that reverses a
path of a digraph into a path of the adaptor ReverseDigraph of chapter 5,
using ListPath::spliceFront(), and check the result with checkPath();
compare it with a copy by pathCopy() and the iterator ArcIt.
Exercise 8.3. Compute the connected components of
a graph with UnionFindEnum, print the items of each class with ClassIt and
ItemIt, and compare the classes with those of connectedComponents() of
chapter 18. (The example examples/08-union-find.cc and the test
test/unionfind_test.cc use the same calls.)
Exercise 8.4. Measure with runningTimeTest()
the time of radixSort(), stableRadixSort() and std::sort on \(10^6\)
random keys drawn by rnd.integer< int >(), and then on keys drawn in
\(\{0,\dots,255\}\); explain the two rankings by the costs of §8.5.
(The test test/radix_sort_test.cc checks the two sorts.)
Exercise 8.5. Draw \(10^5\) numbers by
gamma( 2.5 , 2.0 ) and by pareto( 3.0 , 1.0 ), and compare their sample
means with the means \(k\theta\) and \(k x_{\min}/(k-1)\) of the two
distributions. (The test test/random_test.cc checks the generator.)
Exercise 8.6. Use a Counter with two
subcounters to count the comparisons and the swaps of an insertion sort, and
verify that the parent includes the counts of a SubCounter only after it is
destroyed, and those of a NoSubCounter at once. (The test
test/counter_test.cc exercises the counters.)