Anyways, the core of an attribute grammar scheduler is a topological sort of dependencies. I found this difficult to write. Originally, I tried using a successor relation, where each step was the set of edges (or nodes) that are reachable from the previous. No go, and searching on the web, I didn't see anything else. So, here's another tact:

Given the data:

edge('aa', 'b').

edge('a', 'b').

edge('b', 'c').

edge('c', 'd').

edge('d', 'y').

edge('d', 'z').

edge('a', 'm').

edge('m', 'n').

edge('n', 'o').

edge('o', 'y').

edge('o', 'z').

node(?n) :- edge(?n, ?m).

node(?n) :- edge(?m, ?n).

We calculate the flows-to relation, and then, for each edge, propagate 1 + the label of the previous edge. Finally, we take the maximal incoming label for each node, and voila!

flows(?n, ?m) :- edge(?n, ?m).

flows(?n, ?m) :- flows(?n, ?x), flows(?x, ?m).

whenAll(?n, 0) :- node(?n), !edge(?m, ?n).

whenAll(?n, ?c) :- whenAll(?m, ?d), flows(?m, ?n), ?d + 1 = ?c.

when(?n, ?c) :- whenAll(?n, ?c), ?c + 1 = ?d, !whenAll(?n, ?d).

Testing the result:

?- when(?n, ?c).

Query: ?- when(?n, ?c). ==>> 10 rows in 0ms

Variables: ?n, ?c

('aa', 0)

('a', 0)

('b', 1)

('m', 1)

('c', 2)

('n', 2)

('d', 3)

('o', 3)

('y', 4)

('z', 4)