Thinking In Prolog - for procedural programmers

Help!
15

Here’s an example from The Craft of Prolog for converting a predicate of node pairs into an adjacency list:

    bagof(T1-T2s,
          bagof(T2, edge_pair(T1, T2), T2s),
          AdjancyGraph).

If you replace the bagofs with findall, this won’t work.

Minor note 1: the book uses setof rather than bagof; I think that this is only needed if there are duplicate facts in edge_pair/2.

Minor note 2: the book claims that this suffices for creating an adjacency graph for library(ugraph) top_sort/2 (topological sort). However, it seems that top_sort/2 requires more entries:

edge_pair(a,b).
edge_pair(a,c).
edge_pair(b,c).
edge_pair(b,d).

no_succ(T) :-
    edge_pair(_, T),
    \+ edge_pair(T, _).


adj(TaskGraph) :-
    bagof(T1-T2s,
          bagof(T2, edge_pair(T1, T2), T2s),
          TaskGraph1),
    setof(T-[], no_succ(T), TaskGraph2),
    append(TaskGraph1, TaskGraph2, TaskGraph).

tasks(TaskList) :-
    adj(TaskGraph),
    top_sort(TaskGraph, TaskList).
1 Like