bcds.phison.ra
Class DijkstraAll<V,E>

java.lang.Object
  bcds.phison.ra.RoutingAlgBase<V,E>
      bcds.phison.ra.DijkstraAll<V,E>

All Implemented Interfaces:

RoutingAlg<V,E>, WithEnvParams

Direct Known Subclasses:

DijkstraMaxWidth, LIOA, MinHop, WSP

public class DijkstraAll<V,E>
extends RoutingAlgBase<V,E>
implements RoutingAlg<V,E>

Implements a priority queue based Dijkstra algorithm for finding single-source all-destination shortest paths.

Example of use: The following skeleton shows how to print the shortest paths from some source node to all the others.

    import bcds.phison.ra.DijkstraAll;
    import ...

    // Read graph g of type SimGraph<Node, Link>.
    // Link capacities are in map cap and link costs are
    // in map cost. See GraphReader
    // for an example of how to read the topology.

    TED<Node, Link> ted
       = new TED<Node, Link>(g, cap, cost);
    DijkstraAll<Node, Link> ra = new DijkstraAll<Node, Link>(ted, null);

    // Choose any node from the node set.
    Node u = g.vertexSet().iterator().next();

    ra.runAll(u, u, 0);
    for (Node v : g.vertexSet()) {
       if ( u == v )
          continue;

       Path<Node, Link> p = ra.obtain(v);

       if ( p == null ) {
           System.out.printf("\nNo path available from %s to %s", u, v);
       } else {
           System.out.printf("\n%s = %.0f", p, ra.getTotalCost(v));
       }
    }
 

NOTES FOR DEVELOPERS:

• The "shortest" path for this implementation means the path for which the sum of its link weights (or costs) is the minimum. If the entries in the cost map all return 1, then the shortest path will be the minimum-hop path.
• The main algorithm (see generalizedDijkstra()) is divided into functional "chunks" so that each chunk is delegated to a method that derived classes can override and thus alter the algorithm's behaviour.

  This feature is exploited for example by the classes WSP and DijkstraMaxWidth.

Terminology

• The word run is used quoted ("run") to refer variously to run() or runAll().
• A path request is initiated by a call to "run", and remains the "current" request until another "run". Thus, the expression current source means the source node of a preceeding run. Several methods operate on the "current" request.

Author:

Juan Segovia S.

Nested Class Summary

class

DijkstraAll.PathExpansionInfo Used by evalEdge(E) to store and return the information gathered during the evaluation of the shortest path expanded by the (tentative) inclusion of a given link.

Constructor Summary

DijkstraAll()
Default constructor.

DijkstraAll(TED<V,E> ted, Environ env)
Creates a new instances and passes the parameters to setup.

Method Summary

void	dumpEvalEdgeState(E e, DijkstraAll.PathExpansionInfo pe) Prints debugging information concerning pe and e.
DijkstraAll.PathExpansionInfo	evalEdge(E e) Evaluates the path whose last hop is the link e and determines whether target(e) can have a shorter path via source(e) than what it has now.
void	filterGraph() Saves in this.subg the subgraph resulting from (virtually) removing all links whose residual capacity is below the current requested capacity.
void	generalizedDijkstra() Implements Dijkstra's algorithm divided in functional "chunks" that are delegated to methods (thus, overridable in derived classes).
V	getParent(V v) Returns the parent of node v in the shortest path to the current source, as established by a preceeding call to one of the "run" methods.
double	getTotalCost(V v) Returns the (total) cost of the shortest path from the current source to node v.
java.util.List<V>	getVisitSequence() Returns the nodes visited by a preceeding execution of "run" in the order in which they were removed from the priority queue (once the final minimum cost was determined).
void	initialize() Initializes essential data structures used by the "run" methods.
Path<V,E>	obtain(V dest) Returns the shortest path to dest that has been computed in a previous call to runAll().
Path<V,E>	obtain(V src, V dest) Deprecated. Replaced by obtain(V) so that it is clear that the source node is (implicitly) the one that has been passed to runAll().
java.util.Set<E>	outgoingEdgesOf(V u) Returns the links of u that lead to other nodes (that is, outgoing edges) when that node has just been removed from the priority queue.
Path<V,E>	run(V src, V dest, int rq_cap) Returns the shortest path from src to dest with the restriction that residual capacity must be at least rq_cap along the path.
Path<V,E>	runAll(V src, V dest, int rq_cap) Returns the shortest path from src to dest just as run(V, V, int) but also makes sure that Dijkstra's algorithm runs to completion (that is, creates the full tree rooted at src), thus enabling the use of obtain() later on.
void	setup(TED<V,E> ted, Environ env) Resets all internal data structures.

Methods inherited from class bcds.phison.ra.RoutingAlgBase

buildPathFromParentNodes, commitBackupPath, commitWorkingPath, dumpState, getBackupPath, getCost, getEnviron, getEnvParams, getName, getTED, getWorkingPath, offersProtection, setBackupPath, setRequest, setWorkingPath, topologyHasChanged, uncommitBackupPath, uncommitWorkingPath

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Methods inherited from interface bcds.phison.ra.RoutingAlg

commitBackupPath, commitWorkingPath, dumpState, getBackupPath, getCost, getName, getWorkingPath, offersProtection, topologyHasChanged, uncommitBackupPath, uncommitWorkingPath

Methods inherited from interface bcds.phison.WithEnvParams

getEnviron, getEnvParams

Constructor Detail

DijkstraAll

public DijkstraAll()

Default constructor. To complete the initialization, setup(TED, Environ) must be called.

DijkstraAll

public DijkstraAll(TED<V,E> ted,
                   Environ env)

Creates a new instances and passes the parameters to setup. This class does not expect or use any environment parameter.

Method Detail

setup

public void setup(TED<V,E> ted,
                  Environ env)

Resets all internal data structures.

Specified by:

setup in interface RoutingAlg<V,E>

Overrides:

setup in class RoutingAlgBase<V,E>

obtain

public Path<V,E> obtain(V dest)

Returns the shortest path to dest that has been computed in a previous call to runAll(). Since Dijkstra's algorithm basically obtains paths for all possible destinations in one run, there are situations in which it does not make sense to repeat the path computation when the source node is the same as a previous invocation of run(). This happens, for example, when it is known that the topology is the same, resources are the same, and the requested capacity and the source node are also the same.

This method addresses the preceeding use case: just execute runAll() for a given source, destination and capacity (the destination can even be the same as the source) and then systematically use obtain() until a different source node or capacity are required. Note that a call to runAll() is necessary for obtain() to work, since a simple run() might terminate as soon as it finds the destination node, without computing the shortest path to the remaning nodes.

Throws:

java.lang.IllegalArgumentException - if runAll() has not been called.

obtain

@Deprecated
public Path<V,E> obtain(V src,
                                   V dest)

Deprecated. Replaced by obtain(V) so that it is clear that the source node is (implicitly) the one that has been passed to runAll().

Returns the shortest path from src to dest that has been computed in a previous call to runAll().

Throws:

java.lang.IllegalArgumentException - if runAll() has not been called or the parameter @code src} differs from the source used in a previous call to runAll().

getParent

public V getParent(V v)

Returns the parent of node v in the shortest path to the current source, as established by a preceeding call to one of the "run" methods. Returns null if "run" has not been executed before, or an entry for the requested node cannot be found (for example, if a preceeding "run" finished without establishing a parent for that node).

getTotalCost

public double getTotalCost(V v)

Returns the (total) cost of the shortest path from the current source to node v. It returns whatever was stored for node v by a preceeding call to the "run" methods, or -INF if no such call has been made. If a path from the current source to v does not exist, the value returned is undefined. This class returns +INF in that case, but derived classes may use a different flag value.

getVisitSequence

public java.util.List<V> getVisitSequence()

Returns the nodes visited by a preceeding execution of "run" in the order in which they were removed from the priority queue (once the final minimum cost was determined). The first element is the current source node.

filterGraph

public void filterGraph()

Saves in this.subg the subgraph resulting from (virtually) removing all links whose residual capacity is below the current requested capacity. To achieve this, it calls this.ted.filterByCap(this.rq_cap).

Derived classes may override this to implement some other filtering policy.

initialize

public void initialize()

Initializes essential data structures used by the "run" methods. It is called after the graph has been filtered and just before the actual Dijkstra algorithm begins. The initialization is as follows:

• The priority queue is recreated.
• The parent map is recreated with the current source as its only key with value null.
• The total cost map is recreated, inserting a +INF for each node, except for the current source, which is inserted with value 0.0.
• The structure holding the node visiting order is recreated.
• The structure holding the distance in hops from the source to each node is recreated.
• The source node is inserted into the priority queue with key=0.

Normally, derived classes would call this first, and then proceed with any extra initialization, as essential data structures and values are set up here.

outgoingEdgesOf

public java.util.Set<E> outgoingEdgesOf(V u)

Returns the links of u that lead to other nodes (that is, outgoing edges) when that node has just been removed from the priority queue. This implementation returns the outgoing edges of u in the subgraph (the filtered graph).

evalEdge

public DijkstraAll.PathExpansionInfo evalEdge(E e)

Evaluates the path whose last hop is the link e and determines whether target(e) can have a shorter path via source(e) than what it has now. This implementation does the equivalent of:

    if ( total_cost[source(e)] + getCost(e) < total_cost[target(e)] ) {
       return "reparenting is necessary",
              new cost is the sum above,
              priority key = new cost.
    }
    return "reparenting is not necessary".
 

dumpEvalEdgeState

public void dumpEvalEdgeState(E e,
                              DijkstraAll.PathExpansionInfo pe)

Prints debugging information concerning pe and e.

generalizedDijkstra

public void generalizedDijkstra()

Implements Dijkstra's algorithm divided in functional "chunks" that are delegated to methods (thus, overridable in derived classes).

The implementations is the equivalent to the following pseudo-code. The parts that depend on delegated functions are marked with (*):

   (*) initialize()

       while ( Q is not empty ) {
   (-)    node u = remove min from Q.
          register u in the list of visited nodes.

          break if (u == dest) and (build_full_tree == false).

   (*)    for each edge e in outgoingEdgesOf(u) in subg {
             let v = target(v)
             skip if v has been removed from Q in (-) above.
   (*)       PathExpansionInfo pi = evalEdge(e)
             if ( pi.is_shorter ) {
                update Q with pi.prioq_key.
                update total tost.
                set u as parent of v.
                set v's hops_from_source as one more than that of u's.
             }
          }
       }
 

Explicit checking of residual capacity availability is not performed; it is assumed that filterGraph() had already removed from this.subg all the unsuitable links.

run

public Path<V,E> run(V src,
                     V dest,
                     int rq_cap)

Returns the shortest path from src to dest with the restriction that residual capacity must be at least rq_cap along the path. If no path is available, null is is returned. The full tree is not computed.

The steps performed are:

• call setRequest(src, dest, rq_cap)
• set this.build_full_tree = true if call was initiated through runAll()
• call filterGraph()
• call generalizedDijkstra()
• return path from src to dest and make sure future calls to getWorkingPath() will return this same path.

Specified by:

run in interface RoutingAlg<V,E>

runAll

public Path<V,E> runAll(V src,
                        V dest,
                        int rq_cap)

Returns the shortest path from src to dest just as run(V, V, int) but also makes sure that Dijkstra's algorithm runs to completion (that is, creates the full tree rooted at src), thus enabling the use of obtain() later on.