Depth First Search in Prolog

Question

subtrees([]). 
subtrees([(Cost,T)|Rest]) :−
   number(Cost),
   istree(T),
   subtrees(Rest).

istree(tree(_,Children)) :− subtrees(Children).

dfs(GoalValue,tree(GoalValue,_),GoalValue,0).
dfs(GoalValue,tree(Value,[(Cost,T)|Rest]),Path,FinalCost) :−
   T = tree(IV,_),
   write(IV ),
   dfs(GoalValue, T,P,C),
   string_concat(Value,P,Path),
   FinalCost is C+Cost
; % go down one depth level
   dfs(GoalValue,tree(Value,Rest),Path,FinalCost). % next child

Can someone help me understand this Prolog implementation of Depth First Search? A subpart of my question also includes how to interpret splitting within the Head part.

subtrees([(Cost,T)|Rest])

I am aware that each list is considered [Heads|Tails], but how does one interpret (Cost, T )? Is it a 2D list?

Where did you get this code? Why is there subtrees/1 and istree/1 when dfs/4 does not call them? If this is two separate questions then ask as two separate questions. Also these are most likely duplicates, did you search other questions? — Guy Coder, Feb 07 '22 at 14:42
@GuyCoder this was a part of the prolog programming section under my university's previous exams, subtree/1 and istree/1 implicit the program structure for students instead of a callable function for dfs/4. Yes, I did check for duplicates but wasn't lucky enough. — Pam Cesar, Feb 07 '22 at 15:38
This is depth-first because it goes down into T (depth) as far as it can go, firstly, before trying Rest (i.e. breadth). (Cost, T) I think is a tuple, i.e. a 2-argument term without a name. — brebs, Feb 07 '22 at 22:17
@brebs could you please elaborate it further?, I do understand the concept of dfs traversal in procedural programming, but can't understand the recursive flow of the same in this prolog code base. — Pam Cesar, Feb 08 '22 at 06:42
Where did the 2 comments come from, in the code? They seem to be confusing depth with breadth. Here's better examples: https://stackoverflow.com/questions/27065774/depth-first-search-algorithm-prolog and https://stackoverflow.com/questions/50766565/prolog-graph-depth-first-search — brebs, Feb 08 '22 at 19:15

score 0 · Answer 1 · answered Feb 13 '22 at 22:07

The builtin predicate write_canonical/1 is very useful for interpreting terms as it will remove syntactic sugar. So for your query:

?- write_canonical(subtrees([(Cost,T)|Rest])).
subtrees('.'(','(Cost, T), Rest)).

This means you have a subtrees/1 predicate that contains a list (a list without syntactic sugar is: '.'(Head, Tail)). The first element of that list is the term ','(Cost, T):

?- write_canonical((Cost, T)).
','(Cost, T)

This kind of ','/2 term is actually a Prolog conjunctive clause. It appears the author is abusing the homoiconic nature of Prolog here to mimic a tuple, which becomes inefficient for "tuples" with a length greater than 2 ((a, b, c) is actually ','(a, ',',(b, c)); better with an unnested term like f(a, b, c)), and so is best to avoid. The reading of (Cost, T) is "Cost and T".

Depth First Search in Prolog

1 Answers1