breadth first on binary tree - using Semicontext notation

Question

I would like to compute list being bfs order on binary tree. Moreover, it should work in second side - for list it find tree.
Can you give me some hint, so far I have used something like that, of course it doesn't work...

bfs(nil) --> [].
bfs(t(X, L, R)), [X] --> bfs(L), bfs(R).

Have you tried doing a Google search for "Prolog BFS"? You'll get [quite a few hits](https://www.google.com/search?sourceid=chrome-psyapi2&ion=1&espv=2&ie=UTF-8&q=prolog%20bfs&oq=prolog%20bfs&aqs=chrome..69i57j0l4.5688j0j4). It's going to be more complicated than doing DFS. One approach is to use a queue, which is also used in other languages when developing a BFS method. There's also an interesting presentation in the search list that uses other techniques. — lurker, May 23 '16 at 18:53
Yes, I checked it. Nevertheless, keep in mind that my case is particular - it is **binary** tree. — , May 23 '16 at 18:59
I mean in the list of search results if you click my link. :) The fact that you're dealing with a *binary* tree doesn't change the BFS technique itself. It just changes some of the minor details of the traversal. In fact, it's probably just specialization of the methods shown. There are so many BFS links for prolog in the search I would think at least one of them might specifically do binary trees, but there must be something there that can get you most of the way there. — lurker, May 23 '16 at 19:40

repeat · Answer 1 · 2016-05-24T14:19:48.933

4

This is how you could do it using dcg (without semicontexts) and accumulators:

tree_bfss(T, Xs) :-
   phrase(bfs1([T]), Xs).

bfs1([]) --> [].                    % done if level is empty           
bfs1([X|Xs]) -->
   step_(X, [], Ts),                % single step
   bfs0_(Xs, Ts).                   % process items in this level

bfs0_([], Ts) -->               
   bfs1(Ts).                        % process next level
bfs0_([X|Xs], Ts0) -->
   step_(X, Ts0, Ts),               % single step
   bfs0_(Xs, Ts).                   % continue with this level

step_(nil, Ts, Ts) --> [].
step_(t(L,M,R), Ts, [R,L|Ts]) -->   % push R and L to the next level
   [M].                             % take care of M right now

Sample query using SICStus Prolog 4.3.2:

| ?- tree_bfss(t(t(nil,1,t(nil,2,nil)),3,t(nil,4,nil)), Xs).
Xs = [3,4,1,2] ? ;
no

How about going in the "other" direction?

| ?- tree_bfss(T, [3,4,1,2]).
T = t(t(t(t(nil,2,nil),1,nil),4,nil),3,nil) ? ;
T = t(t(t(nil,1,t(nil,2,nil)),4,nil),3,nil) ? ;
T = t(t(nil,4,t(t(nil,2,nil),1,nil)),3,nil) ? ;
T = t(t(nil,4,t(nil,1,t(nil,2,nil))),3,nil) ? ;
T = t(t(t(nil,2,nil),4,t(nil,1,nil)),3,nil) ? ;
T = t(nil,3,t(t(t(nil,2,nil),1,nil),4,nil)) ? ;
T = t(nil,3,t(t(nil,1,t(nil,2,nil)),4,nil)) ? ;
T = t(nil,3,t(nil,4,t(t(nil,2,nil),1,nil))) ? ;
T = t(nil,3,t(nil,4,t(nil,1,t(nil,2,nil)))) ? ;
T = t(nil,3,t(t(nil,2,nil),4,t(nil,1,nil))) ? ;
T = t(t(nil,1,nil),3,t(t(nil,2,nil),4,nil)) ? ;
T = t(t(nil,1,nil),3,t(nil,4,t(nil,2,nil))) ? ;
T = t(t(t(nil,2,nil),1,nil),3,t(nil,4,nil)) ? ;
T = t(t(nil,1,t(nil,2,nil)),3,t(nil,4,nil)) ? ;
no

Edit

Helpful comments have suggested clarification of the order of the list items:

Above code does not guarantee any particular order within each single tree level.
It does ensure that all items of the i^th level occur before all items of the (i+1)^th level.

(This has made the implementation slightly simpler.)

edited May 24 '16 at 14:19

answered May 24 '16 at 10:20

repeat

18,496
4
54
166

3

Argh, why is the value in the middle? :) – May 24 '16 at 12:31
2

@Boris. It felt more natural to me: (1) it resembles the graphical representation, (2) naming the arguments of `t/3` was (a bit) easier: `L`eft, `M`iddle, `R`ight, – repeat May 24 '16 at 13:09
1

@Boris. Is that conclusive? Or should I rather flip it to `t(M,L,R)` ? – repeat May 24 '16 at 13:09
3

I think it's more common to express the attributes of a binary tree node as "value, left, right". – lurker May 24 '16 at 13:28
2

Does your code really produce `[3,4,1,2]` for that tree? I think it should be `[3,1,4,2]` for a correct BFS traversal. Perhaps change `step_(t(L,M,R), Ts, [R,L|Ts])` to `step_(t(L,M,R), Ts, [L,R|Ts])`. :) – lurker May 24 '16 at 13:31
2

@lurker. It does. I think the order of items (within a level) is unspecified, not necessarily left to right... Initially, I had the order you are proposing. But the code got a little simpler (by using an accumulator instead of a second difference list). As an alternative, one could use `reverse/2` like so: `bfs0_([], Ts0) --> reverse(Ts0,Ts), bfs1(Ts).` but, then again, I don't think it is required. – repeat May 24 '16 at 13:43
1

I think BFS of a tree is traditionally left-then-right. I wouldn't think that would affect the structure of the code at all. Viewing the binary tree as a special form of graph, however, it probably wouldn't matter I suppose. – lurker May 24 '16 at 13:43
1

@lurker. The code structure would stay the same, but an additional argument (or a reverse/2 goal) would be needed... – repeat May 24 '16 at 13:45
1

@lurker. would you suggest I change it for sake of clarity? – repeat May 24 '16 at 13:46
2

By just swapping the `L` and `R` as I suggested seems to produce the results I'm referring to. I don't know if it's necessary to change it other than to point out what the intention is. I don't know if everyone else has the same mental paradigm of BFS for binary trees that I do. :) – lurker May 24 '16 at 13:48
1

@lurker. That does it for this very small tree. In the general case a list difference or an accumulator+reverse is required. – repeat May 24 '16 at 13:50
1

The value can be wherever you want it to be, it just caught me by surprise. It is a bit unconventional. See the comment by @lurker: it is not "left, middle, right", it is "node value, left subtree, right subtree". You see this exact order also in say `struct tnode { T value; struct tnode * left; struct tnode * right; };`. – May 24 '16 at 15:14
1

Thanks for adding the extra comments to the answer. It's made me think: a binary tree truly is just a specialized graph, so this algorithm meets all the requirements of a BFS search. Traditionally, in CS literature, binary tree branches are described left to right and often traversed that way in order to provide a canonical way to uniquely represent the tree in a list form. But as far as the act of traversing is concerned, the choosing an arbitrary of L versus R doesn't impact the algorithm's property of visiting each node exactly once and in true BFS fashion. – lurker May 24 '16 at 16:09
1

Another thought... It might be better to stick to a given, stated traversal convention. If it considers the left versus right ordering arbitrary, then that begs the question whether the solution should generate all such possible results (in either direction). – lurker May 24 '16 at 17:00

lurker · Accepted Answer · 2016-05-25T19:56:20.467

2

Looks like @repeat came up with a nice DCG solution. I had, in the meantime, come up with a "traditional" queue-based solution that is non-DCG:

bfs_tree_list(nil, []).
bfs_tree_list(Tree, List) :-
    bfs_q_list([Tree], List).

bfs_q_list([], []).
bfs_q_list([t(X,L,R)|Qs], [X|Xs]) :-
    enqueue(L, Qs, Q1),
    enqueue(R, Q1, Q2),
    bfs_q_list(Q2, Xs).

% "naive" enqueue using append
enqueue(nil, Q, Q).
enqueue(t(X,L,R), Q1, Q2) :- append(Q1, [t(X,L,R)], Q2).

This follows the methodology shown in the links I provided in my comments. It also follows a strict left-to-right traversal ordering which, I believe, is conventional in binary tree traversals. It's a little simpler than those in the links as those are for more general graphs rather than binary trees. The description of what's happening above is simple:

Start with the top level in the queue
For each element in the queue (until queue is empty)

The above code yields:

| ?- bfs_tree_list(t(3,t(1,nil,t(2,nil,nil)),t(4,nil,nil)), L).

L = [3,1,4,2]

(1 ms) yes

And:

| ?- bfs_tree_list(Tree, [3,1,4,2]).

Tree = t(3,nil,t(1,nil,t(4,nil,t(2,nil,nil)))) ? a

Tree = t(3,nil,t(1,nil,t(4,t(2,nil,nil),nil)))

Tree = t(3,nil,t(1,t(4,nil,t(2,nil,nil)),nil))

Tree = t(3,nil,t(1,t(4,t(2,nil,nil),nil),nil))

Tree = t(3,nil,t(1,t(4,nil,nil),t(2,nil,nil)))

Tree = t(3,t(1,nil,t(4,nil,t(2,nil,nil))),nil)

Tree = t(3,t(1,nil,t(4,t(2,nil,nil),nil)),nil)

Tree = t(3,t(1,t(4,nil,t(2,nil,nil)),nil),nil)

Tree = t(3,t(1,t(4,t(2,nil,nil),nil),nil),nil)

Tree = t(3,t(1,t(4,nil,nil),t(2,nil,nil)),nil)

Tree = t(3,t(1,nil,nil),t(4,nil,t(2,nil,nil)))

Tree = t(3,t(1,nil,nil),t(4,t(2,nil,nil),nil))

Tree = t(3,t(1,nil,t(2,nil,nil)),t(4,nil,nil))

Tree = t(3,t(1,t(2,nil,nil),nil),t(4,nil,nil))

(1 ms) no
| ?-

Here's a revised version that uses a difference list rather than append/3.

bfs_tree_list(nil, []).
bfs_tree_list(Tree, List) :-
    bfs_q_list([Tree|T], T, List).

bfs_q_list(Q, T, []) :- Q == T, !.
bfs_q_list([t(X,L,R)|Qs], T, [X|Xs]) :-
    [t(X,L,R)|Qs] \== T,
    enqueue(L, T1, T),
    enqueue(R, NewT, T1),
    bfs_q_list(Qs, NewT, Xs).

enqueue(nil, Q, Q).
enqueue(t(X,L,R), T, [t(X,L,R)|T]).

edited May 25 '16 at 19:56

answered May 24 '16 at 13:11

lurker

56,987
9
69
103

Could you show me how to realize enqueue with open/difference lists ? – May 24 '16 at 23:34
1

@HaskellFun I added that version to my answer. – lurker May 25 '16 at 14:29
Thanks you very much! – May 25 '16 at 15:57
What about useless choicepoints left open by `bfs_q_tree//2`? – repeat May 25 '16 at 18:47
@repeat yeah my next step on this is try to eliminate that. – lurker May 25 '16 at 18:50
Enjoy;) Take care that the code still runs in both ways (tree -> list and back). – repeat May 25 '16 at 18:53
1

@repeat indeed! I thought I was doing good getting it as far as it is. ;) I find that proper removal of a useless choice point is not so easy. – lurker May 25 '16 at 19:18
IMO the key is *restraint*. I tried to elaborate on how indexing can be used to that end (http://stackoverflow.com/a/37353796/4609915). I can recommend the SICStus doc section on "determinacy detection": https://sicstus.sics.se/sicstus/docs/latest4/html/sicstus.html/Determinacy-Detection.html – repeat May 26 '16 at 09:03
@repeat thanks a lot for the links. I shall review those. In the meantime, I did some tracing to determine where choice points were occurring, etc, and came up with a solution and modified my answer accordingly. – lurker May 26 '16 at 12:34
Those useless choicepoints are gone, but I *do* find the code harder to understand... Also, `bfs_tree_list(nil,[])` still leaves a useless choicepoint. – repeat May 26 '16 at 13:16
Should I add my non-accumulator version as a separate answer? – repeat May 26 '16 at 13:17
@repeat yes, there's a little extra complexity is an artifact of managing the difference list. The elimination of the choice point was done by explicitly checking whether the current queue and the difference tail were the same. Whether it's a separate answer or an addendum to your current answer depends (IMO) on how much of a departure it is from the structure of your current answer. I kept mine together because both were using what I considered to be a "standard" BFS queue method. (Although by the time I tweaked it, I may have thought differently.) – lurker May 26 '16 at 13:22
I think so, too. Structurally, there's next to no difference: accu vs dcg, that's all. – repeat May 26 '16 at 13:29
Here's how you could get rid of the useless choicepoint left behind by `?- bfs_tree_list(nil,[]).`: Define `bfs_tree_list/2` like this: `bfs_tree_list(Tree,List) :- if_(Tree = nil, List = [], bfs_q_list([Tree|T], T, List)).` :) – repeat May 26 '16 at 13:41
1

@repeat thanks for that suggestion. I was thinking something in those terms. :) – lurker May 26 '16 at 13:52
@repeat it seems like [`if_/3`, `=/3`, etc](http://stackoverflow.com/questions/27358456/prolog-union-for-a-u-b-u-c/27358600#27358600) should become part of the ISO standard. It's getting to be a pain having to hunt their implementations down in SO posts. :) – lurker May 26 '16 at 14:01
For the time being use `library(reif)`, available for SWI http://www.complang.tuwien.ac.at/ulrich/Prolog-inedit/swi/reif.pl and for SICStus http://www.complang.tuwien.ac.at/ulrich/Prolog-inedit/sicstus/reif.pl ! – repeat May 26 '16 at 14:56

breadth first on binary tree - using Semicontext notation

2 Answers2

Edit