1

I'm new to prolog and want to limit recursion depth, but it keeps throwing "Arguments are not sufficiently instantiated" error. I'll generalise the problem to a graph.

edge(a,b).
edge(a,x).
edge(b,c).
edge(b,x).
edge(c,d).

So, there's a path from a to d: a-b-c-d It's pretty easy to check if there's a path between two vertices:

path(X,Y) :- edge(X,Y).
path(X,Y) :- edge(X,Z), path(Z,Y).

Now I want to limit the length of the path to N:

limitedPath(X,Y,N) :- edge(X,Y), N >= 0.
limitedPath(X,Y,N) :- edge(X,Z),limitedPath(Z,Y,M), N = M + 1, N>0.

limitedPath(a,b,2) is true, but limitedPath(a,c,1) throws "Arguments are not sufficiently instantiated", and I can't get the reason.

mat
  • 40,498
  • 3
  • 51
  • 78
Kate
  • 13
  • 2
  • 1
    See [this](https://stackoverflow.com/q/26946133/772868) for a general approach. That is: `closure(edge, A, B)` – false Dec 10 '17 at 00:56
  • `M` is not instantiated in the recursive call. If `N` is supposed to be a limit it makes more sense to subtract one, and before the call. – Tomas By Dec 10 '17 at 00:56
  • ah, a tutorial got me confused. – Kate Dec 10 '17 at 01:19
  • 2
    `N = M + 1` doesn't do what you think (unless you're using some funky version of Prolog like Visual, PDC, or Turbo Prolog). It attempts to unify the term in `N` with the term `+(M, 1)`. It does not evaluate `M + 1` and compare with `N`. You probably want `N is M + 1`. Or, as @false has in his answer, use CLP(FD), which is the preferred means of reasoning with integers in Prolog. – lurker Dec 10 '17 at 01:43
  • Yes, I got that. Thanks. – Kate Dec 10 '17 at 01:50
  • @mat: Note the tag – false Dec 12 '17 at 14:27

1 Answers1

3

To continue your idea:

:- use_module(library(clpfd)).

limitedPath(X,Y,N) :- N #>= 0, edge(X,Y).
limitedPath(X,Y,N) :- N #>= 0, N #= M+1, edge(X,Z), limitedPath(Z,Y,M).
false
  • 10,264
  • 13
  • 101
  • 209