DAG Traversal + Cost in Prolog

Question

I'm trying to implement a DAG traversal algorithm that also gets the costs between the edges. I think I'm pretty close but queries always return paths that aren't valid. Can anyone take a look and see what I'm missing here?

edge(b, a, 5).
edge(a, u, 10).
edge(u, o, 140).
edge(u, r, 130).
edge(r, o, 20).
edge(r, v, 50).
edge(o, v, 45).
edge(b, v, 20).

path(Start, Start, [], 0).
path(Start, Finish, [Start, Finish], C) :-
    edge(Start, Finish, Cost),
    C is Cost.
path(Start, Finish, [Start|Path], C) :-
    edge(Start, X, Cost),
    path(X, Finish, Path, RCost),
    C is Cost + RCost.

I'm trying to run path(b, v, S, C).. It is generating all the valid paths, but it's also generating a few invalid paths.

C = 20,
S = [b, v]
C = 200,
S = [b, a, u, o, v]
C = 200,
S = [b, a, u, o]
C = 195,
S = [b, a, u, r, v]
C = 210,
S = [b, a, u, r, o, v]
C = 210,
S = [b, a, u, r, o]
C = 195,
S = [b, a, u, r]
C = 20,
S = [b]

Thanks.

user27815 · Answer 1 · 2018-06-09T05:40:44.497

The best graph traversal code I have seen is in this question: Definition of a path/trail/walk

We can adapt that for your case to be:

edge(b, a, 5).
edge(a, u, 10).
edge(u, o, 140).
edge(u, r, 130).
edge(r, o, 20).
edge(r, v, 50).
edge(o, v, 45).
edge(b, v, 20).


:- meta_predicate path(3,?,?,?).

:- meta_predicate path(3,?,?,?,+).

path(R_3, [X0|Ys], X0,X) :-
   path(R_3, Ys, X0,X, [X0]).

path(_R_3, [], X-0,X-0, _).
path(R_3, [X1-Cost2|Ys], X0-Cost,X, Xs) :-
   call(R_3, X0,X1,Cost),
   non_member(X1, Xs),
   path(R_3, Ys, X1-Cost2,X, [X1-Cost2|Xs]).

non_member(_E, []).
non_member(E, [X-_Cost|Xs]) :-
   dif(E,X),
   non_member(E, Xs).

Then we can query :

?- path(edge,Path,From,To).
Path = [_22918-0],
From = To, To = _22918-0 ;
Path = [b-5, a-0],
From = b-5,
To = a-0 ;
Path = [b-5, a-10, u-0],
From = b-5,
To = u-0 ;
Path = [b-5, a-10, u-140, o-0],
From = b-5,
To = o-0 ;
Path = [b-5, a-10, u-140, o-45, v-0],
From = b-5,
To = v-0 ;

etc

So we get a list of nodes with the cost to get to the next node. You can then simply sum them like this:

?- path(edge,Path,From,To), pairs_values(Path,Values), sumlist(Values,Sum).
Path = [_24478-0],
From = To, To = _24478-0,
Values = [0],
Sum = 0 ;
Path = [b-5, a-0],
From = b-5,
To = a-0,
Values = [5, 0],
Sum = 5 ;
Path = [b-5, a-10, u-0],
From = b-5,
To = u-0,
Values = [5, 10, 0],
Sum = 15 ;
Path = [b-5, a-10, u-140, o-0],
From = b-5,
To = o-0,
Values = [5, 10, 140, 0],
Sum = 155

etc

or you could adapt the code to count the sum as you go saving sum computation.

In this I think we are assuming that there is only one edge from any one node to another.

Will Ness · Answer 2 · 2018-06-05T05:56:10.363

You have one error in your code. This:

path(Start, Start, [], 0).

should have been

path(Start, Start, [Start], 0).

otherwise Path in

path(Start, Finish, [Start|Path], C) :-
    edge(Start, X, Cost),
    path(X, Finish, Path, RCost),
    C is Cost + RCost.

comes back empty from that (first) clause, but what you really intended here is for it to contain Finish as the last element.

Indeed this follows from the logical reading of your predicate as well. If path(Start, Start, Path, Cost) is to succeed, it means there's a Path from Start to Start, which is the non-empty [Start]. An empty path is no path at all.

Now all reported paths are valid. Some are reported multiple times, but that's another issue.

DAG Traversal + Cost in Prolog

2 Answers2