2

I have a knowledge base of this type:

connect(a, b).
connect(a, d).
connect(a, e).
connect(b, a).
connect(b, c).
...

My objective is, given an origin and a destiny, to go through all the existing nodes once, before reaching the final node.

So far this is what I have got:

path(O, D, L):-
    path(O, D, [O], L).

path(D, D, _, [D]).
path(O, D, A, [O|T]):-
    connect(O, I),
    \+ member(I, A),
    path(I, D, [I|A], T).

In order to deal with the double connections e.g. connect(a, b). connect(b, a). I use a list that saves every node I go through and before going into the recursion call I make sure that the node I am going to does not belong in that list.

Now I need to make sure that I go through all the existing nodes before reaching the final one. I have absolutely no idea how to even approach this. How can I ever be sure that I visited all the other nodes before reaching the last one?

false
  • 10,264
  • 13
  • 101
  • 209
João Paiva
  • 1,937
  • 3
  • 19
  • 41

2 Answers2

2

You can test it with your own code (not using findall), by making a small change. Instead of throwing away the list of visited nodes, keep it. So, change path/4 to path/5 as follows:

path(D, D, V, V, [D]).
path(O, D, A, V, [O|T]):-
    connect(O, I),
    \+ member(I, A),
    path(I, D, [I|A], V, T).

Now you can query path(a,c,[a], Visited, Path) and test if any connect node exists that is not a member of Visited.

RdR
  • 116
  • 3
1

You have defined a network as a list of edges. A quick-and-dirty way to collect all nodes would be, for example:

findall(X, ( connect(X, _) ; connect(_, X) ), Xs),
sort(Xs, Nodes)

This will first collect all "from"s and "to"s you have listed in your connect/2, then make a set out of it by sorting and removing duplicates.

At that point you can just compare this set to the path you found (after making a set out of it, too).

Obviously, it is important that your predicate fails there is no path that visits all nodes in the network defined by connect/2.

  • Thank you, that was a very clear explanation and it worked perfectly.Just one question. Why is this approach considered a "quick-and-dirty" way? – João Paiva Nov 21 '16 at 09:50
  • 1
    @JoãoPaiva Because using `findall/3` can be problematic in some situations. I think it is OK in this case, but I was too lazy to think about it carefully. –  Nov 21 '16 at 10:23
  • Oh, okay, I'll be careful when using it in the future then. – João Paiva Nov 21 '16 at 10:33
  • 1
    @JoãoPaiva Basically, you have to consider `findall/3` in comparison to `bagof/3` and `setof/3`. In almost all situations, it would be better to use `bagof/3` and `setof/3` because they allow you to leave some of the variables in the goal (the second argument) free, and enumerate the possible instantiations for these variables. You should definitely read about this elsewhere, a tutorial or a textbook. –  Nov 21 '16 at 11:06
  • Okay, I will study the difference between all 3. Thank you very much. – João Paiva Nov 21 '16 at 11:09