2

In Prolog, how can I implement graph algorithm in order to find all path in order to implement travel salesman problem in directed graph ?

example : 

                                                                         graph
                    expected input     expected output                 X -----> Y
    start X             X  Y               X Z                         Y -----> T
    end   Z             Y  T               X Y Z                       T -----> Z
                        T  Z               X Y T Z                     Y -----> Z
                        Y  Z                                           X -----> Z
                        X  Z

As you know, in directed graph, there could be a cycle. However, no need to pass same point two times. 

             graph             expected output             
           X ----> Y            
           Y ----> X               X Y Z
           Y ----> Z

Why I am elimineting this case is because ;

      output :

      X Y X Y ...   Z
              ^^^
              god knows this length ( when program terminates )
              termination is np problem
Guy Coder
  • 24,501
  • 8
  • 71
  • 136
user1423470
  • 77
  • 2
  • 6

2 Answers2

2

Keep a list of nodes you have already visited. In each step, check if the endpoint of the edge exists in the list or not.

Sufian Latif
  • 13,086
  • 3
  • 33
  • 70
2

I placed some comment that explain what the code does...

% your directed graph
edge(x, y).
edge(y, t).
edge(t, z).
edge(y, z).
edge(x, z).

% get a path from start to end
path(Start, End, Path) :-
    path(Start, End, [Start], Path).

% when target reached, reverse the visited list
path(End, End, RPath, Path) :-
    reverse(RPath, Path).

% take non deterministically an edge, check if already visited before use
path(Start, End, Visited, Path) :-
    edge(Start, Next),
    \+ memberchk(Next, Visited),
    path(Next, End, [Next|Visited], Path).

test:

?- path(x,z,P).
P = [x, y, t, z] ;
P = [x, y, z] ;
P = [x, z] ;
false.
CapelliC
  • 59,646
  • 5
  • 47
  • 90
  • When I use your code, I only get the first path as an output and it's not terminated. Looks like an infinite loop. Do you have any idea what I'm missing? – Dave Chandler Feb 22 '22 at 14:49
  • @DaveChandler: sorry, don't know. My code is as simple as it could be... do you mind to post the code you're trying ? – CapelliC Feb 22 '22 at 15:05
  • @DaveChandler: could you check that **all** your edge/2 facts are ground ? That is, no variables there... – CapelliC Feb 22 '22 at 16:11