From att!surya.ho.att.com!ko Fri Mar 22 10:31:23 1991
Received: from Princeton.EDU (Princeton.EDU.) by fs.Princeton.EDU (4.0/1.105)
id AA21961; Fri, 22 Mar 91 10:31:21 EST
Received: from att.UUCP by Princeton.EDU (5.61++/2.69/princeton)
id AA18354; Fri, 22 Mar 91 10:31:17 -0500
Received: from spark.ho.att.com by surya.ho.att.com (4.1/SMI-4.1)
id AA09832; Thu, 21 Mar 91 17:27:35 EST
Date: Thu, 21 Mar 91 17:27:35 EST
From: surya.ho.att.com!ko
Message-Id: <9103212227.AA09832@surya.ho.att.com>
Received: by spark.ho.att.com (4.1/SMI-4.1)
id AA06596; Thu, 21 Mar 91 17:35:07 EST
To: att!att.uucp, nr@Princeton.EDU
Subject: Example file
Status: RO
Here is an example Turing Web file. Note: I have made a small
modification to "webkernel.tex" by adding \date and \author macros.
These are used in the file that follows. I include the modification
below:
\def\rhead{\.{WEB} OUTPUT} % this running head is reset by starred sections
\def\title{} % an optional title can be set by the user
% The following two are optional, and can be set by the user.
% (Kostas Oikonomou, Nov. 1990.)
\def\author{}
\def\date{}
\def\topofcontents{\centerline{\titlefont\title}\vskip1cm\centerline{\author}
\vskip0.4cm\centerline{\date}\vfill} % this material will start the table of contents page
\def\botofcontents{\vfill} % this material will end the table of contents page
----------------------------- paths.web ----------------------------------------
\def \title {General Least-Cost Paths in Graphs}
\def \author {Kostas N. Oikonomou}
\def \date {August 1990}
% See the TeXbook, p.154 for this!
\font \bbb = msbm10
\newfam\msbmfam
\textfont\msbmfam=\bbb
\def \Nat {{\fam\msbmfam N}}
\def \Real {{\fam\msbfam R}}
\def \c#1{\vert#1\vert}
@* The {\it paths\/} module.
Let $G$ be a complete directed graph on $V=\{0,1,\ldots,n\}$. The edges
are $E=\{(i,j)\mid i =
@t\% The ``include'' allows {\tt paths.ch} to be used unchanged by different parent modules:@>
include "paths.parent"
stub module paths
import (n, m)
export (least_cost, least_cost_path)
procedure least_cost (var c_star : array 1 .. * of real, function l(i,j : nat) : real, @| function f(c1,c2 : real) : real, function relation (c1,c2 : real) : boolean)
procedure least_cost_path (k : nat, var I : array 0 .. * of nat)
end paths
@ To find the paths and their costs, define
$$
c_k(i) = \min_{j:i =
for i : 0 .. n-2
c_k(i) := infinity
for j : i+1 .. n-1
const c := f(l(i,j), c_k_1(j))
if c < c_k(i) then
c_k(i) := c
J(k,i) := j
end if
end for
end for
@
@ =
const infinity := 10.0 ** 200
for k : 2 .. m
@
@
@
end for
@
@ =
body procedure least_cost
c_star(1) := l(0,n)
@
@
end least_cost
@ Procedure |least_cost_path| calculates in $I_0,\dots,I_k$ the
vertices on the least-cost path from 0 to $n$ in $G$ with $k$ edges. It
uses the function $J(k,i)$ computed by procedure |least_cost|.
@ =
body procedure least_cost_path
I(0) := 0
I(k) := n
for i : 1 .. k-1
I(i) := J(k-(i-1), I(i-1))
assert I(i) > I(i-1)
end for
assert I(k-1) < n
end least_cost_path
@
@(paths.ch@> +=
body module paths
var J : array 2 .. m, 0 .. n-2 of nat
@
@
end paths
@ We store $c_k(0)$, the cost of the best 0-to-$n$ $k$-edge path, in
$c^*(k)$. If we know a relationship between the cost of the best path with
$k$ edges and that of the one with $k-1$ edges, e.g. $c^*(k)>c^*(k-1)$, the
function |relation| allows us to check that it holds.
@ =
c_star(k) := c_k(0)
assert relation (c_star(k), c_star(k-1))
@
@ =
var c_k, c_k_1 : array 0 .. n-1 of real
for i : 0 .. n-1 % Here k = 2.
c_k_1(i) := l(i,n)
end for
c_k(n-1) := l(n-1,n) % Here k = 1 and this never changes.
@
@ =
for i : 0 .. n-2
c_k_1(i) := c_k(i)
end for
@* Index.