1

I am trying to create a rule that recursively calls itself, and finds all possible paths to traverse a directed graph. I am using a findall() to do so. The functions is traverse(Start,End).

I have:

traverse(Start,End,[li]) :-
   node(Start,End),
   append(End,Li).

traverse(Start,End,[Li]) :-
   node(Start,Z),
   traverse(Z,End),
   append(Start,Li).

/*here I would like to check that Z is not a member of Li before
  I call traverse(Z,End), I know I can check that it is a member
  using member(Z,Li) but how to I check it is not a member in 
  prolog*/

findalltraverses(Start,End,[list]) :-
   findall(_,traverse(Start,End).
DuDa
  • 3,718
  • 4
  • 16
  • 36
needhelpfasr
  • 13
  • 2
  • 1
    See [this](https://stackoverflow.com/q/26946133/772868) and [that](https://stackoverflow.com/q/30328433/772868). – false Feb 07 '21 at 08:24

1 Answers1

0

Before we start: this language is called prolog.

Your code has several mistakes/errors in different levels. Here is a (not complete) list of them:

  • The findall needs a closing bracket.
  • findall needs 3 parameters. At first position is what you are interested in, second is how to optain the data (which call) and third one is a container for your answers. You are interested in the container, so findalltraverses should have it as attribute.
  • There is a difference between a node and an edge. An edge connects two nodes.
  • Variables start with a capital letter or an underscore.
  • If a variable L is unified with a list you don't have to state it like [L], because for the example L=[1,2,3] [L] would become [[1,2,3]] which is a list containing a list which contains 1, 2 and 3.
  • For a recursive call you often have two cases: an end setting and a recursive call setting. You got this concept right.
  • append has 3 arguments: the lists L1, L2 and L3, where L1 and L2 appended is L3.
  • Your predicate traverse/3 has 3 attributes. There is no predicate traverse/2 defined for 2 attributes.
  • You can not overwrite variables. Once a value for a variable is set, you can not change it anymore. For example: if you have a number N and want to increment it, you need to use a different variable to hold the result: N1 is N+1.
  • Appending single elements E to a list L as head elements (meaning to put it at first position) can be done with the head-tails writing: [E|L]. For E=1 and L=[2,3], [E|L] becomes [1,2,3].
  • To avoid endless loops you need to track the nodes you have already visited. However if you are interested in a path from Start to End you somehow need to forward the path somehow. It is not possible to use the list with visited nodes only since this knowledge is not preserved when stepping back through the recursion. So your traverse predicate should have had 4 attributes.
  • The "not" can be expressed with \+ which means as much as "cannot be proven".

Ok, here is a working code snipped. The recursion end part is a bit different because it does not check if there is a edge from Start to End but asks if Start and End are the same. If so then the resulting path contains only this node. This is important because in the code snipped the path will be build when going back trough the recursion ([Start|Path]) while the list containing visited nodes grows when going into the recursion ([Start|Visited]).

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

traverse(End,End,_,[End]).
traverse(Start,End,Visited,[Start|Path]) :-
    edge(Start,Tmp),
    \+ member(Tmp,Visited),
    traverse(Tmp,End,[Start|Visited],Path).

findalltraverses(Start,End,Out):-
   findall(List,traverse(Start,End,[],List),Out).

Let's test it!

?- findalltraverses(a,d,Out).
Out = [[a, b, c, d], [a, d]].

Looks good.

DuDa
  • 3,718
  • 4
  • 16
  • 36