/* Copyright (c) 2001 by Kevin Forchione. All Rights Reserved. */
/*
* TADS ADV.T/STD.T LIBRARY EXTENSION
* DIJKSTRA.T
* Version 1.1
*
* Djikstra's algorithm (named after its discover, E.W. Dijkstra)
* solves the problem of finding the shortest path from a point
* in a graph (the source) to a destination. It turns out that one
* can find the shortest paths from a given source to all points
* in a graph in the same time, hence this problem is sometimes
* called the single-source shortest paths problem.
*
* This problem is related to the spanning tree one. The graph
* representing all the paths from one vertex to all the others
* must be a spanning tree - it must include all vertices. There
* will also be no cycles as a cycle would define more than one
* path from the selected vertex to at least one other vertex.
*
*----------------------------------------------------------------------
* REQUIREMENTS
*
* + HTML TADS 2.2.6 or later
* + Should be #included after ADV.T and STD.T
*
*----------------------------------------------------------------------
* IMPORTANT LIBRARY INTERFACE AND MODIFICATION
*
* + none
*
*----------------------------------------------------------------------
* COPYRIGHT NOTICE
*
* You may modify and use this file in any way you want, provided that
* if you redistribute modified copies of this file in source form, the
* copies must include the original copyright notice (including this
* paragraph), and must be clearly marked as modified from the original
* version.
*
*------------------------------------------------------------------------------
* REVISION HISTORY
*
* 21-Jan-01: Creation.
* 08-Feb-01: Changed MAX_VALUE to INFINITY and added logic
* to handle cases where (a+b)mod INFINITY < (a+b).
*/
#ifndef _DIJKSTRA_T_
#define _DIJKSTRA_T_
#pragma C+
#define INFINITY 0x7fffffff
class Entry: object
vertex = nil
known = nil
predecessor = nil
value = nil
adjacentEntryList = []
/* the vertex of the initial entry object */
startingVertex = nil
/*
* We loop through the dijkstra algorithm until there are no more
* unknown vertices. This approach attempts to avoid stack
* overflow due to recursion.
*/
main = {
while( self.dijkstra ) {}
}
dijkstra = {
local i, v, w, len, adjEntryList, edgeValue;
/*
* From the set of vertices for which (e.known == nil), select
* the vertex having the smallest tentative value.
*/
v = self.getMinUnknownEntry;
/*
* If we have no unknown vertices we are done.
*/
if ( v == nil )
return nil;
/*
* Set vertex v.known to true.
*/
v.known = true;
if ( entryListPreloaded )
/*
* The entry list has been pre-loaded at instantiation,
* we already have the vertex's adjacentEntryList. Simply
* retrieve it.
*/
adjEntryList = v.adjacentEntryList;
else
/*
* We are building the path entry list with each iteration
* of dijkstra(). Build the entry's adjacent entry list for
* this vertex.
*/
adjEntryList = self.buildAdjacentEntryList( v );
/*
* For each vertex w adjacent to v for which (w.known == nil),
* test whether the tentative value w.value > v.value + c(v,w).
* If it is, set w.value = v.value + c(v,w) and set
* w.predecessor = v.
*/
len = length( adjEntryList );
for ( i = 1; i <= len; ++i )
{
w = adjEntryList[ i ];
if ( w.known == nil )
{
local tot;
edgeValue = self.computeEdge( v, w );
tot = v.value + edgeValue;
/*
* If tot is smaller than either the
* v.value or the edgeValue then we
* really want tot to be INFINITY.
*/
if ( tot < v.value && tot < edgeValue )
tot = INFINITY;
if ( w.value > tot )
{
w.value = tot;
w.predecessor = v;
}
}
}
/* continue with the next iteration of the algorithm */
return true;
}
/*
* Retrieve the entry with known attribute == nil that has
* the minimum value.
*/
getMinUnknownEntry = {
local i, len, s, unknownList = [];
/* make a list of all unknown entries */
len = length( self.entryList );
for ( i = 1; i <= len; ++i )
{
if ( self.entryList[ i ].known == nil )
{
unknownList += self.entryList[ i ];
}
}
/* if the list is empty we signal that we are done */
len = length( unknownList );
if ( len == 0 )
return nil;
/*
* Retrieve the first entry from the unknown list that
* has the smallest value.
*/
s = unknownList[ 1 ];
for ( i = 2; i <= len; ++i )
{
if ( unknownList[ i ].value < s.value )
{
s = unknownList[ i ];
}
}
return s;
}
/*
* Method loads entries to the path entry list. First the
* list is searched by vertex. If a match is found then we
* simply return the entry. If no match is found we instantiate
* an entry, add it to the list, then return the new entry.
*/
addToEntryList( v ) = {
local e;
/*
* If we don't find an entry for this vertex,
* instantiate an entry for it and add the entry
* to the path entry list.
*/
e = self.getEntryByVertex( v );
if ( e == nil )
{
e = Entry.instantiate( v, nil, INFINITY );
self.entryList += e;
}
/* return the entry */
return e;
}
/*
* Search the path entry list for the entry matching
* this vertex. If we don't find an entry for this vertex
* return nil.
*/
getEntryByVertex( v, ... ) = {
local i, e, len, eList = self.entryList;
if ( argcount == 2 ) eList = getarg(2);
len = length( eList );
for ( i = 1; i <= len; ++i )
{
if ( eList[ i ].vertex == v )
{
e = eList[ i ];
break;
}
}
return e;
}
/*
* Builds the entry's adjacent entry list.
*/
buildAdjacentEntryList( e ) = {
local i, len, vList;
/* We call the vertex to retrieve its adjacent vertices */
vList = e.vertex.getAdjacentVertices;
/*
* If the vertex doesn't return an adjacent vertex
* list or the method is not defined for the vertex
* then we use an empty list.
*/
if ( datatype( vList ) != DTY_LIST )
vList = [];
len = length( vList );
for ( i = 1; i <= len; ++i )
{
/*
* We get the corresponding entry for each vertex of
* the adjacency list. If the entry does not already
* exist in the path entry list then addToEntryList()
* will create a new entry and add it to the path
* entry list.
*/
e.adjacentEntryList += self.addToEntryList( vList[ i ] );
}
return e.adjacentEntryList;
}
/*
* Provide a value for the edge between vertices v and w.
* The default is to assume that the edge is unweighted.
*/
computeEdge( v, w ) = {
return 1;
}
/*
* Retrieve only the entries whose values are less than
* INFINITY. When called after main() this produces
* a list of entries for which the starting vertex has
* a path.
*/
getNonMaxValues = {
local i, e, len, nonMaxList = [];
len = length( self.entryList );
for ( i = 1; i <= len; ++i )
{
e = self.entryList[ i ];
if ( e.value != INFINITY )
{
nonMaxList += e;
}
}
return nonMaxList;
}
/*
* An abstract method, this should be called on the Path class.
* Produces an entry list that indicates the shortest path from
* s to v.
*/
shortestPathEntries( s, v, ... ) = {
local path, e, eList, tmp, lst = [], pArg;
/* create a path entry list for s */
if ( argcount == 3 )
pArg = getarg(3);
case DTY_OBJECT:
if ( isclass( pArg, Path ) )
{
path = pArg;
break;
}
default:
path = Path.instantiate( s );
}
path.main;
/* remove any entries not reachable by s */
eList = path.getNonMaxValues;
/* get the entry for v using our modified list */
e = self.getEntryByVertex( v, eList );
/* build the list in order from s to v */
while( e != nil )
{
tmp = lst;
lst = [ e ] + tmp;
e = e.predecessor;
}
path.shortestPathEntryList = lst;
return path;
}
/*
* An abstract method, this should be called on the Path class.
* Produces a vertex list that indicates the shortest path from
* s to v.
*/
shortestPathVertices( s, v, ... ) = {
local i, e, len, eList, vList = [], path;
/* build the shortest path entry list from s to v */
if ( argcount == 3 )
path = self.shortestPathEntries( s, v, getarg(3) );
else
path = self.shortestPathEntries( s, v );
eList = path.shortestPathEntryList;
/* build the vertex list from the entry list */
len = length( eList );
for ( i = 1; i <= len; ++i )
{
e = eList[ i ];
vList += e.vertex;
}
/* clean up path and entry objects */
delete path;
return vList;
}
instantiate( s, ... ) = {
local i, len, p, e;
/* create a new path */
p = new Path;
/* set the path starting vertex */
p.startingVertex = s;
/*
* The addToEntryList() method will create a new
* default entry and add it to the path entry list.
*/
e = p.addToEntryList( s );
/* Indicate that this is the path starting entry */
e.value = 0;
/*
* If we've been passed a vertex list then we 'pre-load'
* the path entry list before dijkstra processing.
*/
if ( argcount == 2 ) {
local vList = getarg( 2 );
/* build the adjcent entry list for our initial entry */
p.buildAdjacentEntryList( e );
/* remove any occurence of s from vList */
vList -= s;
len = length( vList );
for ( i = 1; i <= len; ++i )
{
/*
* The addToEntryList() method will create a
* new entry or retrieve an existing one. If
* the entry is new then it is added to the
* path entry list and its adjacent entry list
* is set up.
*/
e = p.addToEntryList( vList[ i ] );
p.buildAdjacentEntryList( e );
}
p.entryListPreloaded = true;
}
return p;
}
/* clean up the entries */
destruct = {
local i, o, len;
len = length( self.entryList );
for ( i = 1; i <= len; ++i )
{
o = self.entryList[ i ];
delete o;
}
}
;
