11. Spanning trees and arborescences¶
We are concerned in this chapter with two problems of choosing a cheapest set
of arcs that connects the nodes of a graph. The first one is the minimum
spanning tree of an undirected graph, which kruskal() of lemon/kruskal.h
solves by Kruskal's algorithm on a union-find structure
(§8.2). Its directed counterpart, the second one,
is the minimum cost arborescence of a digraph rooted at a given node;
MinCostArborescence of lemon/min_cost_arborescence.h solves it by the
algorithm of Chu, Liu and Edmonds, and also gives an optimal dual solution,
which proves the optimality of the arborescence. The two problems look alike;
however, the greedy choice that solves the first is not enough for the second,
whose algorithm has to contract cycles (cf. Figure 11.2).
11.1 Minimum spanning trees¶
Let \(G=(N,E)\) be an undirected graph with \(n=|N|\) nodes, \(m=|E|\) edges and costs \(c : E\to\mathbb{R}\) on the edges, and let \(N_1,\dots,N_p\) be the node sets of its connected components. A spanning forest of \(G\) is a set \(T\subseteq E\) of edges that contains no cycle and connects the nodes of each \(N_i\); it has \(n-p\) edges, and it is a spanning tree when \(G\) is connected (\(p=1\)). We consider the problem
which, on a connected graph, is the minimum spanning tree problem, and on any other graph is that of a minimum spanning tree of each component. For a spanning forest \(T\) and an edge \(f\notin T\), the two ends of \(f\) lie in the same component, and we let \(P_T(f)\) be the (unique) path of \(T\) between them; a loop \(f\) has \(P_T(f)=\emptyset\). For an edge \(e\in T\), the forest \(T\setminus\{e\}\) splits the component of \(e\) into two node sets, and we let \(C_T(e)\) be the set of the edges of \(G\) with one end in each of them (the fundamental cut of \(e\)). The two objects describe the same pairs of edges.
Lemma 11.1. Let \(T\) be a spanning forest, \(e\in T\) and \(f\in E\setminus T\). Then \(e\in P_T(f)\) if and only if \(f\in C_T(e)\), and, in this case, \(T'=(T\setminus\{e\})\cup\{f\}\) is a spanning forest with \(c(T')=c(T)-c(e)+c(f)\).
Proof. Let \(U\) and \(W\) be the two node sets into which \(T\setminus\{e\}\) splits the component of \(e\). If \(f\) has one end in \(U\) and one in \(W\), the path of \(T\) between its ends must cross from \(U\) to \(W\), which only \(e\) does; hence, \(e\in P_T(f)\). Conversely, if \(e\in P_T(f)\), removing \(e\) cuts this path into a part in \(U\) and a part in \(W\), and the two ends of \(f\) are therefore on opposite sides. In this case, \(T\setminus\{e\}\) has one component more than \(T\), and \(f\) joins two of its components (\(U\) and \(W\)); hence, \(T'\) has no cycle and the same components as \(T\), i.e., it is a spanning forest, and its cost is obvious. \(\square\)
Theorem 11.1. A spanning forest \(T\) is optimal for (11.1) if and only if
or, equivalently, if and only if
Proof. By Lemma 11.1, (11.2) and (11.3) are the same set of inequalities, written once by the edges out of the forest and once by the edges in it. If (11.2) fails for some \(f\) and \(e\in P_T(f)\), the forest \(T'\) of Lemma 11.1 costs \(c(T)-c(e)+c(f)<c(T)\), and \(T\) is not optimal. Conversely, let \(T\) satisfy (11.3), and among the optimal forests let \(T^*\) be one with the largest \(|T\cap T^*|\). If \(T\neq T^*\), since both have \(n-p\) edges, there is an edge \(e\in T\setminus T^*\). Its ends are joined by the path \(P_{T^*}(e)\), which, together with \(e\), is a cycle; this cycle crosses the cut \(C_T(e)\) once through \(e\), and must therefore cross it at least once more, through an edge \(f\neq e\) of \(P_{T^*}(e)\). The only edge of \(T\) in \(C_T(e)\) is \(e\); hence, \(f\notin T\), and \(c(e)\le c(f)\) by (11.3). By Lemma 11.1 applied to \(T^*\) and the pair \(f\in T^*\), \(e\notin T^*\) (indeed \(f\in P_{T^*}(e)\)), the forest \((T^*\setminus\{f\})\cup\{e\}\) costs at most \(c(T^*)\), and is therefore optimal, and it has one more edge in common with \(T\) than \(T^*\), a contradiction. Thus, \(T=T^*\) is optimal. \(\square\)
Kruskal's algorithm (Kruskal
1956) builds a forest that
satisfies (11.2) greedily. It scans the edges in nondecreasing order of cost,
and keeps an edge if it joins two different components of the forest of the
edges kept so far, i.e., if it closes no cycle. The components are the classes
of a union-find structure on the nodes, and the test and the union are one
call of join() (Algorithm 11.1, where \(\mathit{out}\) is the output of the
function and \(\mathit{total}\) its value).
Algorithm 11.1 (Kruskal's algorithm,
kruskal()).
1 if the costs are given as a map: list the pairs (e, c(e)) of all the edges
and sort them by nondecreasing c(e)
2 make a union-find structure with one class {v} per node v; total := 0
3 for each pair (e, c(e)) in the order of the list, with e = uv:
4 if join(u, v): [u and v were in different classes]
5 out(e) := true; total := total + c(e)
6 else: out(e) := false
7 return total
Theorem 11.2. If the list scanned by Algorithm 11.1 holds every edge of \(G\) in nondecreasing order of cost, the edges \(T\) with \(\mathit{out}(e)=\mathit{true}\) form an optimal solution of (11.1), and the value returned is \(c(T)\). For a list in any other order (or holding only some of the edges), \(T\) is a spanning forest of the graph of the edges of the list, i.e., one with no cycle and whose components are those of that graph.
Proof. At each step, the classes of the union-find structure are the node
sets of the components of the forest \((N,T)\) kept so far: this is true at the
start, and join() (Algorithm 8.1) unites the classes of \(u\) and \(v\) exactly
when the edge \(uv\) is kept. An edge is kept only if its ends are in different
components, and therefore closes no cycle; an edge is discarded only if its
ends are already in the same component, which they remain. Hence, at the end,
\(T\) has no cycle and connects the ends of each edge of the list, i.e., it is a
spanning forest of the graph of the list. If the list is sorted and complete,
let \(f\) be a discarded edge. When it was scanned, its ends were joined by a
path of edges kept before it, which is \(P_T(f)\) (a forest has one path between
two nodes) and whose edges cost at most \(c(f)\), since they come earlier in the
list. Thus, (11.2) holds, and \(T\) is optimal by Theorem 11.1. The value is the
sum of the costs of the kept edges, by step 5. \(\square\)
Theorem 11.3. Algorithm 11.1 takes \(O(m\log m)\) time when the costs are given as a map, and \(O(n+m\,\alpha(m,n))\) time when they are given as a sorted list of \(m\) pairs.
Proof. Listing the pairs takes \(O(m)\) and std::sort takes \(O(m\log m)\).
The rest makes \(n\) insertions and \(m\) calls of join(), each made of two
finds and at most one union, which take \(O(n+m\,\alpha(m,n))\) in all by
Theorem 8.2. Since \(\alpha(m,n)\le\log m\) for \(m\ge 2\), the sort dominates in
the first case. \(\square\)
Note that the loop scans all the edges of the list even after the forest is
complete, since the output receives a value for each of them; however, the
work after the last useful edge is only one join() per edge. Of course, when
the costs come already sorted (e.g., from a previous run), passing them as a
list saves the sort, which is usually the dominating cost.
Interface. Function kruskal( g , in , out ) accepts various types for
its arguments, and returns the cost of the forest found, of the type of the
costs. Its graph g may be undirected, with the costs on its edges, or
directed, in which case the arcs are taken as edges (the union-find structure
joins the target and the source of each arc) and their direction is
disregarded. Its costs in may be given either (i) as a readable map on the
edges (or arcs), whose values are the costs, or (ii) as an STL container of
pairs std::pair< GR::Edge , C > (or std::pair< GR::Arc , C >), where C
is the type of the costs. In case (i), the function collects the pairs of each
item and its cost into a vector, and sorts it by cost with std::sort. In
case (ii), the pairs must already be sorted by nondecreasing cost, since no
sort is done (Theorem 11.2 gives what is computed otherwise), and an edge that
is not in the container receives no value in out.
Its output out may also be given in two ways. It may be (i) a writable map
on the edges with bool values, which receives true for the edges of the
forest and false for the others, each edge of the list being written once.
Alternatively, it may be (ii) an output iterator, e.g.,
std::back_inserter( tree ), into which the edges of the forest are copied in
the order in which they are found; the function wraps it in a LoggerBoolMap
(cf. chapter 6), which copies the keys set to true and
ignores the others. A second overload takes out by constant reference, so
that a temporary iterator may be passed. The choice among the forms is made at
compile time by the helper templates of the namespace _kruskal_bits, which
are not part of the interface: KruskalValueSelector, KruskalInputSelector,
KruskalOutputSelector, SequenceInputIndicator, MapInputIndicator,
SequenceOutputIndicator, MapOutputIndicator, RemoveConst and PairComp.
They take an input for a sequence if its value_type has a first_type, and
for a map if it has a type Value; an output is taken for a sequence (an
iterator) if it has a value_type, and for a map if it has a Value.
Figure 11.1 shows the tree that the program of this section computes. Its edges, sorted by cost, are kept in the order 1, 2, 3, 5, 6, while the edges of cost 4, 7, 8 and 9 close cycles. Each of the latter costs at least as much as every edge of the path of the tree between its ends, as (11.2) requires.
The program manual/examples/11-kruskal.cc (the test manual_11_kruskal)
computes the tree of Figure 11.1 twice, with a cost map in and a bool map
out, and then with a sorted vector of pairs in and an output iterator out. It
checks the cost, the number of edges and the condition (11.2), the latter by a
breadth-first search of the path of the tree between the ends of each edge out
of the tree, on the graph of the adaptor FilterEdges (chapter
5).
11.2 Minimum cost arborescences¶
Let \(G=(N,A)\) be a digraph with costs \(c : A\to\mathbb{R}\), and let \(S\subseteq N\) be a nonempty set of sources (one root \(r\) in the simplest case), and \(R\supseteq S\) the set of the nodes reachable from \(S\). For \(X\subseteq N\), we write \(\delta^-(X)\) for the set of the arcs with their head in \(X\) and their tail out of \(X\) (so that a loop enters no set), and \(\delta^-(v)\) for \(\delta^-(\{v\})\). An arborescence of \(R\) rooted at \(S\) is a set \(B\) of arcs with both ends in \(R\) such that
and each node of \(R\) is reachable from \(S\) along the arcs of \(B\). With one source \(r\), it is a spanning tree of \(R\) whose arcs are directed away from \(r\), and with several it is a union of such trees, one per source, that reaches all of \(R\). We look for one of least cost \(c(B)=\sum_{a\in B}c(a)\). Choosing the cheapest arc entering each node, which would mirror the greedy algorithm of the undirected case, may give cycles: in Figure 11.2, the cheapest arcs entering \(a\) and \(b\) form the cycle \(a,b,a\). The optimality of an arborescence is proved instead by a family \(\mathcal F\) of subsets of \(R\setminus S\) with a value \(y_X\) on each set \(X\in\mathcal F\) (a solution of the dual of the linear program of the problem, Edmonds 1967), through the reduced costs
Lemma 11.2. Let \(\mathcal F\) be a family of nonempty subsets of \(R\setminus S\) and \(y:\mathcal F\to\mathbb R\) be such that \(y_X\ge 0\) for each \(X\in\mathcal F\) with \(|X|\ge 2\), and \(c'(a)\ge 0\) for each arc \(a\) with its tail in \(R\) and its head in \(R\setminus S\). Then each arborescence \(B'\) of \(R\) rooted at \(S\) has \(c(B')\ge\sum_{X\in\mathcal F}y_X\), and an arborescence \(B\) attains this bound, and is therefore optimal, if \(c'(a)=0\) for each \(a\in B\) and \(|B\cap\delta^-(X)|=1\) for each \(X\in\mathcal F\).
Proof. Summing (11.5) over the arcs of \(B'\), and exchanging the two sums, gives
The first sum is nonnegative, since each arc of \(B'\) has its tail in \(R\) and, by (11.4), its head in \(R\setminus S\). For a singleton \(X=\{v\}\), one has \(|B'\cap\delta^-(X)|=1\) by (11.4), whatever the sign of \(y_X\). Let \(X\) have \(|X|\ge 2\): its nodes are reachable from \(S\) along \(B'\), and \(X\cap S=\emptyset\). Hence, the first node of \(X\) on such a path is entered by an arc of \(B'\) from out of \(X\), i.e., \(|B'\cap\delta^-(X)|\ge 1\), and \(y_X|B'\cap\delta^-(X)|\ge y_X\) since \(y_X\ge 0\). Thus, \(c(B')\ge\sum_X y_X\), and under the two conditions of the statement both inequalities hold with equality for \(B\). \(\square\)
The algorithm of Chu and Liu 1965 and Edmonds 1967 builds such a pair \((B,y)\) by contraction (Algorithm 11.2). Each node, and later each contracted set \(X\), chooses the arc of least reduced cost that enters it; that reduced cost becomes the dual variable \(y_X\), and it is therefore subtracted, by (11.5), from the reduced costs of all the arcs entering \(X\), the chosen one falling to zero. A cycle of chosen arcs is contracted into a new set, which chooses in its turn, until a chosen arc comes from a node that is already connected to a source. Then the contractions are expanded, the arc that enters a contracted set from outside replacing the chosen arc of the node it enters, while the other chosen arcs of the set stay.
The implementation grows these choices along a path of sets, kept as a stack of levels. Each node is, at any moment, unreached, reached (i.e., in \(R\) and waiting to be processed), on the path, or processed. A level is a set \(X\) of nodes on the path, created with its dual variable \(y_X\) (the \(k\)-th variable created having index \(k\)). It is stored together with one arc \(e_X(w)\) for each reached or processed node \(w\notin X\) with arcs into \(X\), the one of least reduced cost among them, and its reduced cost. The chosen arc \(a_X\) of \(X\) is the arc of least reduced cost among the \(e_X(w)\), and \(\mathit{ord}(a)\) is the index of the set of which \(a\) is the chosen arc (\(-1\) for an arc chosen by none). In Algorithm 11.2, \(Q\) is the list of the reached nodes, in the order in which they were reached, and \(H\) is a heap of nodes.
Algorithm 11.2 (Minimum cost arborescence by
contractions, MinCostArborescence).
init(): every node unreached, pred(v) := INVALID; no set, no dual variable;
ord(a) := -1 and arborescence(a) := false for each arc a
addSource(s): by a depth-first search from s, mark reached each unreached node
that can be reached, and append it to Q; then mark s processed
processNextNode():
1 v := the last node of Q; remove it from Q
2 if v is reached:
3 a := prepare(v)
4 while source(a) is not processed:
5 u := source(a)
6 if u is on the path: a := contract(u)
7 else: a := prepare(u)
8 finalize(a); empty the stack of the levels
9 return v
prepare(u): [a new level X = {u}, at the top of the stack]
1 put u on the path
2 for each node w != u, reached, on the path or processed, with arcs into u:
e_X(w) := an arc wu of least cost; its reduced cost := c(e_X(w))
3 a_X := the e_X(w) of least reduced cost; y_X := its reduced cost
4 subtract y_X from the reduced cost of each e_X(w); ord(a_X) := index of y_X
5 push the level X; return a_X
contract(u): [the cycle closed by the chosen arc of the top level]
1 L := the level that contains u
2 pop L and all the levels above it; X := the union of their nodes
3 for each node w not in X with an arc stored in the popped levels:
e_X(w) := the stored arc from w of least reduced cost
4 a_X := the e_X(w) of least reduced cost; y_X := its reduced cost
5 subtract y_X from the reduced cost of each e_X(w); ord(a_X) := index of y_X
6 push the level X; return a_X
finalize(a): [expansion of the levels of the path]
1 t := target(a); pred(t) := a; insert t in H with key ord(a)
2 while H is not empty:
3 w := a node of least key in H; remove it from H; mark w processed
4 for each arc e = wz with ord(e) >= 0:
5 if z has never been in H: pred(z) := e; insert z in H with key ord(e)
6 else if z is in H and ord(e) < key(z): pred(z) := e; key(z) := ord(e)
7 arborescence(pred(w)) := true
start(): while Q is not empty: processNextNode()
run(s): init(); addSource(s); start()
The steps are the private members prepare(), contract() and finalize()
of the class. The levels are its records StackLevel (with the arcs \(e_X(w)\)
as records CostArc of an arc and its reduced cost), and the dual variables
are its records DualVariable. The nodes on the path are stored in the order
in which they were put there, so that the nodes of a level, and of each dual
variable, are a range of that order (whose first element locates the level of
a node in step 1 of contract()). Note that step 2 of prepare() keeps the
cheapest of several parallel arcs from \(w\), and skips the loops and the arcs
from unreached nodes. The theory needs three facts on a call of
processNextNode(); in Lemma 11.3, the reduced costs are those of (11.5) for
the family \(\mathcal F\) of all the sets created so far.
Lemma 11.3. Suppose that all the calls of
addSource() precede the first call of processNextNode(). Then the
following hold at each point of the execution. (i) The sets of \(\mathcal F\)
form a laminar family (any two are disjoint or nested), and the levels on the
stack are disjoint. (ii) For each level \(X\) on the stack and each node \(w\)
with an arc stored in it, the stored reduced cost of \(e_X(w)\) is its reduced
cost (11.5), which is the least reduced cost of the arcs from \(w\) into \(X\).
(iii) Every arc with its tail in \(R\) and its head in \(R\setminus S\) has
\(c'(a)\ge 0\), and \(y_X\ge 0\) for each \(X\in\mathcal F\) with \(|X|\ge 2\). (iv)
For each \(X\in\mathcal F\), the chosen arcs of the sets of \(\mathcal F\)
strictly contained in \(X\) have both ends in \(X\), have indices smaller than
that of \(X\), and connect the nodes of \(X\) strongly; the chosen arc \(a_X\) has
\(c'(a_X)=0\), and enters no set of \(\mathcal F\) other than \(X\) and the sets
contained in \(X\).
Proof. We argue by induction on the steps, all statements holding trivially
before the first set is created. A new set is either a singleton \(\{u\}\) of a
node \(u\) that was only reached, and therefore in no set (prepare()), or the
union of the levels from \(L\) to the top (contract()). In both cases it is
disjoint from the levels left on the stack and from the sets of the previous
calls (whose nodes are processed), and contains the sets of the levels it
replaces, which gives (i). For (ii), consider a level \(X\) and an arc \(e\) from
\(w\notin X\) into \(X\). After \(X\) is created, the reduced cost of \(e\) changes
only when a set is created that contains the head of \(e\) and not \(w\); by (i),
such a set contains \(X\), and its creation pops \(X\). Hence, the reduced costs
stored at the creation of \(X\) (by step 4 of prepare(), or by step 5 of
contract()) stay exact while \(X\) is on the stack. That they are computed
right at the creation follows from (ii) for the popped levels. Indeed, an arc
entering the union \(X\) of step 2 of contract() from \(w\notin X\) enters only
one of the popped levels, in which an arc from \(w\) of least reduced cost is
stored; in prepare(), no set contains \(u\) before, and the reduced costs are
the costs.
For (iii), the creation of \(X\) subtracts \(y_X\), the least reduced cost of the
arcs from the nodes of \(R\) out of \(X\) into \(X\), from each of them. Hence, they
stay nonnegative, and no other reduced cost changes. The arcs from the nodes
that are not yet reached are excluded, but no node is reached after the first
call of processNextNode(); hence, all the arcs from \(R\) are considered.
Since the stored reduced costs are nonnegative after their level is created,
the value \(y_X\) of a contracted set, which is one of them, is nonnegative.
For (iv), consider the stack \(L_0,\dots,L_t\) of the levels, from the bottom.
The chosen arc of \(L_i\), for \(i<t\), comes from a node of \(L_{i+1}\): indeed,
\(L_{i+1}\) was pushed by prepare() on the tail of that arc, and the later
contractions only enlarge \(L_{i+1}\) (or pop \(L_i\) too). Thus, when
contract( u ) merges the levels \(L_j,\dots,L_t\), with \(u\in L_j\), the chosen
arcs of \(L_j,\dots,L_{t-1}\) go from each level to the one below it, and that
of \(L_t\) goes from \(L_j\) to \(L_t\). They form a cycle through the levels, all
inside \(X\), created before \(X\). Together with the induction hypothesis for the
levels, this shows that the chosen arcs of the sets strictly contained in \(X\)
are inside \(X\), have smaller indices, and connect \(X\) strongly. Finally, when
\(a_X\) is chosen, its reduced cost becomes zero. Afterwards, by (i), a new set
that contains the head of \(a_X\) contains \(X\), and is created by a contraction
that merges \(X\) with other levels, of which \(a_X\) is then an inside arc by
what precedes. Hence, no later set is entered by \(a_X\), and \(c'(a_X)\) stays
zero. \(\square\)
Lemma 11.4. When finalize( a ) is called at
step 8 of processNextNode(), it marks processed all the nodes on the path,
and gives each of them an arc pred whose tail was processed before it. These
arcs are such that exactly one of these arcs enters each set created in the
same call of processNextNode(); all these arcs are chosen arcs.
Proof. The arcs that finalize() follows have \(\mathit{ord}\ge 0\), i.e.,
they are chosen arcs, whose heads are on the path (those of the previous calls
having been removed from \(H\) for good, and the sources never entering it).
With the notation of the proof of Lemma 11.3, \(a\) is the chosen arc of the top
level \(L_t\), from a processed node. From its head, the chosen arcs inside
\(L_t\) reach all of \(L_t\) (Lemma 11.3 (iv)), that of \(L_{t-1}\) leads into
\(L_{t-1}\), and so on. Hence, all the nodes on the path enter \(H\) and are
processed, each one with an arc pred whose tail is processed, and it remains
to count the arcs entering a set \(X\) created in the call. An arc chosen for a
set strictly contained in \(X\) has both ends in \(X\) (Lemma 11.3 (iv)). Hence,
an arc with \(\mathit{ord}\ge 0\) that enters \(X\) from out of \(X\) is the chosen
arc of \(X\) or of a set containing \(X\), created after \(X\), and has an index at
least that of \(X\). Let \(x\) be the first node of \(X\) removed from \(H\): its arc
pred comes from out of \(X\), since no node of \(X\) was processed before. Let
\(z\) be another node of \(X\), and consider the moment at which \(z\) is removed
from \(H\). Since \(x\) is processed and the chosen arcs inside \(X\) connect \(X\)
strongly, there is such an arc from a processed node of \(X\) to a node \(z'\) of
\(X\) not yet processed, and therefore in \(H\), with a key smaller than the index
of \(X\) (Lemma 11.3 (iv)). Since \(z\) has the least key in \(H\), its key is also
smaller than the index of \(X\). Hence, the final pred of \(z\), whose
\(\mathit{ord}\) is that key, is not an arc entering \(X\) from outside, and
exactly one arc pred enters \(X\). \(\square\)
Theorem 11.4. After init(), the calls
addSource( s ) for the sources \(s\in S\) and start(), the arcs pred( v )
for \(v\in R\setminus S\) form a minimum cost arborescence \(B\) of \(R\) rooted at
\(S\). The arborescence map is true on the arcs of \(B\) only, and the dual
variables satisfy the conditions of Lemma 11.2 with \(B\); hence, dualValue()
\(=\sum_X y_X=c(B)=\) arborescenceCost().
Proof. Each node of \(R\setminus S\) is appended to \(Q\) when it is reached,
and is processed either when it is taken from \(Q\) or, before, by finalize()
in the call of another node (Lemma 11.4). A source is processed by
addSource() and receives no arc, and no node out of \(R\) is touched. Each
node \(v\in R\setminus S\) gets its arc pred( v ) when it is processed, from a
node processed before, and keeps it. Hence, \(B\) satisfies (11.4), and the
order of processing shows that it has no cycle and that each node of \(R\) is
reachable from \(S\) along \(B\), i.e., \(B\) is an arborescence of \(R\) rooted at
\(S\). Each set of \(\mathcal F\) is entered by exactly one arc of \(B\): by Lemma
11.4, by one arc pred given in its own call, and by no arc given in a later
call, whose heads are disjoint from it. The arcs of \(B\) are chosen arcs, which
have \(c'=0\) by Lemma 11.3 (iv), and Lemma 11.3 (iii) gives the remaining
conditions of Lemma 11.2, which proves the optimality of \(B\) and the equality
of the values. The map is set at step 7 of finalize(), once on each arc of
\(B\) when its head is processed. \(\square\)
The hypothesis that the sources are all given before the first node is processed is needed by Lemma 11.3 (iii): a node reached later may have arcs into sets created before it was reached, whose reduced costs were never reduced (and may be negative). Note also that the costs may have any sign: only the dual variables of the singletons may be negative, and Lemma 11.2 does not need them nonnegative, since each singleton of \(R\setminus S\) is entered by one arc of every arborescence.
Theorem 11.5. init() takes \(O(n+m)\) time,
all the calls of addSource() take \(O(n+m)\) in all, and start() takes
\(O(n^2+m)\) time, with the binary heap of the default traits or with any heap
whose operations take \(O(n)\) time.
Proof. The first two bounds are clear: the search of addSource() marks
each node at most once, and scans the arcs out of a node only when it marks it
(or when it is a source). Each call of prepare() puts a new node on the
path, and therefore happens at most once per node of \(R\); it takes
\(O(|\delta^-(u)|+n)\) time, the second term for the at most \(n\) arcs stored.
Each call of contract() pops at least two levels (the source of the chosen
arc of the top level is out of it) and pushes one. Hence, in a call of
processNextNode() that puts \(k\) nodes on the path, at most \(k-1\)
contractions are made and at most \(2k-1\) levels are created, each holding at
most \(n\) arcs and popped at most once; locating the level of \(u\) costs \(O(k)\).
Summing over all the calls, the levels cost \(O(n^2)\) and the arcs entering the
nodes \(O(m)\). Finally, finalize() inserts each node of the path once in \(H\)
and removes it once, and scans the arcs out of it once; the decreases are at
most as many as the chosen arcs, i.e., the dual variables, at most \(2n\) in
all. Hence, all the calls of finalize() take \(O(n\log n+m)\) time with a
binary heap, and \(O(n^2+m)\) with any heap of \(O(n)\) operations. \(\square\)
Faster implementations, in \(O(m+n\log n)\), exist (Gabow et al. 1986), but the library does not use them. Note that the dual solution makes the result somewhat easier to check: the conditions of Lemma 11.2 can be verified arc by arc, and the sum of the \(y_X\) must equal the cost of the arborescence.
Interface. MinCostArborescence< GR , CM , TR > takes the digraph type
GR, the type CM of the cost map (by default GR::ArcMap< int >), and the
traits class TR, by default MinCostArborescenceDefaultTraits< GR , CM >.
The cost map is read once for each arc at each node that the arc enters (in
step 2 of prepare()), and once more by arborescenceCost(). The traits give
the types Digraph, CostMap, Value (the type of the costs),
ArborescenceMap and PredMap, with the functions createArborescenceMap()
and createPredMap() that allocate the two maps. The ArborescenceMap (by
default an ArcMap< bool >) receives false on each arc at init(), and
then true once on each arc of the arborescence; the PredMap is a
NodeMap< Arc >. They also give HeapCrossRef and Heap, i.e., a
NodeMap< int > and a BinHeap on integer keys, which finalize() uses for
\(H\). The named parameters SetArborescenceMap< T > and SetPredMap< T > set
the types of the two maps, which must then be given by arborescenceMap( m )
and predMap( m ) (their create functions assert). Similarly,
SetHeap< H , CR > sets the type of the heap and of its cross reference map
(by default a NodeMap< int >), which the algorithm constructs on the digraph
with \(-1\) as the value of each node. The class also defines Create, the type
itself, which the named parameters produce.
abLEMON
MinCostArborescence takes the type of its heap from its traits class,
with the named parameter SetHeap; LEMON 1.3.1 used a BinHeap that
could not be changed.
Its constructor takes the digraph and the cost map, and the setters
arborescenceMap( m ) and predMap( m ) return the object; the maps not
given are allocated by init() and deleted by the destructor. Its execution
control is made of init(), addSource( s ), processNextNode() (which
returns the node taken from \(Q\), and must not be called on an empty \(Q\)),
queueSize(), emptyQueue(), start() and run( s ), which is init(),
addSource( s ) and start(). A call addSource( s ) marks the nodes
reachable from s, and may be repeated for several sources, before start()
as Theorem 11.4 requires. Despite the word "queue" of the documentation, \(Q\)
is a stack: the nodes are taken in the reverse of the order in which they were
reached.
Its queries on the arborescence are arborescence( a ), which is true if the
arc \(a\) is the arc pred of its target, arborescenceMap(), pred( v )
(INVALID for a source and for an unreached node), predMap(), and
arborescenceCost(), computed in \(O(m)\) from the arcs pred. Also,
reached( v ) is true if \(v\) is reachable from a source, and processed( v )
if it has been processed. Its queries on the dual solution are dualNum(),
the number of the dual variables (some of which may have value zero), and
dualValue( k ) and dualSize( k ), the value and the number of nodes of the
\(k\)-th one; dualValue() is the sum of all of them, in \(O(n)\). An iterator
DualIt( mca , k ) lists the nodes of the \(k\)-th set, converts to Node, and
is compared with INVALID to stop. Finally, the function
minCostArborescence( g , cost , source , arborescence ) runs the algorithm
from one source, writes the arborescence into the given bool arc map, and
returns its cost.
The program manual/examples/11-arborescence.cc (the test
manual_11_arborescence) solves the instance of Figure 11.2, reads the dual
solution through DualIt, checks the conditions of Lemma 11.2 arc by arc and
the equality of the primal and dual values, and calls the function-type
interface.
11.3 Exercises¶
Exercise 11.1. Prove that Kruskal's algorithm is
also correct when the costs are scanned in nonincreasing order and an edge is
discarded, instead of kept, if the edges not yet discarded still connect its
ends (the reverse-delete algorithm), and check (11.3) on random graphs by the
method of the program manual/examples/11-kruskal.cc. (The test
test/kruskal_test.cc runs kruskal() with each form of input and output.)
Exercise 11.2. Compute a maximum spanning tree
with kruskal(), through a map that negates the costs (e.g., negMap() of
chapter 6), and explain by Theorem 11.1 why the greedy algorithm remains
correct.
Exercise 11.3. Run kruskal() on a digraph and
on the graph of the adaptor Undirector of the same digraph, and verify that
the two trees have the same cost.
Exercise 11.4. Give a digraph on which choosing
the cheapest arc entering each node, and then breaking each cycle at its most
expensive arc, does not give a minimum cost arborescence, and check the answer
of MinCostArborescence on it. (The test test/min_cost_arborescence_test.cc
checks the dual solution as the program manual/examples/11-arborescence.cc
does.)
Exercise 11.5. Use two sources with
addSource() and verify that the result is the cheapest union of two
arborescences rooted at them. Compare it with a single run from a new root
joined to the two sources by arcs of cost zero, and explain the equality of
the two costs by Lemma 11.2.