programming/tads2/examples/dijkstra.t

/* 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   = []

    instantiate( v, p, n ) = {
        local e = new Entry;

        e.vertex        = v;
        e.predecessor   = p;
        e.value         = n;

        return e;
    }
;

class Path: object
    entryList       	    = []
    shortestPathEntryList   = []
    entryListPreloaded	    = nil

    /* 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);
    
        switch( datatype( pArg ) )
        {
            case DTY_LIST:
                path = Path.instantiate( s, getarg(3) );
                break;
                
            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;
        }
    }
;

#pragma C-

#endif  /* _DIJKSTRA_T_ */