search all paths and the shortest path for a graph - Prolog

Posted by prologian on Stack Overflow See other posts from Stack Overflow or by prologian
Published on 2010-04-01T22:22:06Z Indexed on 2010/04/01 22:23 UTC
Read the original article Hit count: 811

Filed under:
|

Hi , I have a problem in my code with turbo prolog wich search all paths and the shortest path for a graph between 2 nodes the problem that i have is to test if the node is on the list or not exactly in the clause of member and this is my code :

/*



           1    ---- b ----   3
           ---       |        ---
        ---          |             -----
      a              |5                  d
        ---          |             -----
            ---      |         ---
             2  ---  |     ---   4
                  -- c  --

for example we have for b--->c 
([b,c],5) , ([b,a,c],3) and ([b,d,c],7) : possible paths.
([b,a,c],3) : the shortest path.                                                        

*/

DOMAINS
list=Symbol *
PREDICATES


distance(Symbol,Symbol)
    path1(Symbol,Symbol,list,integer)
    path(Symbol,Symbol,list,list,integer)
    distance(Symbol,list,integer)
    member(Symbol,list)
    shortest(Symbol,Symbol,list,integer)

CLAUSES 
    distance(a,b,1).
    distance(a,c,2).
    distance(b,d,3).
    distance(c,d,4).
    distance(b,c,5).
    distance(b,a,1).
    distance(c,a,2).
    distance(d,b,3).
    distance(d,c,4).
    distance(c,b,5).

member(X, [Y|T]) :- X = Y; member(X, T).

absent(X,L) :-member(X, L),!,fail.
    absent(_,_).

/*find all paths*/
path1(X, Y, L, C):- path(X, Y, L, I, C).
path(X, X, [X], I, C) :- absent(X, I).
path(X, Y, [X|R], I, C) :- distance(X, Z, A) , absent(Z, I), 
   path(Z, Y, R, [X|I] ,C1) , C=C1+A .

/*to find the shortest path*/
shortest(X, Y, L, C):-path(X, Y, L, C),path(X, Y, L1, C1),C<C1.

© Stack Overflow or respective owner

Related posts about prolog

Related posts about graph