CODEWITHSUNDEEP
prologincrementbacktracking
Steve
Steve

Reputation: 23

increment and backtracking in prolog

My purpose is to count the number of nodes between two nodes in Prolog. For example, in this example there is one node (node2) between node1 and node3:

link(node1,node2).
link(node2,node3).

Because we can't change the state of a variable already instantiated in Prolog, my first intuition was to try something with recursion like this to count:

nb_nodes_netween(N1,N2,R) :-
    link(N1,N2).
nb_nodes_netween(N1,N2,R) :-
    link(N1,A),
    T is R+1,
    nb_nodes_netween(A,N2,T).

My problem concerns the counter.. Thank you

EDIT New version with R variable as OUT value (the final Result) and T variable as IN value (a kind of accumulator).

R = R + 1 but I have no idea how to translate this in Prolog. Maybe can I store the nodes in a list and T is the length of the list. 

nb_nodes_between(N1,N2,R) :-
    link(N1,N2).
nb_nodes_between(N1,N2,R) :-
    link(N1,A),
    R is T+1,% TODO 
    nb_nodes_netween(A,N2,R).

Upvotes: 0

Views: 178

Answers (1)

damianodamiano
damianodamiano

Reputation: 2662

So, the solution is quite simple:

nb_nodes_between(N1,N2,R,R) :-
    link(N1,N2).
nb_nodes_between(N1,N2,T,O) :-
    link(N1,A),
    R is T+1,% TODO 
    nb_nodes_between(A,N2,R,O).

?- nb_nodes_between(node1,node3,0,O).
O = 1
false

I want to point out a thing: suppose you have this knowledge base to represent the graph:

link(node1,node2).
link(node2,node3).
link(node3,node4).
link(node4,node2).

Try the query:

?- b_nodes_between(node1,node2,0,O).
O = 0
O = 3
O = 6
O = 9
O = 12
O = 15
and so on...

Whit this solution, if there is a loop in the graph, the programm will loop as well. To avoid looping and get ONLY one path, you have to add a cut ! in your code, like this:

nb_nodes_between(N1,N2,R,R) :-
    link(N1,N2),!. %<-- note the cut !

?- nb_nodes_between(node1,node2,0,O).
O = 0

Upvotes: 1

Related Questions