eyeprolog

Roads across France

Which cities can you reach by one-way roads?

Ten one-way roads connect cities in France. Two rules compute every city reachable from every other, and EyeProlog explains each route by the roads it used.

Run it in the playground · Source

The question

A road from Paris to Orléans and one from Orléans to Blois mean you can get from Paris to Blois. Reachability is the transitive closure of the road relation: one or more legs, always in the direction of travel.

The roads

oneway(paris, orleans).
oneway(paris, chartres).
oneway(paris, amiens).
oneway(orleans, blois).
oneway(orleans, bourges).
oneway(blois, tours).
oneway(chartres, lemans).

oneway(A, B) means there is a road from A to B, not back.

The rules

path(A, B) :-
    oneway(A, B).
path(A, C) :-
    oneway(A, B),
    path(B, C).

A path is a road, or a road followed by a path. The recursive rule takes a concrete road first and only then asks the smaller question from the next city. That order is what makes the search productive: written as path(A, B), path(B, C), the rule would start by asking the very question it is trying to answer.

The answer

eyeprolog examples/graph.pl

path(paris, orleans).
path(paris, chartres).
path(paris, amiens).
path(orleans, blois).
path(orleans, bourges).

21 answers in total: the 10 direct roads, then the longer routes such as path(paris, nantes) and path(chartres, tours).

The reason

step(path(paris, tours),
     rule(12),
     ['A' = paris, 'C' = tours, 'B' = orleans],
     [oneway(paris, orleans), path(orleans, tours)]).
step(path(orleans, tours),
     rule(12),
     ['A' = orleans, 'C' = tours, 'B' = blois],
     [oneway(orleans, blois), path(blois, tours)]).

Paris reaches Tours through Orléans, Orléans reaches Tours through Blois, and path(blois, tours) is a direct road. Read top-down, the steps spell out the route Paris → Orléans → Blois → Tours.

The check

condition('C1', resolution, ok, 31).
condition('C4', coverage, ok, 53).
condition('C7', relevance, ok, 52).
verdict(checked).

All 31 steps replay against the clauses they cite, and all 21 claims are covered. Nothing is trusted.

Try it

Add oneway(nantes, paris). The graph now has a cycle and the untabled search no longer finishes. Add :- table path/2. and it does.
Ask only where you can go from Chartres: --goal 'path(chartres, X)'.
Replace the recursive rule with the left-recursive path(A, C) :- path(A, B), path(B, C). What happens to the run?

Learn more in The Art of EyeProlog, Chapters 4 and 13.

This site is open source. Improve this page.