/* 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_ */