The Algorithm Design Manual Second Edition

Stop and Think: Ordering the Sequence

Problem: “A DNA sequencing project generates experimental data consisting of

small fragments. For each given fragment f , we know certain other fragments are

forced to lie to the left of f , and certain other fragments are forced to be to the

right of f . How can we find a consistent ordering of the fragments from left to right

that satisfies all the constraints?”

Solution: Create a directed graph, where each fragment is assigned a unique vertex.

Insert a directed edge

−→

(l, f ) from any fragment l that is forced to be to the left

But what is the graph? One approach might be to lay a grid of points in the

room. Create a vertex for each grid point that is a valid place for the character

to stand; i.e., that does not lie within an obstacle. There will be an edge between

---

224

6 .

W E I G H T E D G R A P H A L G O R I T H M S

of f , and a directed edge

−→

(f, r) to any fragment r forced to be to the right of f .

We seek an ordering of the vertices such that all the edges go from left to right.

This is a topological sort of the resulting directed acyclic graph. The graph must

be acyclic, because cycles make finding a consistent ordering impossible.