com.net2plan.libraries

Class CandidatePathList

Object

com.net2plan.libraries.CandidatePathList

public class CandidatePathList
extends Object

A candidate path list is an object containing a set of paths computed for each demand in the network. This object is commonly used for solving flow-path formulations. Each path is characterized by a demand and a sequence of traversed links (route). If more than one demand exists between two nodes, the same route appears in different paths, each for one demand. There are several forms of initializing a candidate path list, based on the k-shortest path idea. In general, for every demand k paths are computed with the shortest weight according to some weights assigned to the links.

The computation of paths can be configured via "parameter=value" options in the constructor. There are several options to configure, which can be combined:

• computePaths: Indicates whether or not paths should be computed (default: true)
• K: Number of desired loopless shortest paths (default: 3). If K'<K different paths are found between the demand node pairs, then only K' paths are included in the candidate path list
• maxLengthInKm: Maximum path length measured in kilometers allowed (default: Double.MAX_VALUE)
• maxNumHops: Maximum number of hops allowed (default: Integer.MAX_VALUE)
• maxPropDelayInMs: Maximum propagation delay in miliseconds allowed in a path (default: Double.MAX_VALUE)
• maxWeight: Maximum path weight allowed (default: Double.MAX_VALUE)
• maxWeightFactorRespectToShortestPath: Maximum path weight factor with respect to the shortest path weight (default: Double.MAX_VALUE)
• maxWeightRespectToShortestPath: Maximum path weight with respect to the shortest path weight (default: Double.MAX_VALUE). While the previous one is a multiplicative factor, this one is an additive factor
• useRoutesWithinNetPlan: Indicates whether or not existing routes are added to the candidate path list (default: false)
• weights: Link weight vector (default: vector of 1s, which corresponds to a shortest path algorithm using number of hops as metric)

Since:

0.2.0

Author:

Pablo Pavon-Marino, Jose-Luis Izquierdo-Zaragoza

Constructor Summary

Constructors

Constructor and Description
CandidatePathList(File f) Initializes the candidate path list, previously stored in a system file.
CandidatePathList(NetPlan netPlan, long layerId, Map<Long,Double> linkWeightMap, String... paramValuePairs) Initializes the candidate path list, computing all the paths for each demand.
CandidatePathList(NetPlan netPlan, long layerId, String... paramValuePairs) Initializes the candidate path list, computing all the paths for each demand.
CandidatePathList(NetPlan netPlan, Map<Long,Double> linkWeightMap, String... paramValuePairs) Initializes the candidate path list, computing all the paths for each demand.
CandidatePathList(NetPlan netPlan, String... paramValuePairs) Initializes the candidate path list, computing all the paths for each demand.

Method Summary

Methods

Modifier and Type	Method and Description
long	addPath(long demandId, List<Long> seqLinks) Adds a new path to the path list.
Map<Long,Double>	computeDemandCarriedTraffic(double[] x_p) Computes the amount of traffic carried for each demand, if each path carries the traffic given in x_p vector
Map<Long,Double>	computeDemandShortestPathWeight(Map<Long,Double> linkWeightMap) Returns the shortest path cost for every demand.
Map<Long,Double>	computeLinkCarriedTrafficMap(double[] y_p) Computes the amount of traffic in each link, if each path carries the traffic given in x_p vector.
Map<Long,Double>	computeLinkCarriedTrafficMap(Map<Long,Double> y_p) Computes the amount of traffic in each link, if each path carries the traffic given in x_p vector.
double[]	computeLinkCarriedTrafficVector(double[] y_p) Computes the amount of traffic in each link, if each path carries the traffic given in x_p vector.
double[]	computeLinkCarriedTrafficVector(Map<Long,Double> y_p) Computes the amount of traffic in each link, if each path carries the traffic given in y_p map.
Map<Long,Double>	computePathMaximumCarriedTrafficMap(double[] h_d) Computes for each path the maximum amount of traffic that is expected to carry in case of non-bifurcated routing, that is, the offered traffic of its corresponding demand.
Map<Long,Double>	computePathMaximumCarriedTrafficMap(Map<Long,Double> h_d) Computes for each path the maximum amount of traffic that is expected to carry in case of non-bifurcated routing, that is, the offered traffic of its corresponding demand.
double[]	computePathMaximumCarriedTrafficVector(double[] h_d) Computes for each path the maximum amount of traffic that is expected to carry in case of non-bifurcated routing, that is, the offered traffic of its corresponding demand.
double[]	computePathMaximumCarriedTrafficVector(Map<Long,Double> h_d) Computes for each path the maximum amount of traffic that is expected to carry in case of non-bifurcated routing, that is, the offered traffic of its corresponding demand.
cern.colt.matrix.tdouble.DoubleMatrix2D	getDemand2LinkAssignmentMatrix() Returns the demand-link incidence matrix (a DxE matrix in which an element δde is equal to the number of times which traffic routes carrying traffic from demand d traverse link e).
cern.colt.matrix.tdouble.DoubleMatrix2D	getDemand2PathAssignmentMatrix() Returns the demand-path incidence matrix (a DxP matrix in which an element δdp is equal to 1 if traffic route p is able to carry traffic from demand d).
Set<Long>	getDemandPaths(long demandId) Returns the set of identifiers of the paths that are associated to the demand.
long[]	getDemandPathsVector(long demandId) Returns the array of identifiers of the paths that are associated to the demand.
cern.colt.matrix.tdouble.DoubleMatrix2D	getLink2PathAssignmentMatrix() Returns the link-path incidence matrix (an ExP matrix in which an element δep is equal to the number of times which traffic route p traverses link e).
Set<Long>	getLinkAssociatedPaths(long linkId) Returns the set of identifiers of the paths that traverse a link.
long[]	getLinkAssociatedPathsVector(long linkId) Returns the array of identifiers of the paths that traverse a link.
Set<Long>	getNodePairPaths(long ingressNodeId, long egressNodeId) Returns the set of identifiers of the paths that are associated to the first demand of a node pair.
long[]	getNodePairPathsVector(long ingressNodeId, long egressNodeId) Returns the array of identifiers of the paths that are associated to the first demand of a node pair.
int	getNumberOfPaths() Returns the number of paths in the list.
List<List<Long>>	getPathAllSequencesOfLinksList() Returns the sequence of links for each path in ascending order of path identifier.
Map<Long,List<Long>>	getPathAllSequencesOfLinksMap() Returns the sequence of links for each path.
double	getPathCost(long pathId) Returns the cost of a path, given a set of link weights.
double	getPathCost(long pathId, Map<Long,Double> linkWeightMap) Returns the cost of a path, given a set of link weights.
Map<Long,Double>	getPathCostMap() Computes the weight of each path in the list, for the given weight of the links.
Map<Long,Double>	getPathCostMap(Map<Long,Double> linkWeightMap) Computes the weight of each path in the list, for the given weight of the links.
double[]	getPathCostVector() Computes the weight of each path in the list, for the given weight of the links.
double[]	getPathCostVector(Map<Long,Double> linkWeightMap) Computes the weight of each path in the list, for the given weight of the links.
long	getPathDemand(long pathId) Obtains the demand associated to the path.
List<Long>	getPathDemandList() Obtains the demand associated to each path in ascending order of path identifiers.
Map<Long,Long>	getPathDemandMap() Obtains the demand associated to each path.
long[]	getPathDemandVector() Obtains a vector with the demand associated to each path.
Set<Long>	getPathIds() Returns the identifiers of the active paths.
long[]	getPathIdsVector() Returns the identifiers of the active paths.
long	getPathNextId() Returns the identifier of the next added path.
List<Long>	getPathSequenceOfLinks(long pathId) Returns the sequence of links associated to a path.
List<Long>	getPathSequenceOfNodes(long pathId) Obtains the sequence of nodes of the given path.
boolean	isPathActive(long pathId) Indicates whether a path is active.
boolean	linkBelongsToPath(long linkId, long pathId) Checks whether a link belongs to a path.
void	removePath(long pathId) Removes a path from the candidate path list.
void	removePaths(Set<Long> pathIds) Removes a set of paths from the candidate path list.
void	saveToFile(File f) Saves the current candidate path list to a given file for further usage.
String	toString() A formatted String describing the paths in the list, their associated demands and sequence of links.

Methods inherited from class Object

equals, getClass, hashCode, notify, notifyAll, wait, wait, wait

Constructor Detail

CandidatePathList

public CandidatePathList(File f)

Initializes the candidate path list, previously stored in a system file.

Parameters:

f - File containing a previously computed CandidatePathList

Since:

0.3.0

CandidatePathList

public CandidatePathList(NetPlan netPlan,
                 long layerId,
                 Map<Long,Double> linkWeightMap,
                 String... paramValuePairs)

Initializes the candidate path list, computing all the paths for each demand. A candidate path list is an object containing a set of paths computed for each demand in the network. This object is commonly used for solving flow-path formulations. Each path is characterized by a demand and a sequence of traversed links (route). If more than one demand exists between two nodes, one path per demand is created, even though they follow the same route. There are several forms of initializing a candidate path list, based on the k-shortest path idea. In general, for every demand k paths are computed with the shortest weight according to some weights assigned to the links.

Parameters:

netPlan - The network plan, containing at least the nodes, links and demands in the network. Routes already defined will be ommitted

layerId - Layer identifier

linkWeightMap - Link weight for the shortest path algorithm (null means 'all-one' map)

paramValuePairs - Parameters to be passed to the class to tune its operation. An even number of String is to be passed. For each String pair, first String must be the name of the parameter, second a String with its value. If no name-value pairs are set, default values are used

Since:

0.3.0

CandidatePathList

public CandidatePathList(NetPlan netPlan,
                 long layerId,
                 String... paramValuePairs)

Initializes the candidate path list, computing all the paths for each demand. A candidate path list is an object containing a set of paths computed for each demand in the network. This object is commonly used for solving flow-path formulations. Each path is characterized by a demand and a sequence of traversed links (route). If more than one demand exists between two nodes, one path per demand is created, even though they follow the same route.

There are several forms of initializing a candidate path list, based on the k-shortest path idea. In general, for every demand k paths are computed with the shortest weight according to some weights assigned to the links.

Here, all link weights are initialized to 1, meaning that shortest path will be computed according to the number of hops.

Parameters:

netPlan - The network plan, containing at least the nodes, links and demands in the network. Routes already defined will be ommitted

layerId - Layer identifier

paramValuePairs - Parameters to be passed to the class to tune its operation. An even number of String is to be passed. For each String pair, first String must be the name of the parameter, second a String with its value. If no name-value pairs are set, default values are used

Since:

0.3.0

CandidatePathList

public CandidatePathList(NetPlan netPlan,
                 Map<Long,Double> linkWeightMap,
                 String... paramValuePairs)

Initializes the candidate path list, computing all the paths for each demand. A candidate path list is an object containing a set of paths computed for each demand in the network. This object is commonly used for solving flow-path formulations. Each path is characterized by a demand and a sequence of traversed links (route). If more than one demand exists between two nodes, one path per demand is created, even though they follow the same route. There are several forms of initializing a candidate path list, based on the k-shortest path idea. In general, for every demand k paths are computed with the shortest weight according to some weights assigned to the links.

Parameters:

netPlan - The network plan, containing at least the nodes, links and demands in the network. Routes already defined will be ommitted

linkWeightMap - Link weight for the shortest path algorithm (null means 'all-one' map)

paramValuePairs - Parameters to be passed to the class to tune its operation. An even number of String is to be passed. For each String pair, first String must be the name of the parameter, second a String with its value. If no name-value pairs are set, default values are used

Since:

0.2.0

CandidatePathList

public CandidatePathList(NetPlan netPlan,
                 String... paramValuePairs)

Initializes the candidate path list, computing all the paths for each demand. A candidate path list is an object containing a set of paths computed for each demand in the network. This object is commonly used for solving flow-path formulations. Each path is characterized by a demand and a sequence of traversed links (route). If more than one demand exists between two nodes, one path per demand is created, even though they follow the same route.

There are several forms of initializing a candidate path list, based on the k-shortest path idea. In general, for every demand k paths are computed with the shortest weight according to some weights assigned to the links.

Here, all link weights are initialized to 1, meaning that shortest path will be computed according to the number of hops.

Parameters:

netPlan - The network plan, containing at least the nodes, links and demands in the network. Routes already defined will be ommitted

paramValuePairs - Parameters to be passed to the class to tune its operation. An even number of String is to be passed. For each String pair, first String must be the name of the parameter, second a String with its value. If no name-value pairs are set, default values are used

Since:

0.2.0

Method Detail

addPath

public long addPath(long demandId,
           List<Long> seqLinks)

Adds a new path to the path list.

Parameters:

demandId - Demand identifier

seqLinks - Sequence of traversed links

Returns:

Path identifier

Since:

0.3.0

computeDemandCarriedTraffic

public Map<Long,Double> computeDemandCarriedTraffic(double[] x_p)

Computes the amount of traffic carried for each demand, if each path carries the traffic given in x_p vector

Parameters:

x_p - The traffic carried by each path in the list

Returns:

The traffic carried by each demand

Since:

0.2.0

computeDemandShortestPathWeight

public Map<Long,Double> computeDemandShortestPathWeight(Map<Long,Double> linkWeightMap)

Returns the shortest path cost for every demand.

Parameters:

linkWeightMap - Link weights

Returns:

Shortest path cost for every demand

Since:

0.2.0

computeLinkCarriedTrafficMap

public Map<Long,Double> computeLinkCarriedTrafficMap(double[] y_p)

Computes the amount of traffic in each link, if each path carries the traffic given in x_p vector.

Parameters:

y_p - Capacity units occupied by each path

Returns:

The traffic carried in each link

Since:

0.2.0

computeLinkCarriedTrafficMap

public Map<Long,Double> computeLinkCarriedTrafficMap(Map<Long,Double> y_p)

Computes the amount of traffic in each link, if each path carries the traffic given in x_p vector.

Parameters:

y_p - Capacity units occupied by each path

Returns:

The traffic carried in each link

Since:

0.2.0

computeLinkCarriedTrafficVector

public double[] computeLinkCarriedTrafficVector(double[] y_p)

Computes the amount of traffic in each link, if each path carries the traffic given in x_p vector.

Parameters:

y_p - Capacity units occupied by each path

Returns:

The traffic carried in each link

Since:

0.2.0

computeLinkCarriedTrafficVector

public double[] computeLinkCarriedTrafficVector(Map<Long,Double> y_p)

Computes the amount of traffic in each link, if each path carries the traffic given in y_p map.

Parameters:

y_p - Capacity units occupied by each path

Returns:

The traffic carried in each link

Since:

0.2.0

computePathMaximumCarriedTrafficMap

public Map<Long,Double> computePathMaximumCarriedTrafficMap(double[] h_d)

Computes for each path the maximum amount of traffic that is expected to carry in case of non-bifurcated routing, that is, the offered traffic of its corresponding demand.

Parameters:

h_d - Offered traffic per demand

Returns:

Maximum traffic that is expected to carry each path in case of non-bifurcated routing

Since:

0.3.1

computePathMaximumCarriedTrafficMap

public Map<Long,Double> computePathMaximumCarriedTrafficMap(Map<Long,Double> h_d)

Computes for each path the maximum amount of traffic that is expected to carry in case of non-bifurcated routing, that is, the offered traffic of its corresponding demand.

Parameters:

h_d - Offered traffic per demand

Returns:

Maximum traffic that is expected to carry each path in case of non-bifurcated routing

Since:

0.3.0

computePathMaximumCarriedTrafficVector

public double[] computePathMaximumCarriedTrafficVector(double[] h_d)

Computes for each path the maximum amount of traffic that is expected to carry in case of non-bifurcated routing, that is, the offered traffic of its corresponding demand.

Parameters:

h_d - Offered traffic per demand

Returns:

Maximum traffic that is expected to carry each path in case of non-bifurcated routing

Since:

0.3.1

computePathMaximumCarriedTrafficVector

public double[] computePathMaximumCarriedTrafficVector(Map<Long,Double> h_d)

Computes for each path the maximum amount of traffic that is expected to carry in case of non-bifurcated routing, that is, the offered traffic of its corresponding demand.

Parameters:

h_d - Offered traffic per demand

Returns:

Maximum traffic that is expected to carry each path in case of non-bifurcated routing

Since:

0.3.0

getDemand2LinkAssignmentMatrix

public cern.colt.matrix.tdouble.DoubleMatrix2D getDemand2LinkAssignmentMatrix()

Returns the demand-link incidence matrix (a DxE matrix in which an element δ_de is equal to the number of times which traffic routes carrying traffic from demand d traverse link e).

Returns:

The demand-link incidence matrix

Since:

0.3.1

getDemand2PathAssignmentMatrix

public cern.colt.matrix.tdouble.DoubleMatrix2D getDemand2PathAssignmentMatrix()

Returns the demand-path incidence matrix (a DxP matrix in which an element δ_dp is equal to 1 if traffic route p is able to carry traffic from demand d).

Returns:

The demand-path incidence matrix

Since:

0.3.1

getDemandPaths

public Set<Long> getDemandPaths(long demandId)

Returns the set of identifiers of the paths that are associated to the demand.

Parameters:

demandId - Demand identifier

Returns:

A set with the path identifiers

Since:

0.3.0

getDemandPathsVector

public long[] getDemandPathsVector(long demandId)

Returns the array of identifiers of the paths that are associated to the demand.

Parameters:

demandId - Demand identifier

Returns:

An array with the path identifiers

Since:

0.3.0

getLink2PathAssignmentMatrix

public cern.colt.matrix.tdouble.DoubleMatrix2D getLink2PathAssignmentMatrix()

Returns the link-path incidence matrix (an ExP matrix in which an element δ_ep is equal to the number of times which traffic route p traverses link e).

Returns:

The link-path incidence matrix

Since:

0.3.1

getLinkAssociatedPaths

public Set<Long> getLinkAssociatedPaths(long linkId)

Returns the set of identifiers of the paths that traverse a link.

Parameters:

linkId - Link identifier

Returns:

A set with path identifiers

Since:

0.3.0

getLinkAssociatedPathsVector

public long[] getLinkAssociatedPathsVector(long linkId)

Returns the array of identifiers of the paths that traverse a link.

Parameters:

linkId - Link identifier

Returns:

An array with path identifiers

Since:

0.3.0

getNodePairPaths

public Set<Long> getNodePairPaths(long ingressNodeId,
                         long egressNodeId)

Returns the set of identifiers of the paths that are associated to the first demand of a node pair.

Parameters:

ingressNodeId - Ingress node identifier

egressNodeId - Ingress node identifier

Returns:

A set with path identifiers

Since:

0.3.0

getNodePairPathsVector

public long[] getNodePairPathsVector(long ingressNodeId,
                            long egressNodeId)

Returns the array of identifiers of the paths that are associated to the first demand of a node pair.

Parameters:

ingressNodeId - Ingress node identifier

egressNodeId - Ingress node identifier

Returns:

An array with the path identifiers

Since:

0.3.0

getNumberOfPaths

public int getNumberOfPaths()

Returns the number of paths in the list.

Returns:

The number of paths

Since:

0.2.0

getPathAllSequencesOfLinksList

public List<List<Long>> getPathAllSequencesOfLinksList()

Returns the sequence of links for each path in ascending order of path identifier.

Returns:

List of sequence of links

Since:

0.3.0

getPathAllSequencesOfLinksMap

public Map<Long,List<Long>> getPathAllSequencesOfLinksMap()

Returns the sequence of links for each path.

Returns:

Sequence of links per path

Since:

0.3.0

getPathCost

public double getPathCost(long pathId)

Returns the cost of a path, given a set of link weights.

Parameters:

pathId - Path identifier

Returns:

Path cost

Since:

0.3.0

getPathCost

public double getPathCost(long pathId,
                 Map<Long,Double> linkWeightMap)

Returns the cost of a path, given a set of link weights.

Parameters:

pathId - Path identifier

linkWeightMap - Link weights

Returns:

Path cost

Since:

0.3.0

getPathCostMap

public Map<Long,Double> getPathCostMap()

Computes the weight of each path in the list, for the given weight of the links. The weight of a path is the sum of the weights of the traversing links

Returns:

An array with the cost of each path

Since:

0.2.0

getPathCostMap

public Map<Long,Double> getPathCostMap(Map<Long,Double> linkWeightMap)

Computes the weight of each path in the list, for the given weight of the links. The weight of a path is the sum of the weights of the traversing links

Parameters:

linkWeightMap - The set of weight per link

Returns:

An array with the cost of each path

Since:

0.2.0

getPathCostVector

public double[] getPathCostVector()

Computes the weight of each path in the list, for the given weight of the links. The weight of a path is the sum of the weights of the traversing links

Returns:

An array with the cost of each path

Since:

0.2.0

getPathCostVector

public double[] getPathCostVector(Map<Long,Double> linkWeightMap)

Computes the weight of each path in the list, for the given weight of the links. The weight of a path is the sum of the weights of the traversing links

Parameters:

linkWeightMap - The set of weight per link

Returns:

An array with the cost of each path

Since:

0.2.0

getPathDemand

public long getPathDemand(long pathId)

Obtains the demand associated to the path.

Parameters:

pathId - Path identifier

Returns:

Demand identifier

Since:

0.3.0

getPathDemandList

public List<Long> getPathDemandList()

Obtains the demand associated to each path in ascending order of path identifiers.

Returns:

A list with the demand identifier for each path

Since:

0.3.0

getPathDemandMap

public Map<Long,Long> getPathDemandMap()

Obtains the demand associated to each path.

Returns:

A map with the demand identifier for each path

Since:

0.3.0

getPathDemandVector

public long[] getPathDemandVector()

Obtains a vector with the demand associated to each path.

Returns:

A vector with the demand identifiers

Since:

0.3.0

getPathIds

public Set<Long> getPathIds()

Returns the identifiers of the active paths.

Returns:

An ordered set with the path identifiers

Since:

0.3.0

getPathIdsVector

public long[] getPathIdsVector()

Returns the identifiers of the active paths.

Returns:

An ordered vector with the path identifiers

Since:

0.3.0

getPathNextId

public long getPathNextId()

Returns the identifier of the next added path.

Returns:

Next path identifier

Since:

0.3.0

getPathSequenceOfLinks

public List<Long> getPathSequenceOfLinks(long pathId)

Returns the sequence of links associated to a path.

Parameters:

pathId - Path identifier

Returns:

Sequence of links

Since:

0.3.0

getPathSequenceOfNodes

public List<Long> getPathSequenceOfNodes(long pathId)

Obtains the sequence of nodes of the given path.

Parameters:

pathId - Path identifier

Returns:

Sequence of nodes

Since:

0.3.0

isPathActive

public boolean isPathActive(long pathId)

Indicates whether a path is active.

Parameters:

pathId - Path identifier

Returns:

true in case the path is active. Otherwise, false

Since:

0.3.0

linkBelongsToPath

public boolean linkBelongsToPath(long linkId,
                        long pathId)

Checks whether a link belongs to a path.

Parameters:

linkId - Link identifier

pathId - Path identifier

Returns:

true if link e belongs to path p. Otherwise, false.

Since:

0.3.0

removePath

public void removePath(long pathId)

Removes a path from the candidate path list.

Parameters:

pathId - Path identifier

Since:

0.3.0

removePaths

public void removePaths(Set<Long> pathIds)

Removes a set of paths from the candidate path list.

Parameters:

pathIds - Path identifiers

Since:

0.3.0

saveToFile

public void saveToFile(File f)

Saves the current candidate path list to a given file for further usage.

Parameters:

f - Output file

Since:

0.3.0

toString

public String toString()

A formatted String describing the paths in the list, their associated demands and sequence of links.

Overrides:

toString in class Object

Returns:

String

Since:

0.2.0