DP on a directed acyclic graph
The tables for the frog, the stairs and the coins were filled from left to right, and that worked because each entry only read entries to its left. The frog's figure, repeated below, shows why. Each stone is a circle, each jump is an arrow, and a stone's entry is computed from the stones with arrows into it. Every arrow points right, so going from left to right always fills the start of an arrow before its end.
Any DP can be drawn like that. The drawing is called the DP's dependency graph: it has one vertex per state, and an arrow from state to state whenever the transition for reads the value of . For the table to be filled, it must have no cycle: a state on a cycle would need its own value before it could be computed, and a recursive function for it would call itself forever. A directed graph without cycles is called a directed acyclic graph (DAG).
An order of the vertices in which every arrow runs from an earlier vertex to a later one is a topological order, and Kahn's algorithm, which the Graphs lesson builds step by step, computes one. In these terms, an evaluation order for a DP is a topological order of its states.
Most DP programs never store this graph or compute that order, because the arrows follow a pattern, such as all pointing right, that a loop follows. For many DPs that make a sequence of choices, the answer is a cheapest or longest path through this graph. The frog's cheapest route, for example, is the cheapest path from stone 0 to the last stone when each arrow costs its jump.
A problem that gives the graph directly
In the next problem the input is the graph itself, and the answer is a longest path. A flight may go from a higher-numbered city to a lower one, so the city numbers are not an order we can rely on, and the program has to find a topological order as it fills the table.
There are cities and one-way flights, and no sequence of flights returns to a city it has left. Find a route from city 1 to city that visits as many cities as possible.
The first input line holds and , and each of the next lines holds a flight from city to city . Print the number of cities on the best route, then the cities in order; any best route is accepted. If city cannot be reached, print IMPOSSIBLE.
Constraints
Sample · Input
5 5 1 2 2 5 1 3 3 4 4 5
Output
4 1 3 4 5
In the sample, the route 1, 2, 5 visits three cities and the route 1, 3, 4, 5 visits four, so the answer is 4. Listing every route is hopeless at the limits. If each city has flights to cities and , the routes from city 1 to city are the frog's routes over stones, and for their number has 20,899 digits.
The table needs far less work. The state is a city: let best[v] be the largest number of cities on a route from city 1 to city . The last flight of such a route arrives from some city , and the part before that flight is a route from city 1 to , which has at most best[u] cities. So best[v] is one more than the largest best[u] among the cities that have a flight to , and city 1 is the base case:
Unreachable cities and the route itself
- A city that city 1 cannot reach has no route at all, so it must not pass a length on to other cities. The table stores 0 for "no route found". Every real route has at least one city, so 0 cannot be mistaken for a length.
- The problem asks for the route as well as its length. As with the frog,
parent[v]records the city whosebest[u]gavebest[v]its value, and the route is read by following parents back from city .
The order from Kahn's algorithm
Kahn's algorithm builds a topological order by taking one vertex at a time and putting it next in the order. For each vertex it keeps a count of the arrows into it from vertices not yet taken. The count starts at the vertex's indegree, the number of arrows into it, and the algorithm takes a vertex once its count reaches 0.
The widget lets you run it on the sample's flights. It calls the vertices tasks and numbers them from 0, so task 0 is city 1 and task 4 is city 5. The badge on a task shows its count, and only a task at 0 can be taken.
After city 1 is taken, cities 2 and 3 (tasks 1 and 2) both show 0. Take them in either order. The table comes out the same, because a city's entry only needs the entries of the cities that fly into it to be finished first.
The button that adds the edge , in the widget's numbering, puts in a flight from city 4 back to city 3. Cities 3 and 4 then wait for each other, the order stops after cities 1 and 2, and the table cannot be completed. The problem rules this out by promising that no sequence of flights returns to a city it has left.
Turn the transition around
The transition looks at the flights into a city, but an adjacency list stores the flights out of each city. So the program turns the transition around. When Kahn's algorithm takes a city , the program offers best[u] + 1 to every city that flies to, and keeps the largest offer it has received. Kahn's algorithm takes only after every flight into it has been processed, so by then every offer has arrived and best[v] is final. On the sample it goes like this:
| City taken | Its best | Offers it makes |
|---|---|---|
| 1 | 1 | 2 to city 2 and 2 to city 3 |
| 2 | 2 | 3 to city 5 |
| 3 | 2 | 3 to city 4 |
| 4 | 3 | 4 to city 5, which beats the 3 from city 2, so city 4 becomes the parent of city 5 |
| 5 | 4 | none |
Fill the table while Kahn's algorithm runs
The program is Kahn's algorithm with three lines added inside its loop over the flights out of a city: the test of the offer against best[v], and the two assignments under it.
def longest_route(n, flights):
graph = [[] for _ in range(n + 1)]
indegree = [0] * (n + 1)
for a, b in flights:
graph[a].append(b)
indegree[b] += 1
best = [0] * (n + 1) # 0: not reachable from city 1
parent = [0] * (n + 1)
best[1] = 1
ready = deque(v for v in range(1, n + 1) if indegree[v] == 0)
while ready:
u = ready.popleft()
for v in graph[u]:
if best[u] > 0 and best[u] + 1 > best[v]:
best[v] = best[u] + 1
parent[v] = u
indegree[v] -= 1
if indegree[v] == 0:
ready.append(v)
if best[n] == 0:
return None
route = [n]
while route[-1] != 1:
route.append(parent[route[-1]])
return route[::-1]
data = sys.stdin.read().split()
n, m = int(data[0]), int(data[1])
flights = [(int(data[2 + 2 * i]), int(data[3 + 2 * i])) for i in range(m)]
route = longest_route(n, flights)
if route is None:
print("IMPOSSIBLE")
else:
print(len(route))
print(*route)On the sample the program prints 4 and the route 1 3 4 5.
The queue starts with every city that has no flight into it, whether or not city 1 can reach it. An unreachable city makes no offer, but taking it still lowers the indegrees of the cities it flies to, and without that those cities would never be taken.
Each city enters the queue once and each flight is processed once, so the running time is , about steps at the limits.
The same table by recursion
A memoized recursive function gets the order without computing it first. Store, for each city, a list of the flights into it, and let best(v) call best(u) for every city with a flight into . A call returns only after the calls it made have returned, so the entries are finished in a topological order. The recursion is a depth-first search of the dependency graph along the arrows backwards, and a stored value marks a state as visited. The price is the depth of the recursion.
On a chain of cities the calls nest deep, and Python stops at about 1,000 nested calls unless the limit is raised.
Time and space of DP on a DAG
- Time
- Each city is taken once, and each flight makes one offer.
- Space
- The adjacency lists hold every flight.
best,parentand the indegrees take one number per city.
Common mistakes
Starting every city at a route of one city.
- Where it breaks
- The input
3 1with the one flight2 3should printIMPOSSIBLE. With everybeststarting at 1,best[3]becomes 2, built on the route 2, 3, which does not start at city 1. The testbest[n] == 0no longer fires, and the walk back along the parents visits 3, 2, 0, 0 and so on without ever arriving at city 1. - The fix
- Set only
best[1] = 1. Leave every other city at 0, and let a city whose entry is 0 make no offer.
Starting the queue with city 1 alone.
- Where it breaks
- With 4 cities and the flights
1 3,2 3and3 4, the answer is the route 1, 3, 4. City 3 waits for the flight from city 2 to be processed, city 2 is never taken, so city 3 never is either, and city 4 receives no offer. The program printsIMPOSSIBLE. - The fix
- Start the queue with every city whose indegree is 0.
Recall A flight from city 2 to city 3 is added to the sample. Which entries of `best` change, and is 1, 3, 2, 4, 5 still a valid order to fill them in?
City 3 now receives an offer of 3 from city 2 as well as the offer of 2 from city 1, so best[3] rises from 2 to 3. The change carries along the flights out of city 3: best[4] becomes 4 and best[5] becomes 5, for the route 1, 2, 3, 4, 5.
The order 1, 3, 2, 4, 5 is no longer topological, because the new flight runs from city 2 to city 3 and city 3 comes first. Filled in that order, city 3 would make its offer before hearing from city 2.
Key terms
| Term | Meaning |
|---|---|
| dependency graph | A drawing of a DP with one vertex per state and an arrow from state to state whenever the transition for reads . |
| directed acyclic graph (DAG) | A directed graph in which no sequence of arrows returns to a vertex it has left. |
| topological order | An order of the vertices in which every arrow runs from an earlier vertex to a later one. For a DP, it is an evaluation order. |