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:
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 listmaxLengthInKm
: Maximum path length measured in kilometers allowed (default: Double.MAX_VALUE)maxNumHops
: Maximum number of hops allowed (default: Integer.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)weights
: Link weight vector (default: vector of 1s, which corresponds to a shortest path algorithm using number of hops as metric)Constructor and Description |
---|
CandidatePathList(NetPlan netPlan,
boolean useRoutesWithinNetPlan,
double[] weights,
String... paramValuePairs)
Initializes the candidate path list, computing all the paths for each
demand.
|
CandidatePathList(NetPlan netPlan,
boolean useRoutesWithinNetPlan,
String... paramValuePairs)
Initializes the candidate path list, computing all the paths for each
demand.
|
CandidatePathList(NetPlan netPlan,
double[] weights,
String... paramValuePairs)
Initializes the candidate path list, computing all the paths for each
demand.
|
CandidatePathList(NetPlan netPlan,
File f)
Initializes the candidate path list, previously stored in a system file.
|
CandidatePathList(NetPlan netPlan,
String... paramValuePairs)
Initializes the candidate path list, computing all the paths for each
demand.
|
Modifier and Type | Method and Description |
---|---|
int |
addPath(int demandId,
int[] seqLinks)
Adds a new path to the path list.
|
com.jom.DoubleMatrixND |
computeDemand2LinkAssignmentMatrix()
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).
|
com.jom.DoubleMatrixND |
computeDemand2PathAssignmentMatrix()
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).
|
com.jom.DoubleMatrixND |
computeLink2PathAssignmentMatrix()
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).
|
List<int[]> |
computePathsPerLinkSublist(int[] pathIds)
For the set of paths provided, computes the map which provides for each
link, the paths traversing the link.
|
int[] |
computeShortestPathsForDemand(int d,
double[] weightPerLink)
Returns the path identifiers of the shortest path for a given demand.
|
double[] |
computeSpWeightPerDemand(double[] weightPerLink)
Returns the shortest path cost for every demand.
|
double[] |
computeTrafficCarriedPerDemand(double[] x_p)
Computes the amount of traffic carried for each demand, if each path
carries the traffic given in x_p vector
|
double[] |
computeTrafficInEachLink(double[] x_p)
Computes the amount of traffic in each link, if each path carries the
traffic given in x_p vector
|
double[] |
computeWeightPerPath(double[] weightPerLink)
Computes the weight of each path in the list, for the given weight of the
links.
|
int |
getDemandId(int p)
Obtains the demand associated to the path
|
int[] |
getDemandIdsPerPath()
Obtains a vector with the demands associated to each path (the path id is the index)
|
int |
getNumberOfPaths()
Returns the number of paths in the list
|
List<Integer> |
getPath(int p)
Obtains the path object associated to identifier p
|
double |
getPathCost(int p,
double[] weightPerLink)
Returns the cost of a path, given a set of link weights
|
int[] |
getPathsPerDemand(int d)
Returns the array of identifiers of the paths that are associated to this
demand
|
int[] |
getPathsPerDemandAndLink(int d,
int e)
Returns the array of identifiers of the paths of demand d that traverse
link e
|
int[] |
getPathsPerLink(int e)
Returns the array of identifiers of the paths that traverse this link
|
int[] |
getSequenceOfLinks(int p)
Obtains the sequence of links of path p
|
int[] |
getSequenceOfNodes(int p)
Obtains the sequence of links of path p
|
int[] |
getShortestPathsPerDemand(double[] weightPerLink,
double[] outputSpCosts)
Returns the identifiers of the shortest paths for each demand, according
to the given weights.
|
boolean |
linkBelongsToPath(int e,
int p)
Checks whether a link belongs to a path.
|
void |
removePath(int p)
Removes a path from the candidate path list.
|
void |
save(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 |
public CandidatePathList(NetPlan netPlan, File f)
netPlan
- The network plan, containing at least the nodes, links and
demands in the network. Routes already defined will be ommittedf
- File containing a previously computed CandidatePathList
public CandidatePathList(NetPlan netPlan, String... paramValuePairs)
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.
netPlan
- The network plan, containing at least the nodes, links and
demands in the network. Routes already defined will be ommittedparamValuePairs
- 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 usedpublic CandidatePathList(NetPlan netPlan, double[] weights, String... paramValuePairs)
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.
netPlan
- The network plan, containing at least the nodes, links and
demands in the network. Routes already defined will be ommittedweights
- Link weight vector for the shortest path algorithmparamValuePairs
- 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 usedpublic CandidatePathList(NetPlan netPlan, boolean useRoutesWithinNetPlan, String... paramValuePairs)
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.
netPlan
- The network plan, containing at least the nodes, links and
demands in the network.useRoutesWithinNetPlan
- A flag to indicate whether current routes
in netPlan (if available) should be added as candidate pathsparamValuePairs
- 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 usedpublic CandidatePathList(NetPlan netPlan, boolean useRoutesWithinNetPlan, double[] weights, String... paramValuePairs)
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.
netPlan
- The network plan, containing at least the nodes, links and
demands in the network.useRoutesWithinNetPlan
- A flag to indicate whether current routes
in netPlan (if available) should be added as candidate pathsweights
- Link weight vector for the shortest path algorithmparamValuePairs
- 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 usedpublic void save(File f)
f
- Output filepublic boolean linkBelongsToPath(int e, int p)
e
- Link identifierp
- Path identifiertrue
if link e
belongs to path p
. Otherwise, false
.public int getDemandId(int p)
p
- Path identifierpublic void removePath(int p)
p
- Path identifierpublic int[] getDemandIdsPerPath()
public int getNumberOfPaths()
public List<Integer> getPath(int p)
p
- Path identifierpublic int[] getPathsPerDemand(int d)
d
- The demandpublic int addPath(int demandId, int[] seqLinks)
demandId
- Demand identifierseqLinks
- An array with the sequence of link identifierspublic int[] getPathsPerLink(int e)
e
- The link identifierpublic int[] getPathsPerDemandAndLink(int d, int e)
d
- The demand identifiere
- The link identifierpublic double[] computeTrafficInEachLink(double[] x_p)
x_p
- The traffic carried by each path in the listpublic double[] computeTrafficCarriedPerDemand(double[] x_p)
x_p
- The traffic carried by each path in the listpublic int[] getShortestPathsPerDemand(double[] weightPerLink, double[] outputSpCosts)
weightPerLink
- The weight for each linkoutputSpCosts
- If an array of a length equal to the number of
demands is passed, the costs of the shortest paths are stored therepublic com.jom.DoubleMatrixND computeDemand2LinkAssignmentMatrix()
public com.jom.DoubleMatrixND computeDemand2PathAssignmentMatrix()
public com.jom.DoubleMatrixND computeLink2PathAssignmentMatrix()
public List<int[]> computePathsPerLinkSublist(int[] pathIds)
pathIds
- The paths of interestpublic double[] computeWeightPerPath(double[] weightPerLink)
weightPerLink
- The set of weight per linkpublic double[] computeSpWeightPerDemand(double[] weightPerLink)
weightPerLink
- Link weightspublic double getPathCost(int p, double[] weightPerLink)
p
- Path identifierweightPerLink
- Link weightspublic int[] computeShortestPathsForDemand(int d, double[] weightPerLink)
d
- Demand identifierweightPerLink
- Link weightspublic int[] getSequenceOfLinks(int p)
p
- Path identifierpublic int[] getSequenceOfNodes(int p)
p
- Path identifierpublic String toString()
String
describing the paths in the list, their associated demands and sequence of linkstoString
in class Object