From dmiles@teknowledge.com  Wed Dec 13 04:52:47 2000
Received: from helium.teknowledge.com (promethium.teknowledge.com [128.136.192.50])
	by swi.psy.uva.nl (8.9.3/8.9.3) with ESMTP id EAA15976
	for <prolog@swi.psy.uva.nl>; Wed, 13 Dec 2000 04:52:46 +0100 (MET)
Received: by helium.teknowledge.com with Internet Mail Service (5.5.2650.21)
	id <WM9NX4R7>; Tue, 12 Dec 2000 19:49:00 -0800
Message-ID: <EE25484266A64A47AE06CFC47C64232B1A1844@helium.teknowledge.com>
From: "Douglas R. Miles" <dmiles@teknowledge.com>
To: "'kevindunne@c4.com'" <kevindunne@c4.com>,
        "'prolog@swi.psy.uva.nl'"
	 <prolog@swi.psy.uva.nl>,
        "'Richard A. O'Keefe'" <ok@atlas.otago.ac.nz>
Subject: RE: 
Date: Tue, 12 Dec 2000 19:48:47 -0800
MIME-Version: 1.0
X-Mailer: Internet Mail Service (5.5.2650.21)
Content-Type: text/plain;
	charset="iso-8859-1"

Kevin,

My favorite prolog traceroute is implemented in Sicstus as ugraph or wgraph
in the library directories.

min_path(+V1, +V2, +Graph, -Path, -Cost) 
	Path is a shortest path of cost Cost from V1 to V2 in Graph. Takes
O(N^2) time. 
min_paths(+Vertex, +Graph, -Tree) 
	Tree is a tree of all the shortest paths from Vertex to every other
vertex in Graph. This is the single-source shortest paths problem. 
path(+Vertex, +Graph, -Path) 
	Given a Graph and a Vertex of Graph, returns a maximal Path rooted
at Vertex, enumerating more paths on backtracking. 


http://clwww.essex.ac.uk/manuals/sicstus-3.7/sicstus_26.html  It is easily
used in SWI.


% Douglas


-----Original Message-----
From: Richard A. O'Keefe [mailto:ok@atlas.otago.ac.nz]
Sent: Monday, December 11, 2000 3:03 PM
To: kevindunne@c4.com; prolog@swi.psy.uva.nl
Subject: Re:


"Kevin Dunne" <kevindunne@c4.com> wrote
that he is trying to write a public transport route finding 
program in Prolog.

	I have written up all my facts and rules about all these
	different things but I am having real trouble trying to write
	the code to input a source and a destination and to search
	through all of my data, to find the easiest way to get from
	source to destination using whatever transport available???
	Any ideas anybody
	
Open any good data structures and algorithms textbook (Cormen, 
Leiserson,
and Rivest is an *extremely* good one), turn to the index, and look up
"shortest path".  You will find several algorithms given, depending on
whether you want to find the shortest path for a given pair or for all
pairs.


----------------
* To UNSUBSCRIBE, please use the HTML form at

    http://www.swi.psy.uva.nl/projects/SWI-Prolog/index.html#mailinglist

or send mail to prolog-request@swi.psy.uva.nl using the 
Subject: "unsubscribe"
(without the quotes) and *no* message body.

** An ARCHIVE of this list is maintained at

    http://www.swi.psy.uva.nl/projects/SWI-Prolog/mailinglist/archive/

