Program Analysis Problem Sheet 11
1. The question considers the Ford-Fulkerson Algorithm. MaximumFlow(G, s, t, c, ):
let f(e) = 0 for all e ∈ E
while there is a path from s to t in the residual graph Gf
let p be a simple path from s to t
f ← augment(G, f, p)
let Gf be the new residual graph associated with f
return f augment(G, f, p):
let the bottleneck edge in p have capacity x for each edge (u, v) in the path p
if (u, v) is a forward edge then f (u, v) ← f (u, v) + x
if (u, v) is a backward edge then f (v, u) ← f (v, u) − x
Term 1, 2015
return f
We will look at how this algorithm would apply to the following network.
v 18 v 25
11 16 12 26 15 16
s v3 t 28 5
32 20 22
v1
v4
source
flow
sink
(a) Show the residual graph that would be produced given the initial zero flow rates in the network. In drawing a residual graph, to compactly show a forward edge with capacity x and a backward edge with capacity y, label the original edge −→x ; ←−y .
Program Analysis Model Answer:
Term 1, 2015
Residual graph:
−→ ←−
v2 −→ ←−
18; 0
v5 −→ ←−
−→ ←−
−→ ←−
−→ ←−
−→ ←−
11; 0
16; 0
12; 0
26; 0
15; 0
16; 0
s v3 t
−→ ←−
−→ ←−
−→ ←−
32; 0
20; 0
22; 0
−→ ←−
−→ ←−
28; 0
5 ; 0
v1
v4
(b) Select path (s, v2, v3, t), and show the residual graph that results from augmenting the flow based on this path.
Model Answer:
Residual graph:
v2 −→ ←−
18; 0
v5 −→ ←−
−→ ←−
−→ ←−
−→ ←−
−→ ←−
−→ ←−
0;11
5;11
12; 0
26; 0
15; 0
5;11
s v3 t
−→ ←−
−→ ←−
−→ ←−
32; 0
20; 0
22; 0
−→ ←−
−→ ←−
28; 0
5 ; 0
v1
v4
(c) Now select path (s, v3, v5, t), and show the residual graph that results from aug- menting the flow based on this path.
Model Answer: Residual graph:
Program Analysis
v2 −→ ←−
Term 1, 2015
0 ; 11
5 ; 11
0 ; 12
14; 12
−→ ←−
3 ; 12
5 ; 11
−→ ←−
18; 0
v5 −→ ←−
−→ ←−
−→ ←−
−→ ←−
s v3 t
−→ ←−
−→ ←−
−→ ←−
32; 0
20; 0
22; 0
−→ ←−
−→ ←−
28; 0
5 ; 0
v1
v4
(d) Nowselectpath(s,v3,v2,v5,t),andshowtheresidualgraphthatresultsfromaug- menting the flow based on this path.
Model Answer:
Residual graph:
−→ ←−
v2 −→ ←−
15; 3
v5 −→ ←−
−→ ←−
−→ ←−
−→ ←−
−→ ←−
0;11
8; 8
0;12
11; 15
0 ; 15
5 ; 11
s v3 t
−→ ←−
−→ ←−
−→ ←−
32; 0
20; 0
22; 0
−→ ←−
−→ ←−
28; 0
5 ; 0
Model Answer:
Residual graph:
v1
v4
(e) Now select path (s, v1, v4, t), and show the residual graph that results from aug- menting the flow based on this path.
v2 −→ ←−
15; 3
v5 −→ ←−
−→ ←−
−→ ←−
−→ ←−
−→ ←−
−→ ←−
0;11
8; 8
0;12
11; 15
0 ; 15
5 ; 11
s v3 t
−→ ←−
−→ ←−
−→ ←−
12;20
0 ; 20
2 ; 20
−→ ←−
−→ ←−
28; 0
5 ; 0
v1
v4
Program Analysis Term 1, 2015
(f) Now select path (s, v1, v3, t), and show the residual graph that results from aug- menting the flow based on this path.
Model Answer:
Residual graph:
−→ ←−
v2 −→ ←−
15; 3
v5 −→ ←−
−→ ←−
−→ ←−
−→ ←−
−→ ←−
0;11
8; 8
0;12
11;15
0 ; 15
0 ; 16
s v3 t
−→ ←−
−→ ←−
−→ ←−
7;25
0 ; 20
2;20
−→ ←−
−→ ←−
23; 5
5 ; 0
v1
v4
(g) Now select path (s, v1, v3, v2, v5, t), and show the residual graph that results from augmenting the flow based on this path.
Model Answer:
Residual graph:
v2 −→ ←−
8 ; 10
v5 −→ ←−
−→ ←−
−→ ←−
−→ ←−
−→ ←−
−→ ←−
0;11
15; 1
0;12
4;22
0 ; 15
0 ; 16
s v3 t
−→ ←−
−→ ←−
−→ ←−
0;32
0 ; 20
2;20
−→ ←−
−→ ←−
16;12
5; 0
v1
v4
(h) Show the flow rates that have been achieved for the network. Model Answer: Final flow rates
Program Analysis Term 1, 2015
v
10/18 v 25
11/11
1/16 12/12 22/26 16/16
15/15
s v3 t
12/28
0/5
32/32
source
v1
20/20
flow
v4
20/22
sink
(i) Identify a cut of the network that has a cut capacity equal to the maximum flow of the network.
Model Answer: The cut required here is A = {s} and B = V − {s}. The max- imum flow of 58 is equal to the cut capacity of this cut, since it is the sum of the capacities for the edges (s, v1), (s, v2) and (s, v3).
Program Analysis Term 1, 2015 2. Suppose you’re a consultant for the Ergonomic Architecture Commission, and
they come to you with the following problem.
They’re really concerned about designing houses that are “user-friendly,” and they’ve been having a lot of trouble with the setup of light fixtures and switches in newly designed houses. Consider, for example, a one-floor house with n light fixtures and n locations for light switches mounted in the wall. You’d like to be able to wire up one switch to control each light fixture, in such a way that a person at the switch can see the light fixture being controlled.
Sometimes this is possible and sometimes it isn’t. Consider the two simple floor plans for houses in Figure 1. There are three light fixtures (labelled a b, c) and three switches (labelled 1, 2, 3). It is possible to wire switches to fixtures in Fig- ure 1(a) so that every switch has a line of sight to the fixture, but this is not possi- ble in Figure 1fig:3(b).
Let’s call a floor plan, together with n light fixture locations and n switch loca- tions, ergonomic if it’s possible to wire one switch to each fixture so that every fixture is visible from the switch that controls it. A floor plan will be represented by a set of m horizontal or vertical line segments in the plane (the walls), where
the ith wall has endpoints (xi, yi), (x′i, yi′). Each of the n switches and each of the n fixtures is given by its coordinates in the plane. A fixture is visible from a switch if the line segment joining them does not cross any of the walls.
Give an algorithm to decide if a given floor plan is ergonomic. The running time should be polynomial in m and n. You may assume that you have a subrou- tine with O(1) running time that takes two line segments as input and decides whether or not they cross in the plane.
2 33
(a) Ergonomic (b) Not ergonomic
Figure 1: The floor plan in (a) is ergonomic, because we can wire switches to fixtures in such a way that each fixture is visible from the switch that controls it. (This can be done by wiring switch 1 to a, switch 2 to b, and switch 3 to c.) The floor plan in (b) is not ergonomic, because no such wiring is possible.
a
1** 2
c
*
b
a
1**
c
*
b
Program Analysis Term 1, 2015
Model Answer: We build the following bipartite graph G = (V, E). V is par- tioned into sets X and Y , with a node xi ∈ X representing switch i, and a node yi ∈Y representingfixturej.(xi,yj)isanedgeinEifandonlyifthelinesegment from xi to yi does not intersect any of the m walls in the floor plan. Thus, whether (xi, yi) ∈ E can be determined initially by m segment-intersection tests; so G can be built in time O(n2m).
Now, we test in O(n3) time whether G has a perfect matching, and declare the floor plan to be “ergonomic” if and only if G does have a perfect matching. Our answer is always correct, since a perfect matching in G is a pairing of the n switches and the n fixtures in such a way that each switch can see the fixture it is paried with, by the definition of the edge E; conversely, such a pairing of switches and fixtures defines a perfect matching in G.
Program Analysis Term 1, 2015
3. Consider a set of mobile computing clients in a certain town who each need to be connected to one of several possible base stations. We’ll suppose there are n clients, with the position of each client specified by its (x, y) coordinates in the plane. There are also k base stations; the position of each of these is specified by (x, y) coordinates as well.
For each client, we wish to connect it to exactly one of the base stations. Our choice of connections is constrained in the following ways. There is a range pa- rameter r — a client can only be connect to a base station that is within distance r. There is also a load parameter L — no more than L clients can be connected to any single base station.
Your goal is to design a polynomial-time algorithm for the following problem. Given the positions of a set of clients and a set of base stations, as well as the range and load parameters, decide whether every client can be connected si- multaneously to a base station, subject to the range and load conditions in the previous paragraph.
Model Answer: We build the following flow network. There is a node vi for each client i, a node wj for each base station j, and an edge (vi,wj) of capacity 1 if client i is within range of base station j. We then connect a super-source s to each of the client nodes by an edge of capacity 1, and we connect each of the base station nodes to a super-sink t by an edge of capacity L.
We claim that there is a feasible way to connect all clients to base stations if and only if there is an s − t flow of value n. If there is a feasible connection, then we send one unit of flow from s to t along each of the paths (s, vi , wj , t) where client i is connected to base station j. This does not violate the capacity conditions, in particular on the edges (wj , t) due to the load constraints. Conversely, if there is a flow of value n, then there is one with integer values. We connect client i to base station j if the edge (vi , wj ) carries one unit of flow, and we observe that the capacity condition ensures that no base station is overlooked.
The running time is the time required to solve a maximum flow problem on a graph with O(n + k) nodes and O(nk) edges.