Cut at the end of a Prolog statement

Question

I have encountered this cut which should return true if there exists an edge A-B or B-A for some node B of graph Graph.

node(A,Graph) :- adjacent(A,_,Graph),!.

The problem is I do not understand why removing this cut would have any effects on the returned solutions.

As I understand it the only use for a cut at the end of a Prolog statement is when there is another statement with the same name [another node(...)] which we don't want to be called if the first one succeedes. An example would be a function that takes X and Y and returns the larger one as the third parameter.

max1(X, Y, X) :- X > Y, !.
max1(_X, Y, Y).

However, there is no other statement called node(...) so I can't see how the cut could affect the solutions.

This is my code. It should find a spanning tree. It is explained in detail here. The compiler is SWI-Prolog 7.6.4 on linux.

:- op(900, fy, not).

stree1( Graph, Tree)  :-
    subset( Graph, Tree),  tree( Tree),  covers( Tree, Graph).

tree( Tree)  :-
    connected( Tree),  not hasacycle( Tree).

connected( Graph)  :-
    not ( node( A, Graph), node( B, Graph), not path( A, B, Graph, _) ).

hasacycle( Graph)  :-
     adjacent( Node1, Node2, Graph),
     path( Node1, Node2, Graph, [Node1, X, Y | _] ). 

covers( Tree, Graph)  :-
    not ( node( Node, Graph), not node( Node, Tree) ).

subset( [], [] ). 
subset( [X | Set], Subset)  :-  subset( Set, Subset).
subset( [X | Set], [X | Subset])  :-  subset( Set, Subset).

adjacent( Node1, Node2, Graph)  :-
      member( Node1-Node2, Graph)
      ;
      member( Node2-Node1, Graph).

node( Node, Graph)  :-  adjacent( Node, _, Graph). 

path( A, Z, Graph, Path)  :-
      path1( A, [Z], Graph, Path).

path1( A, [A | Path1], _, [A | Path1] ).

path1( A, [Y | Path1], Graph, Path)  :-
      adjacent( X, Y, Graph),
      not member( X, Path1), 
      path1( A, [X, Y | Path1], Graph, Path).

Solutions returned without cut (correct)

?- stree1([a-b, b-c, b-d, c-d], Tree).
Tree = [a-b, b-d, c-d] ;
Tree = [a-b, b-c, c-d] ;
Tree = [a-b, b-c, b-d] ;
false.

Solutions returned with cut (incorrect)

?- stree1([a-b, b-c, b-d, c-d], Tree).
Tree = [a-b] ;
Tree = [a-b, c-d] ;
Tree = [a-b, b-d] ;
Tree = [a-b, b-d, c-d] ;
Tree = [a-b, b-c] ;
Tree = [a-b, b-c, c-d] ;
Tree = [a-b, b-c, b-d] ;
false.

Koralp Catalsakal Koralp Catalsakal · Accepted Answer · 2019-01-20T18:38:16

"As I understand it the only use for a cut at the end of a Prolog statement is when there is another statement with the same name [another node(...)] which we don't want to be called if the first one succeedes."

Well, this is not true for your condition since you are using member/2 predicate which will work with backtracking. In that situation, using cuts will prune the solution tree that Prolog uses in backtracking and can cause a change in the results you get. To explain with an example see the slightly modified code of your original post here:

node( Node, Graph , Target)  :-  adjacent( Node, Target, Graph),!.

adjacent( Node1, Node2, Graph)  :-
  member( Node1-Node2, Graph)
  ;
  member( Node2-Node1, Graph).

When you run this query in the console, you will see the output :

?- node(l,[l-x,l-y],Target).
Target = x

Why? Because in the beginning, there are two leaves of your search tree. Either the pair (l-x) or (l-y) satisfies the condition in adjacent/3. Then, according to the depth-first search, the pair (l-x) gets selected, and since you have a ! statement in your code, the rest of the search tree is now pruned. Hence, you get the result as Target = x

However, if you remove the ! statement from the code, what you will see is:

?- node(l,[l-x,l-y],Target).
Target = x ;
Target = y ;
false.

Here, you see that both leaves of the search tree are executed sequentially, according to the depth-first order, and you see two results. This is what causes you to see different results when the ! is existent or not.

Cut at the end of a Prolog statement

1 Answers