Tree Breadth-First in Prolog

[Mathie]

Hello !

I’m using: Prolog 6.2.2

I have a tree :

Whith this code :

/* The tree database */ 

:- op(500,xfx,'is_parent'). 

a is_parent b.    c is_parent g.     f is_parent l.     j is_parent q. 
a is_parent c.    c is_parent h.     f is_parent m.     j is_parent r. 
a is_parent d.    c is_parent i.     h is_parent n.     j is_parent s. 
b is_parent e.    d is_parent j.     i is_parent o.     m is_parent t. 
b is_parent f.    e is_parent k.     i is_parent p. 

I would like to do a depth-first research and a breadth-first research.

For the depth-first research, I did:

search(A) :- write(A),
            test(A).

test(A) :- nl,
          A is_parent B,
          print(B),
          test(B).

The rule works : a -> b -> e -> k -> f -> l -> m -> t -> c -> g -> h -> n -> i -> o -> p -> d -> j -> q -> r -> s

But I don’t know how to do breadth-first research. I would like to have this outing:

a -> b -> c -> d-> e -> f -> g -> g -> h -> i -> i -> j -> k -> l -> m -> n -> o -> p -> q -> r -> s -> t

I have no leads and I don’t know where to start.

Does anyone know how to do that?
Thanks you in advance

[EricGT]

@Mathie

I’m using: Prolog 6.2.2

You really should upgrade.

Does anyone know how to do that?

Of course we do; I take it you would like something more useful.

A place that has useful beginner code in many programming languages including Prolog is RosettaCode:

Prolog Tasks

Sample code for what you seek is: Tree Traversal
The specific example you want to look at is referred to as level order in the Prolog example. (link)

level_order([]).
 
level_order(A) :-
	level_order_(A, U-U, S),
	level_order(S).
 
level_order_([], S-[],S).
 
level_order_([[Node, FG, FD] | T], CS, FS) :-
	format('~w ', [Node]),
	append_dl(CS, [FG, FD|U]-U, CS1),
	level_order_(T, CS1, FS).
 
level_order_([nil | T], CS, FS) :-
	level_order_(T, CS, FS).
 
 
append_dl(X-Y, Y-Z, X-Z).

I did not test this but it should work. Also note that it uses a variation of append/3 that is commonly seen by new users of Prolog but is known by more experienced users.

Also, should your answer be?

a → b → c → d-> e → f → g → h → i → j → k → l → m → n → o → p → q → r → s → t

[Mathie]

@EricGT

level_order_

Thank you for your answer!
The problem is that my tree is not a list, which doesn’t really correspond to the example.

And I don’t see how to transcribe that with what I’ve done.

[EricGT]

@Mathie

And I don’t see how to transcribe that with what I’ve done.

That was expected.

I am looking for something simpler that I can just reference without having to write some code, but so far all of the examples want to use findall/3 which really doesn’t give any insight into how to solve the problem.

The basic trick is that you have to remember the links you have not visited and store them in something like a FIFO queue and then take them from the queue.

[EricGT]

Still looking for something better but remember that one of the users here did a tutorial on searching.

See: Graph traversal for problem solving tutorial

[joeblog]

I think that link may predate @jan’s fix of Swis updating. The current one is https://swish.swi-prolog.org/p/Graphs1.swinb

Prolog is “hardwired” to do depthfirst search, whereas doing breadthfirst requires you to manage the frontier list yourself. You invariably also end up having to manage the frontier list for depthfirst search to avoid hanging your computer if there are cycles (something tabling aims to solve, but I haven’t battled through its documentation yet).

I initially used code from Bratko’s textbook, but ditched it because it doesn’t illustrate the difference between depthfirst and breadthfirst clearly. The difference is very subtle in that depthfirst uses a stack and breadthfirst a queue. Unfortunately, while Prolog handles stacks very simply and quickly, its queues are confusing and slow if you’re a novice. I’ve tried to explain this at https://swish.swi-prolog.org/p/Iteration2.swinb.

Anyways, I have to tried to give some simple examples in the above Swish link.

[EricGT]

Here is some working code

:- op(500,xfx,'is_parent').

a is_parent b.    c is_parent g.     f is_parent l.     j is_parent q.
a is_parent c.    c is_parent h.     f is_parent m.     j is_parent r.
a is_parent d.    c is_parent i.     h is_parent n.     j is_parent s.
b is_parent e.    d is_parent j.     i is_parent o.     m is_parent t.
b is_parent f.    e is_parent k.     i is_parent p.

start(Parent,In_order) :-
    queue([Parent],[],In_order).

queue([],In_order,In_order).
queue([Parent|Queue0],In_order0,In_order) :-
    append(In_order0,[Parent],In_order1),
    findall(Child,Parent is_parent Child,Children),
    append(Queue0,Children,Queue),
    queue(Queue,In_order1,In_order).

I still don’t like that I am using findall/3 for a beginner example as it hides some of the details.

Example run:

?- start(a,In_order);true.
In_order = [a, b, c, d, e, f, g, h, i|...] [write]
In_order = [a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q, r, s, t] .

Since the answer was long made use of Help: I want the whole answer

---

Here are the details.

The first thing needed is to find the children of a parent. This is accomplished using findall/3, e.g.

?- findall(Child,a is_parent Child,Children).
Children = [b, c, d].

says to use a is_parent Child on the facts and only remember the Child and collect them into Children

The next thing is to keep a FIFO queue of the nodes visited. This is done using

start(Parent,_) :-
    queue([Parent],_,_).

queue([],_,_).
queue([Parent|Queue0],_,_) :-
    ...,
    findall(_,_,Children),
    append(Queue0,Children,Queue),
    queue(Queue,_,_).

where the queue is initialized with queue([Parent],_,_)
new nodes to add to the queue are found with findall(_,_,Children)
the new nodes are added to the queue with append(Queue0,Children,Queue)
and the new queue is passed along in queue(Queue,_,_) for the recursion.
Also a base case is needed for the recursion queue([],_,_).

Instead of printing out the nodes as they were visited I just accumulated them into the in_order list, e.g.

start(_,In_order) :-
    queue(_,[],In_order).

queue(_,In_order,In_order).
queue([Parent|_],In_order0,In_order) :-
    append(In_order0,[Parent],In_order1),
    ...,
    ...,
    queue(_,In_order1,In_order).

The in_order list is internalized with [] in queue(_,[],In_order)
The in_order list accumulates the current node Parent with append(In_order0,[Parent],In_order1)
and the new in_order list is passed along in queue(_,In_order1,In_order) for the recursion.
Also a base case is needed for the recursion queue(_,In_order,In_order) that moves the accumulated values into the output variable to be passed back up.

You can add the fancy formatting with -> but this gives you the more technical parts of the FIFO queue.

Also note that this code only works on trees, no DAGs or graphs. The reason being that it does not keep track of which nodes it has visited. That is easily added and would not be surprised if that is one of the next exercises.

[Mathie]

@EricGT

Also note that this code only works on trees, no DAGs or graphs. The reason being that it does not keep track of which nodes it has visited. That is easily added and would not be surprised if that is one of the next exercises.

Thank you very much, you’re really nice!
I’ll look around to try to understand all this. I need to understand how the lists work.

Thank you again! I come back to you

[Boris]

If you can get a copy of “The Craft of Prolog” by Richard O’Keefe: in Chapter 2, “Searching”, you will find good explanations of the usual search algorithms (including breadth-first search). There are complete, well explained code listings there. Just go to the library and find the book.

[joeblog]

Here’s one way you could do it

:- op(500,xfx,'is_parent').

a is_parent b.    c is_parent g.     f is_parent l.     j is_parent q.
a is_parent c.    c is_parent h.     f is_parent m.     j is_parent r.
a is_parent d.    c is_parent i.     h is_parent n.     j is_parent s.
b is_parent e.    d is_parent j.     i is_parent o.     m is_parent t.
b is_parent f.    e is_parent k.     i is_parent p.

getchildren(Parent, Children) :-
    setof(Child, Parent^is_parent(Parent, Child), Children), !.
getchildren(_, []).

depthfirst([]) :- !.
depthfirst([Node|Frontier]) :-
    format('~p ', [Node]),
    getchildren(Node, Children),
    append(Children, Frontier, NewFrontier),
    depthfirst(NewFrontier).

breadthfirst([]) :- !.
breadthfirst([Node|Frontier]) :-
    format('~p ', [Node]),
    getchildren(Node, Children),
    append(Frontier, Children, NewFrontier),
    breadthfirst(NewFrontier).

This gives me:

?- depthfirst([a]).
a b e k f l m t c g h n i o p d j q r s 
true.

?- breadthfirst([a]).
a b c d e f g h i j k l m n o p q r s t 
true.

There’s unfortunately quite a lot in the above code to confuse a Prolog novice.

A key thing to note is the only difference between depthfirst and breadthfirst are the order in which the children list of the current node are appended to the yet to be explored nodes in the Frontier list.

Since we are not searching for a specific node in the tree, the recursion ends once all nodes have been explored (in an order dependent on the two search methods).

To get the children of the current node, I’ve used setof (+Template, +Goal, -Set), which is a little more convoluted than findall (+Template, :Goal, -Bag).

setof/3 returns a sorted list with duplicates removed, whereas findall/3 returns a list in the order that the X is_parent Y clauses were read. Another difference is setof/3 fails if you enter a terminal, say h, as in setof(Child, h is_parent Child, Children) whereas findall/3 would return an empty list. To get setof to return an empty list (which I want for the way I’ve written breadthfirst and depthfirst), I’ve created the second predicate getchildren(_, []) for when the first predicate getchildren(Parent, Children) fails.

More confusing yet, since I’m using a variable for Parent but am not returning it in setof’s :Goal, I need the caret ^ for setof/3 and bagof/3 but not for findall/3. (These are all things which seem easy once you get used to Prolog, but most of us find extremely bewildering at first).

[EricGT]

@joeblog

most of us find extremely bewildering at first

Not only is is extremely bewildering at first, but bewildering for a long time or until you get someone or something that explains it in a means that makes sense to you. The use of ^ drove me nuts for a long time and I can’t remember where I first read about it that cleared up the confusion, but if you find these things and they don’t make sense for a while don’t think that is just you.

[jan]

setof/3 is a great predicate and studying will improve your understanding of Prolog a lot. In many cases though, findall/3 is way easier to understand and a simple sort/2 turns the bag into a set. The moment you discover this is not doing what you want for some particular problem is probably the right moment to learn how setof/3 works and what the logical reasoning is that explains why it does what it does.

[Mathie]

All right, I get it. I didn’t know I could do that with the lists. Everything becomes clearer for me.

However, I do not understand this line you put before your predicates:

queue([],In_order,In_order).

And :

breadthfirst([]) :- !.

What is that ?

Thank you !

[EricGT]

When you reply if you want someone particular to look at something, you can tag them as such. That way we will be notified to come take a look. I was only notified of this because I have my options set to notify me of any post made for the Help! topic.

@EricGT

However, I do not understand this line you put before your predicates:

queue([],In_order,In_order).

@joeblog

However, I do not understand this line you put before your predicates:

breadthfirst([]) :- !.

[EricGT]

@Mathie

However, I do not understand this line you put before your predicates:

queue([],In_order,In_order).

The predicate queue/3 is a loop done using recursion.

queue([],In_order,In_order).
queue([Parent|Queue0],In_order0,In_order) :-
    append(In_order0,[Parent],In_order1),
    findall(Child,Parent is_parent Child,Children),
    append(Queue0,Children,Queue),
    queue(Queue,In_order1,In_order).

With recursion code in Prolog it is typically done with at least one clause for the recursion

queue([Parent|Queue0],In_order0,In_order) :-
    append(In_order0,[Parent],In_order1),
    findall(Child,Parent is_parent Child,Children),
    append(Queue0,Children,Queue),
    queue(Queue,In_order1,In_order).

and one clause to handle the base case

queue([],In_order,In_order).

The base case is saying that if there are no more nodes to process in the FIFO queue which is a list, and an empty list is represented as [], then take the value in the second argument and unify it with the third argument which will be a variable when called.

Then upon backtracking, the third argument of queue/3 will hold the in-order list and be passed back as the recursion is undo and finally to

start(Parent,In_order) :-
    queue([Parent],[],In_order).

where

queue([Parent],[],In_order).

will receive the In-order list and pass it back to

start(Parent,In_order)

which will pass it back to the top level and it will be printed.

Make sense?

If not try running it with the GUI tracer gtrace/0. e.g.

?- gtrace.
true.

[trace]  ?- start(a,In_order).

[Mathie]

That’s understood for me.

Thank you all for your quick and clear explanations. I have learned a lot and this has filled in my gaps regarding Prolog.

Very happy to see a community like this!

[joeblog]

@Mathie Prolog’s ways of handling different cases is very confusing at first.

To illustrate, I’ll translate the JavaScript switch example found at https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Statements/switch

The Prolog equivalent would look something like

fruit('Oranges') :- !,
    format("Oranges are $0.59 a pound.~n", []).

fruit(Fruit) :-
    member(Fruit, ['Mangoes', 'Papayas']), !,
    format("~w are $2.79 a pound.~n", [Fruit]).

fruit(Fruit) :-
   format("Sorry, we are out of ~w.~n", [Fruit]).

Edit As advised by @jan, I moved the cuts to immediately after the tests which check if Fruit matches that particularly case.

The exclamation mark ! (called cut in Prolog jargon) is akin to the break in the JavaScript example. If the first two predicates didn’t have the ! cut, ‘Oranges’ would match both the first and last predicate, and ‘Mangoes’ or ‘Papayas’ would match the second and third predicates. As does break, the ! tells the program not to continue trying to match further cases once one has succeeded, leaving the final uncut predicate as the default if none of the previous cases matched.

Back to my example:

@Mathie

breadthfirst() :- !.

The cut ! isn’t actually required in this case since the empty list wouldn’t match the next case depthfirst([Node|Frontier]) in any event. It is the recursive base case which calls the program to a halt by doing nothing (other than return true).

But telling it not to bother looking further if it has got to the end (empty list) might save an infinitismal amount of time and electricity.

[joeblog]

Here’s a slightly more polished version with no cuts or carets, and also returns the traversal path as a list (which is typically what you want). It doesn’t avoid cycles, but checking to see if a node has already been visited wouldn’t require much more work.

:- op(500,xfx,'is_parent').

a is_parent b.    c is_parent g.     f is_parent l.     j is_parent q.
a is_parent c.    c is_parent h.     f is_parent m.     j is_parent r.
a is_parent d.    c is_parent i.     h is_parent n.     j is_parent s.
b is_parent e.    d is_parent j.     i is_parent o.     m is_parent t.
b is_parent f.    e is_parent k.     i is_parent p.

getchildren(Parent, Children) :-
    findall(Child, Parent is_parent Child, Unsorted),
    sort(Unsorted, Children).

depthfirst([], []).
depthfirst([Node|Frontier], [Node|Visited]) :-
    getchildren(Node, Children),
    append(Children, Frontier, NewFrontier),
    depthfirst(NewFrontier, Visited).

breadthfirst([], []).
breadthfirst([Node|Frontier], [Node|Visited]) :-
    getchildren(Node, Children),
    append(Frontier, Children, NewFrontier),
    breadthfirst(NewFrontier, Visited).

?- depthfirst([a], Path), print(Path).
[a,b,e,k,f,l,m,t,c,g,h,n,i,o,p,d,j,q,r,s]
Path = [a, b, e, k, f, l, m, t, c|...].

?- breadthfirst([a], Path), print(Path).
[a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t]
Path = [a, b, c, d, e, f, g, h, i|...].

[jan]

@joeblog

fruit(Fruit) :-
    member(Fruit, ['Mangoes', 'Papayas']),
    format("~w are $2.79 a pound.~n", [Fruit]), !.

Some people do not like cuts at all (and there are good reasons for that). If you don’t mind about using cuts (which can also make sense), it is wise to consider a clause a a thing that consists of a guard and an action and put the cut between the two to tell not not to consider any other guard.

The guard in general consists of two parts: the clause head and additional conditions. In this case member/2 acts as guard and the cut should be immediately after the call to member/2.

A rule of thumb is that cuts should not be at the end of a clause, there is at most one cut in a clause and the last clause should not contain cuts. As with virtually any rule there are exceptions. Still, in either of the two cases it is a good idea to reconsider this is really what you want/need.

[joeblog]

Thanks @jan, I’ll edit my example to reflect these tips.