Search code examples
prologbacktracking

Prolog Bactracking

I've been trying to write a prolog program and I'm having problems with its bactracking, it makes no sense to me. Here's one of my clauses that I'm having troubles with:

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


spider(Grafo, AristasArana) :-
  findall(edge(Grafo,X,Y),edge(Grafo,X,Y),AristasTotales),
  member(edge(Grafo,X1,Y1),AristasTotales),
  zpider(edge(Grafo,X1,Y1),AristasTotales,AristasArana),
  length(AristasArana,L),
  L > 2.

zpider(edge(Grafo,X1,Y1),AristasTotales,AristasArana) :-
  member(edge(Grafo,A1,A2), AristasTotales),
  X1 \= A1,
  Y1 = A2,
  findall(edge(Grafo,X,Y),(Y = A2),ListaAux1),
  findall(edge(Grafo,X,Y),(X = A2),ListaAux2),
  % Pueden haber repetidos y no se eliminan.
  append(ListaAux2,ListaAux1,AristasArana).

zpider(edge(Grafo,X1,Y1),AristasTotales,AristasArana) :-
  member(edge(Grafo,A1,A2), AristasTotales),
  X1 \= A1,
  Y1 = A1,
  findall(edge(Grafo,X,Y),(Y = A1),ListaAux1),
  findall(edge(Grafo,X,Y),(X = A1),ListaAux2),
  % Pueden haber repetidos y no se eliminan.
  append(ListaAux2,ListaAux1,AristasArana).

zpider(edge(Grafo,X1,Y1),AristasTotales,AristasArana) :-
  member(edge(Grafo,A1,A2), AristasTotales),
  X1 = A1,
  Y1 \= A2,
  findall(edge(Grafo,X,Y),(Y = A1),ListaAux1),
  findall(edge(Grafo,X,Y),(X = A1),ListaAux2),
  % Pueden haber repetidos y no se eliminan.
  append(ListaAux2,ListaAux1,AristasArana).

zpider(edge(Grafo,X1,Y1),AristasTotales,AristasArana) :-
  member(edge(Grafo,A1,A2), AristasTotales),
  X1 = A2,
  Y1 \= A2,
  findall(edge(Grafo,X,Y),(Y = A2),ListaAux1),
  findall(edge(Grafo,X,Y),(X = A2),ListaAux2),
  % Pueden haber repetidos y no se eliminan.
  append(ListaAux2,ListaAux1,AristasArana).

The whole program does not unify when it should, so I tried to trace. it on gprolog and here's the first problem I found:

 5    3  Exit: member(edge(g1,a,b),[edge(g1,a,b),edge(g1,b,c),edge(g1,a,c),edge(g1,d,a),edge(g1,d,b),edge(g1,d,c)]) ? 
      6    3  Call: a\=a ? 
      7    4  Call: a=a ? 
      7    4  Exit: a=a ? 
      6    3  Fail: a\=a ? 
      5    3  Redo: member(edge(g1,a,b),[edge(g1,a,b),edge(g1,b,c),edge(g1,a,c),edge(g1,d,a),edge(g1,d,b),edge(g1,d,c)]) ? 
      5    3  Exit: member(edge(g1,b,c),[edge(g1,a,b),edge(g1,b,c),edge(g1,a,c),edge(g1,d,a),edge(g1,d,b),edge(g1,d,c)]) ? 
      6    3  Call: a\=b ? 
      7    4  Call: a=b ? 
      7    4  Fail: a=b ? 
      6    3  Exit: a\=b ? 
      5    3  Redo: member(edge(g1,b,c),[edge(g1,a,b),edge(g1,b,c),edge(g1,a,c),edge(g1,d,a),edge(g1,d,b),edge(g1,d,c)]) ?

For some reason, after it triumphs here 6 3 Exit: a\=b ? it would redo the previous clause until it fails and I do not understand why.

Edit: The idea is for the program to unify if there is a node which has 3 or more edges attached to it (does not matter if those edges comes from or to that node). Note that it is possible to unify more than once, if more than one node has three or more edges attached to it. Edges, as you can see, are given as facts.

Solution

  • First off, you make heavy use of this "idiom": findall(Foo,Foo,T), member(Foo,T). You would have been better off just doing Foo. You're materializing the knowledge store into a list variable, presumably because it's more familiar to you and you assume it will be easier to work with, but it doesn't really buy you anything. It's pushing your food around on your plate. Especially because you don't then do anything better with T that might justify the work, like using select/3 to constrain your search.

    Second, you have four clauses for zpider/3. Why? You're doing some kind of strange breakdown of cases where the first node and subsequent nodes match or don't match on the first or second argument. I think you're unclear on the fact that each of these clauses will be executed once, and then backtracked into. You're not getting the benefit of all four of these running sequentially. Each one of them represents an alternate solution. That's why you have backtracking you don't expect!

    I conclude your code is pretty wide of the mark. Part of the problem you're having, though, is that your graph's nodes are all solutions, so it'll be hard to debug. Let's make a more interesting graph. I came up with this, in graphviz syntax:

    graph g {
    a -- c;
    b -- c;  b -- e;
    c -- d;  c -- e;
    d -- e;
}

    graph

    I'm highlighting two of the nodes in green to signify that they meet your criterion (three edges); the rest do not, so if we succeed we should just see c and e as the nodes we get back.

    Let's try doing this inefficiently, just for fun. We need three links, so let's go get them specifically.

    uedge(Graph, X, Y) :- edge(Graph, X, Y).
uedge(Graph, X, Y) :- edge(Graph, Y, X).

thrice_connected(Graph, Node) :-
    uedge(Graph, Node, A),
    uedge(Graph, Node, B),
    uedge(Graph, Node, C),
    A \== B, B \== C, A \== C.

    For starters, I define uedge/3 which gives us undirected graph edges, and I've defined thrice_connected/2 which uses that to find three connections to this node that are different. You can see that it works, albeit inefficiently, by running it, but you'll get a lot of duplicated values because A, B and C get permuted every which way. So, what I've done here works, but it's not really all that efficient. It's inefficient because every time it fails, it resumes the last uedge/3 search over again, until it has done all three of them. This is bad with three and it would only get worse with more!

    To do this more efficiently, you have to realize that you need a unique list of nodes. In your code, you go to some effort to make a list of edge/3 structures for your fact database. You don't need to recreate the structure you have, you can create something a little more useful by using setof/3, which incidentally buys you uniqueness right off the bat:

    ?- setof(Adjacent, uedge(g, Node, Adjacent), AdjacentNodes).
Node = a,
AdjacentNodes = [c] ;
Node = b,
AdjacentNodes = [c, e] ;
Node = c,
AdjacentNodes = [a, b, d, e] ;
Node = d,
AdjacentNodes = [c, e] ;
Node = e,
AdjacentNodes = [b, c, d].

    Look at that, it's so close to the solution it practically hurts. That one second-order query says "give me the set of Adjacent nodes, defined as edges in g from Node to Adjacent." Because we didn't specify Node, Prolog will generate them, and we get one solution for each node in the graph. Perfect! From here the solution is almost trivial:

    thrice_connected(Graph, Node) :-
    setof(Adjacent, uedge(Graph, Node, Adjacent), AdjacentNodes),
    length(AdjacentNodes, Len),
    Len >= 3.

    We're really just taking the previous query, generalizing it a little and making it perform the >= 3 test.

    ?- thrice_connected(Graph, Node).
Graph = g,
Node = c ;
Graph = g,
Node = e.

    And it works!