I just began reading Data Structures and Algorithms (Aho, Hopcraft, and Ullman). At the beginning, there is an example that discusses designing a traffic light for a complicated intersection of roads.

A visual is given of the intersection along with a table of incompatible turns ("turns" are considered to be any movement from one part of the intersection to another).

Here is the intersection:

enter image description here

Here is the table of incompatible turns:

enter image description here

I'm confused by some of the data shown here. If we just take the first column as an example, the turns listed as "incompatible" make sense i.e. a turn from A to B (AB) cannot be safely performed while a turn is being made from B to C (BC). Likewise, the turn AB clearly cannot be made safely while turn BD is being made.

However, the turns AB and DB are listed as compatible turns. Also, AB and EB are listed as compatible. Why?

I realize collisions can potentially be avoided here if people observe the "right-of-way," but I still don't see how these are considered compatible. They seem like collision courses.

I see how the listed incompatible turns cannot be avoided with the "right-of-way," while the turns I am questioning can potentially be avoided. However, the book mentions nothing about "right-of-way," so I'm simply making an assumption here.

Am I missing something obvious?

Note: I posted my question here because this book is on computer science, and there isn't a stack exchange site for algorithms. This also seems too theoretical to be posted on the engineering site, but I wasn't exactly sure where to post it.

Thank you for your help. I'd rather not read a book on algorithms with uncertainty. This book is recommended by Carnegie Mellon's Department of Software Engineering, so I'm assuming it's a fine source of information.


Here is another graph of the incompatible turns:

enter image description here

  • $\begingroup$ I'm not seeing anywhere a definition of which turns are compatible. Without such a definition, you could replace Figure 1.3 with an arbitrary table of your choice, which will be as valid, since Figure 1.3 defines the notion of compatibility. Does the text define when two turns are compatible? $\endgroup$ – Yuval Filmus Jan 20 '18 at 16:10
  • $\begingroup$ There isn't a clear definition of compatible turns. Here's what is written: "Some pairs of turns, like AB (from A to B) and EC, can be carried out simultaneously, while others, like AD to EB, cause lines of traffic to cross and therefore cannot be carried out simultaneously. The light at the intersection must permit turns in such an order that AD and EB are never permitted at the same time, while the light might permit AB and EC to be made simultaneously." In figure 1.2, the vertices represent turns and the edges connect pairs of vertices whose turns cannot be performed simultaneously. $\endgroup$ – Dan Kreiger Jan 20 '18 at 18:15
  • $\begingroup$ I suggest ignoring this example. It's meaningless without clear definitions. $\endgroup$ – Yuval Filmus Jan 20 '18 at 18:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.