Vocking B., Alt H., Dietzfelbinger M., Reischuk R., Scheideler C., Vollmer H., Wagner D. Algorithms Unplugged

Подождите немного. Документ загружается.

340 Robert G¨orke, Steﬀen Mecke, and Dorothea Wagner

The algorithm Maximum Flow ﬁnds a maximum ﬂow from the start S to

the target Z, by repeatedly calling the procedures Raise and Push.

1 procedure Maximum Flow (G, S, Z)

2 begin

3RaiseS to height n (n is the number of junctions).

4 For each street leaving S, push as many cars as possible away from S.

5 Leave all other junctions (except S)atheight0.

6 while there is a junction C with excess ﬂow do

7 if pushing from C possible

8 Apply procedure Push (at junction C).

9 else

10 Apply procedure Raise (at junction C).

11 endwhile

12 end

In order to describe a complete run of our algorithm, we ﬁrst have to give

names to the junctions:

The following pictures show the progress of the algorithm. We annotated each

junction with its current height.

Initial state:

0. Push all cars away from the start:

1. Raise (Ada’s Column) to 1:

2. Push (Ada’s Column):

one car to Euler’s Gate:

34 Maximum Flows – Towards the Stadium During Rush Hour 341

3. Raise (Euler’s Gate) to 1 4. Push (E): 1 to C

We list some intermediate steps in short only:

5. Raise (C)to1 6.Push (C): 3 to F

7. Raise (F )to1 8.Push (F): 2 to Z

9. Raise (F ) to 2 10. Push (F): 1 to C

11. Raise (C) to 2 12. Push (C): 1 to E

13. Push (E): 1 to G 14. Raise (G)to1

15. Push (G): 1 to Z 16. Raise (B)to1

17. Push (B): 1 to D 18. Raise (D)to2

19. Push (D): 1 to B 20. Raise (B)to3

21. Push (B): 1 to D 22. Raise (D)to3

23. Push (D): 1 to F 24. Raise (A)t

o10

25. Push (A

): 2 to S 26. Raise (F )to3

27. Push (F ): 1 to C 28. Push (C): 1 to E

29. Raise (E)to2

30. Push (E): 1 to G

31. Push (G): 1 to Z

32. Raise (B)to10

33. Push (B): 2 to S

This is the solution to our problem:

342 Robert G¨orke, Steﬀen Mecke, and Dorothea Wagner

We could now use this solution to route traﬃc in the real world, avoiding

congestions.

Some Open Questions

• The algorithm does not specify which junction to choose each time step

6 is called. Any choice works as long as we obey the rules for pushing

(“always downwards”) and raising (“only if no more pushing is possible

and then only as high as necessary to push again”)! Our example needs

33 steps: 15 times Raise and 18 times Push (excluding the initial raising

of and pushing from the start). Try coming up with a diﬀerent sequence

of operations for our example. Can you ﬁnd one that reaches a solution

more quickly?

• Have you realized that excess ﬂow may only be pushed back to S, after a

junction has been raised higher than n?

Why Does It Work?

As if by magic, the algorithm always works correctly. If you are in the mood,

try playing around with diﬀerent road networks. But if you are interested in

why the algorithm works, continue reading:

First of all, we should convince ourselves that the algorithm outputs a

valid traﬃc ﬂow. To this end we must merely realize that:

• We have never pushed more cars along a road than ﬁt on it (capacity rule),

and

• no junction ends up with excess ﬂow (ﬂow conservation rule).

Thus the traﬃc can ﬂow unhindered.

Having tried a few examples, you will notice that there is a crucial dif-

ference between junctions which are higher than n, and those that are not.

From high junctions traﬃc is always pushed back towards S. These are the

junctions having no chance any more to pass their excess ﬂow on towards Z.

Butwhathappensbeforethis?

In the beginning excess ﬂow is only pushed from junctions at height 1 to

junctions at height 0. In a way these are the simple cases. Only after all simple

options are exhausted, are junctions gradually raised higher and higher. An

important observation is that excess ﬂow is always only pushed down one

level, i.e., from junction C at height h to a neighboring junction D at height

h − 1. It can never happen that this neighboring junction D has, e.g., height

h −2. After all, we would then not have been allowed to raise C that high in

the ﬁrst place. Cars that are supposed to arrive at Z must gradually descend

from h to h−1, then from h−1toh−2 and so on, until they arrive at Z,which

always remains at height 0. Therefore at least h diﬀerent stages are visited.

34 Maximum Flows – Towards the Stadium During Rush Hour 343

This ensures that excess ﬂow cannot be pushed back and forth perpetually

between two junctions. This is due to the fact that there can be at most

n − 1 diﬀerent stages (not n because we never pass through S). Moreover,

this guarantees that really all options to push forth excess ﬂow are exhausted,

before pushing back ﬂow to S. If by no means excess ﬂow can be routed to Z,

backward routing toward S works by the same principle. Ultimately all excess

ﬂow ends up at either Z or S, and we have ﬁnally found the best traﬃc ﬂow.

Epilogue

Some time later Jogi’s sister learned how to meticulously prove that this algo-

rithm ﬁnds the best traﬃc ﬂow. In fact, this is quite involved. It turned out,

that the order in which junctions are selected for Push and Raise operations

does not aﬀect the correctness of the algorithm. She also learned that Andrew

Goldberg and Robert Tarjan found this algorithm in 1988. Jogi often still gets

stuck in traﬃc jams on his way to the stadium.

Solution

There is actually a sequence of operations that requires only 19 steps to ﬁnd

the best traﬃc ﬂow:

1. Raise (A)to1 2.Push (A): 1 to E

3. Raise (C)to1 4.Push (C): 1 to E

5. Push (C): 1 to F 6. Raise (B)to1

7. Push (B): 1 to D 8. Raise (D)to1

9. Push (D): 1 to F 10. Raise (F)to1

11. Push (F): 2 to Z 12. Raise (E)to1

13. Push (E): 2 to G 14. Raise (G)to1

15. Push (G): 2 to Z 16. Raise (A)to10

17. Push (A): 2 to S 18. Raise (B)to10

19. Push (B

): 2 to S

Further Reading

1. Chapter 7 (Depth-First Search)

Many ﬂow algorithms are based on a so-called depth-ﬁrst search or

breadth-ﬁrst search in the graph. This is also true for the algorithm of

Ford–Fulkerson, for instance. In this chapter you can read up on how a

depth-ﬁrst search in a graph works, and how it can be used.

344 Robert G¨orke, Steﬀen Mecke, and Dorothea Wagner

2. Chapter 9 (Cycles in Graphs)

In rare cases, the algorithm of Goldberg and Tarjan sends a few units of

ﬂow around in a circle somewhere in the graph that does not contribute to

the actual ﬂow from the start to the target. By means of a cycle search,

these circular paths can be removed after the maximum ﬂow has been

determined. This chapter explains how this can be done.

3. Chapter 32 (Shortest Paths)

A problem closely related to maximum ﬂows is the search for a shortest

path. Here the goal is not to route a whole ﬂow of cars from the start to

the target but to ﬁnd the quickest route for a single car. You can read up

on how these shortest paths can be found in this chapter.

4. The 3D-animation Flow Commander at

http://i11www.iti.uni-karlsruhe.de/adw/jaws/GTVisualizer3D.

jnlp (requires Java Web Start).

Why not look at height as an actual third dimension? Fly through the

graph and behold Push and Raise operations taking place in 3D! If Java

is installed on your computer (which is most likely the case), you can

install and launch Flow Commander at this URL.

5. One of the quickest algorithms for maximum ﬂows: Lestor R. Ford, Jr. and

D.R. Fulkerson. Flows in Networks. Princeton University Press, 1962.

6. The original publication of the presented algorithm: Andrew V. Goldberg

and Robert E. Tarjan: A new approach to the maximum-ﬂow problem.

Journal of the ACM 35:921–940, 1988.

http://dx.doi.org/10.1145/48014.61051

7. The English Wikipedia article on the algorithm of Goldberg and Tarjan:

http://en.wikipedia.org/wiki/Push-relabel

algorithm

8. The Wikipedia article on network ﬂow:

http://en.wikipedia.org/wiki/Flow

network

Among other things this article explains how ﬂows are interrelated to

so-called cuts.

Marriage Broker

Volker Claus, Volker Diekert, and Holger Petersen

Universit¨at Stuttgart, Stuttgart, Germany

35.1 Problem

A marriage broker attempts to create the greatest possible number of couples

from a given set of men and women. A necessary condition is that the two

persons who form a couple are mutually friendly. We also assume the classic

marriage: Each pair consists of exactly one man and one woman, and each

person appears in the set of couples not more than once.

Put somewhat more abstractly, there is a set H of men, a set D of women

and a set L of “friendly couples” of the form HD. An entry of the form HD

means that the man H and the woman D are mutually friendly. The goal is to

form the largest number of couples from L, with no person a member of more

than one couple. Figure 35.1 shows a set H = {A, B, C, D, E} of 5 men and

asetD = {P, Q,R,S,T } of 5 women. If a man and a woman are mutually

friendly, we connect them with a line (a so-called edge). As an example, we

look at a set L with the sympathy-relations AP , AR, BP, BQ, BS, CQ, CR,

CT, DR, DS, ES and ET. This is graphically shown in Fig. 35.2.

Fig. 35.1. Five women and ﬁve men

B. V¨ocking et al. (eds.), Algorithms Unplugged,

DOI 10.1007/978-3-642-15328-0

35,

 Springer-Verlag Berlin Heidelberg 2011

346 Volker Claus, Volker Diekert and Holger Petersen

Fig. 35.2. The sympathy-relations between men and women

Now the broker could choose the following couples: BP, CR, ES. However

then the broker has to stop, because he cannot put together another suitable

pair. But the broker may also have formed couples AP , BQ, CR, DS and

ET, in which case all persons would have a partner. Now the problem is: How

does one ﬁnd a largest possible subset M of L, in which every person from H

and D appears not more than once? Such a subset M is called a maximum

matching for H, D and L.

First we want to introduce the idea and after that the algorithm which

helps to construct such a maximum matching. It is unimportant whether the

algorithm is executed by an employee of the broker (using index cards and

other tools) or by request of the aﬀected persons between themselves.

35.2 The Basic Principle of the Procedure

Initially, one can put people together into couples if they are friendly but not

already assigned to another couple. Once this is no longer possible, there can

be a partnerless person (here we take a partnerless man H) who asks all the

women who are friendly to him whether they can leave their partner.

These women are assigned to exactly one man, and therefore they hand

over the question to their partner. In the next step all these men ask all

the women who are friendly to them whether these women can leave their

partner. Now these women ask their assigned men whether they could ﬁnd

a new partner, etc. A wave of inquiries runs from the partnerless man H to

women who are friendly to him, and from these to their respective assigned

men and even spreads further to the set of all persons until one of the following

conditions is met:

(i) At one point a man asks a previously partnerless woman. In this case the

whole wave of requests stops immediately. From this new partnership one

35 Marriage Broker 347

follows the chain of requests backwards toward the man H and exchanges

the previous partnerships along exactly this way.

(ii) One ﬁnds out that the wave of requests reaches only women who already

have partners. In this case one deletes the man H from the set of men.

Subsequently one can adopt this picture of a wave of requests, spreading

from H toward all persons, alternately going through a friendly relationship

and an already taken assignment. Once a new partnership is discovered, this

wave breaks abruptly, and the couples are rearranged on the path of requests

from this new partnership to H.

Hint: This wave can be processed simultaneously or in any sequence, but

the most vivid picture is the parallel uniformly spreading wave (in Computer

Science we talk about breadth-ﬁrst search regarding L). Here no person is

asked who has already been questioned once, so that the wave only expands

to persons who have not yet been considered.

35.3 The Construction of a Maximum Matching

One starts with any pair from the set L. Let this pair be HD and put M =

{HD}. (If the set L is empty, there are, of course, no couples to form and

there is nothing to do.) Note that in the set M below each person appears

not more than once.

Now we can assume that a set of couples M = {H

,...,H

}

has been constructed. If all men occur in M one is ﬁnished, because bigamy is

illegal. The interesting situation is when a man H is without a female partner,

thus he does not occur in M. How can we assign to him a female partner D?

(a) Obviously one has to ask every person D about person H who has

sympathies for D (i.e., HD is included in the set L), whether she still has

no partner. If there exists such a person D without a partner, then one just

adds HD to the set M and applies the algorithm again to another partnerless

person. We have performed this by starting from the pair BP by adding pairs

CR and ES in Fig. 35.3.ThesetM = {BP,CR,ES} is given by the red

edges. Case (a) is not true any more and we cannot enlarge M in this way,

although there are still partnerless persons left.

(b) What has to be done if there is no partnerless person D matching

the partnerless person H in L? Then there is a partner H



assigned to each

person D, who is found friendly by H. Now one tries to take away woman D

from man H



in favor of man H, which means one tries to replace H



D by

HD, consequently H



becomes partnerless.

Now one tries to take away the partner H



from one of the women D



(but not the woman D), who is friendly to H



,makingH



partnerless and

requiring another partner, etc. Only such women D



, D



, D



, etc., are being

considered who have not yet been included. Based on H a sequence of alter-

nating friendship relations HD and already allocated H



D relations from the

348 Volker Claus, Volker Diekert and Holger Petersen

Fig. 35.3. Assembly of the set M only with criterion (a) of the algorithm

set M is passed through. At one point either case (a) occurs, or the iteration

stops when all persons reachable in this way have been tried unsuccessfully.

If case (a) occurs, then one has obtained a new set of couples by actually

making the replacements “H



D was replaced by HD,” which leads to the

case (a), while all other couples in M remain unchanged. Expressed more

precisely: If case (a) occurs the ﬁrst time, then there is exactly one sequence

(starting with H = H

)

,...,H

with H

being partnerless, H

∈L,H

∈ M, H

∈L,...,H

k−1

∈

M,H

∈Land D

is partnerless. The situation with the partnerless

woman D

allows the replacement of the red edges in M by the black edges (“re-coloring”

of red and black edges on this path):

where M grows by one pair and all persons who already had a partner before

now have a partner once again. With this increased set M one starts the

algorithm again.

In our example, this approach leads to success (see Figs. 35.4–35.8): Previ-

ously, the couples BP, CR and ES were selected. More couples are no longer

possible. So now couples have to be regrouped. For this we assume in Fig. 35.4

the man A, who still has no partner. We assign to him one of his potential

partners P or R, which now makes man B (former partner of P )orC (former

partner of R) partnerless; for each of these again an attempt is made to ﬁnd

new female partners (Fig. 35.5), etc. Each person is not treated more than

35 Marriage Broker 349

Fig. 35.4. A is partnerless. A could be paired with P or with R. We start with P .

Her partner is B. Experimentally we now replace BP by AP , indicated by dashed

edges

Fig. 35.5. Now B is partnerless. The case (a) occurs already, because the couple

BQ with the partnerless woman lies in L

once, i.e., if during the process a person is met who has already been investi-

gated, he or she is not considered again. If case (a) occurs, one gets a new set

M,asshowninFig.35.8.

theorem states that the person H may be excluded from the further proce-

dure.

In principle, this situation is quite easy to understand. Because what hap-

pens if the set M does not get enlarged? Then there is a set of d women, who

have been totally questioned starting from H.Eachofthesed women also has

a partner after the rearrangement, so there are d men with a partner. Only

the last of the men who lost his partner, now has none. So there are d +1

men who occurred in this row. And here comes the crucial observation: The