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

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

All Implemented Interfaces:

RoutingAlg<V,E>, WithEnvParams

public class DijkstraMaxWidth<V,E>
extends DijkstraAll<V,E>

Finds a path between two nodes offering the maximum minimum "width", where the width is anything passed as a cost map. For example, if the cost map is set to the residual capacity, this class finds the widest path. If more than one such path exists, that with fewer hops from the source is returned.

Beware that is class does not find "shortest paths" but solves the maximum bottleneck problem..

The implementation of the classical adaptaion of Dijkstra's algorithm to the "bottleneck" problem. See for instance

N. Malpani and J. Chen. "A note on practical construction of maximum bandwidth paths", Information processing letters, vol. 83, num 3, pp. 175-180, 2002.

A difference, however, is that DijkstraMaxWidth uses distance from source (in hops) to break a tie, that is, when two paths offer the same bottleneck, the shorter of the two is chosen.

This problem requires a "maximum" priority queue, that is, one where the first element to remove is the one with the highest key. DijkstraAll uses a "minimum" priority queue. Thus, to take advantage of the methods in that class, the keys in the priority queue are inserted here with negative sign (negated).

Example: Given the following topology:

 :n: indicates link "width" (capacity for example).

  2 ----:8:---- 5 ----:9:---- 6
  |             |             |
  |             |             |
 :7:           :3:            |
  |             |             |
  |             |             |
  1 ----:8:---- 4            :2:
  |             |             |
  |             |             |
 :3:           :8:            |
  |             |             |
  |             |             |
  0 ----:8:---- 3 ----:5:---- 7
 

The SWPs from node 0 are:

   Path            Max-bottleneck
   ------------------------------
   0-3-4-1               8
   0-3-4-1-2             7
   0-3                   8
   0-3-4                 8
   0-3-4-1-2-5           7
   0-3-4-1-2-5-6         7
   0-3-7                 5
 

Notes:

• The method DijkstraAll.runAll(V, V, int) is supported.
• getTotalCost() returns -INF for destinations for which DijkstraAll.obtain(V) returns null.

Author:

Juan Segovia S.

Nested Class Summary

Nested classes/interfaces inherited from class bcds.phison.ra.DijkstraAll

DijkstraAll.PathExpansionInfo

Constructor Summary

DijkstraMaxWidth()
Default constructor.

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

Method Summary

DijkstraAll.PathExpansionInfo	evalEdge(E e) Returns an object with the field is_shorter set to true if link e offers a "wider" path to target(e), or it is of the same "width" but the source is shorter throuth it in number of hops.
void	initialize() Sets total_cost[src] to +INF and the rest to -INF.

Methods inherited from class bcds.phison.ra.DijkstraAll

dumpEvalEdgeState, filterGraph, generalizedDijkstra, getParent, getTotalCost, getVisitSequence, obtain, obtain, outgoingEdgesOf, run, runAll, setup

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

DijkstraMaxWidth

public DijkstraMaxWidth()

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

DijkstraMaxWidth

public DijkstraMaxWidth(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.

The cost map, via getCost(e), is used for obtaining the "width" of each link. The residual capacity is used only to exclude links that cannot meet the required capacity.

Method Detail

initialize

public void initialize()

Sets total_cost[src] to +INF and the rest to -INF. These two values make that: a) at the beginning, any link adjacent to the source is a "possible bottleneck", and b) non-initialized nodes accept any new parent.

Overrides:

initialize in class DijkstraAll<V,E>

evalEdge

public DijkstraAll.PathExpansionInfo evalEdge(E e)

Returns an object with the field is_shorter set to true if link e offers a "wider" path to target(e), or it is of the same "width" but the source is shorter throuth it in number of hops. The field new_cost is set to min(total_cost[source(e)], ted.getCost(e)).
The field prioq_key is set to -new_cost so that the min priority queue can be used as a "max" priority queue, that is, the nodes that offers the "widest" path is closer to the source.

Overrides:

evalEdge in class DijkstraAll<V,E>