gov.nist.antd.merlin.algorithm.route.shortestpath.k
Class KspDisjoint

java.lang.Object
  |
  +--gov.nist.antd.merlin.algorithm.AlgorithmTemplate
        |
        +--gov.nist.antd.merlin.algorithm.route.shortestpath.k.KspDisjoint

All Implemented Interfaces:

Algorithm, DMLDump

public class KspDisjoint

extends AlgorithmTemplate

This class implements the k-shortest node-disjoint paths with the Dijkstra's algorithm. As it finds each shortest path, it removes the nodes on that path from the graph, so the next shortest path can be found. Format: centralized [name k use gov.nist.antd.merlin.algorithm.route.shortestPathDistance.KspDisjoint connection [from to ] ] The cost is the distance of a link.

 This class was developed at the National Institute of Standards and
 Technology by employees of the Federal Government in the course of
 their official duties. Pursuant to title 17 Section 105 of the United
 States Code this software is not subject to copyright protection and
 is in the public domain.
 NIST assumes no responsibility whatsoever for its use by other parties,
 and makes no guarantees, expressed or implied, about its quality,
 reliability, or any other characteristic.
 

 We would appreciate acknowledgement if the software is used.
 

 NIST ALLOWS FREE USE OF THIS SOFTWARE IN ITS "AS IS" CONDITION AND
 DISCLAIM ANY LIABILITY OF ANY KIND FOR ANY DAMAGES WHATSOEVER RESULTING
 FROM THE USE OF THIS SOFTWARE.
 

Author:

borchert

, gallo , rouil

Nested Class Summary

class

KspDisjoint.KGraph KGraph adds a method deleteEdge and overides buildpath() to be able to delete edges in the graph as paths are constructed.

Field Summary

private KspDisjoint.KGraph	graph The graph of the net.
private int	k find the k shortest paths.

Fields inherited from class gov.nist.antd.merlin.algorithm.AlgorithmTemplate

Fields inherited from interface gov.nist.antd.optical.algorithm.Algorithm

ROUTING, RWA, UNKNOWN, WAVELENGTH

Constructor Summary

KspDisjoint()
Default constructor.

Method Summary

void	config(com.renesys.raceway.DML.Configuration cfg, Glass net) Configure the Centralized Algorithm.
void	dijkstra(int startId) The Dijktra's algorithm.
java.lang.Object[]	execute(Glass net, OpticalConnection[] routes, java.lang.Object[] parameter) This method executes the algorithm in the synchronized mode.
java.util.Vector	execute(Glass net, java.util.Vector routes, java.util.Vector parameter) This method executes the algorithm.
private double	getCost(Edge edge) Get the cost of the given edge
byte	getType() Returns the value of the routing algorithms.
boolean	processRequest(OpticalConnection oRoute) Process a request
java.lang.String	toDML() This method generates the DML representation of this class.

Methods inherited from class gov.nist.antd.merlin.algorithm.AlgorithmTemplate

getName, isDebug, setDebug, setName

Methods inherited from class java.lang.Object

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

Field Detail

k

private int k

find the k shortest paths.

graph

private KspDisjoint.KGraph graph

The graph of the net.

Constructor Detail

KspDisjoint

public KspDisjoint()

Default constructor.

Method Detail

dijkstra

public void dijkstra(int startId)

The Dijktra's algorithm. The cost of an edge is the distance of the link

getCost

private double getCost(Edge edge)

Get the cost of the given edge

Parameters:

edge - The edge.

Returns:

the cost of the given edge.

processRequest

public boolean processRequest(OpticalConnection oRoute)

Process a request

Parameters:

oRoute - The connection Request

execute

public java.util.Vector execute(Glass net,
                                java.util.Vector routes,
                                java.util.Vector parameter)
                         throws AlgorithmException

This method executes the algorithm.

Specified by:

execute in interface Algorithm

Specified by:

execute in class AlgorithmTemplate

Parameters:

net - The OpNet that contains the topology.

routes - The vector containing the OpticalConnection objects. These objects must not have an owner.

parameter - not used by this algorithm.

Returns:

The route vector containing the objects of OpticalRoutes with the calculated linklist.

Throws:

AlgorithmException - An AlgorithmException occured.

execute

public java.lang.Object[] execute(Glass net,
                                  OpticalConnection[] routes,
                                  java.lang.Object[] parameter)
                           throws AlgorithmException

This method executes the algorithm in the synchronized mode.

Specified by:

execute in interface Algorithm

Overrides:

execute in class AlgorithmTemplate

Parameters:

net - The OpNet that contains the topology.

routes - The array of OpticalConnection objects. These objects must not have an owner.

parameter - The array of objects containing the parameters for the algorithm.

Returns:

The array of objects containing the result.

Throws:

AlgorithmException - An AlgorithmException occured.

config

public void config(com.renesys.raceway.DML.Configuration cfg,
                   Glass net)
            throws com.renesys.raceway.DML.configException

Configure the Centralized Algorithm.

Specified by:

config in interface Algorithm

Overrides:

config in class AlgorithmTemplate

Parameters:

cfg - configuration

net - The OpNet that contains the topology.

Throws:

com.renesys.raceway.DML.configException - when a configuration exception occurs.

toDML

public java.lang.String toDML()

This method generates the DML representation of this class. Only return the options.

Specified by:

toDML in interface DMLDump

Overrides:

toDML in class AlgorithmTemplate

Returns:

The DML configuration as String

getType

public byte getType()

Returns the value of the routing algorithms.

Specified by:

getType in interface Algorithm

Overrides:

getType in class AlgorithmTemplate

Returns:

The value Algorithm.ROUTING.