/* File:      shortest_path.P
** Author(s): David S. Warren
** Contact:   xsb-contact@cs.sunysb.edu
** 
** Copyright (C) The Research Foundation of SUNY, 1986, 1993-1998
** 
** XSB is free software; you can redistribute it and/or modify it under the
** terms of the GNU Library General Public License as published by the Free
** Software Foundation; either version 2 of the License, or (at your option)
** any later version.
** 
** XSB is distributed in the hope that it will be useful, but WITHOUT ANY
** WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
** FOR A PARTICULAR PURPOSE.  See the GNU Library General Public License for
** more details.
** 
** You should have received a copy of the GNU Library General Public License
** along with XSB; if not, write to the Free Software Foundation,
** Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
**
** $Id: shortest_path.P,v 1.2 2000/01/09 02:30:01 cbaoqiu Exp $
** 
*/


/* Experimentation with shortest path, using table builtins. */

:- import subsumes_chk/2 from subsumes.
:- import get_calls_for_table/2, get_returns_for_call/2 from tables.

:- table(sp/3).

demo :-
	sp(a,X,C),
	write('Best cost so far from a to '),write(X),write(' is '),writeln(C),fail.
demo.

sp(X,Y,C) :- 
	dist(X,Y,C),
	none_better(X,Y,C).
sp(X,Y,C) :-
	sp(X,Z,C1),
	none_better(X,Z,C1),
	dist(Z,Y,C2),
	C is C1+C2,
	none_better(X,Y,C).


none_better(X,Y,C) :-
	get_calls_for_table(sp(X,_,_),Call),
	subsumes_chk(Call,sp(X,Y,_)),
	!,
	\+ (	get_returns_for_call(Call,Ret),
		Ret = sp(X,Y,C1),
		C1 < C
	).

dist(a,d,2).
dist(a,b,5).
dist(a,c,3).
dist(c,b,1).
dist(b,e,3).
dist(b,d,4).
dist(e,d,2).
dist(d,b,1).