public class GraphUtils
extends Object
Auxiliary static methods to work with graphs.
These methods make intensive use of several Java libraries (i.e. JOM, JGraphT or JUNG) hiding low-level details to users.
Modifier and Type | Class and Description |
---|---|
static class |
GraphUtils.ClosedCycleRoutingException
Exception thrown when hop-by-hop routing includes closed cycles.
|
Modifier and Type | Method and Description |
---|---|
static void |
checkRouteContinuity(List<Link> seqLinks,
Constants.CheckRoutingCycleType checkCycles)
Checks for validity of a given path (continuity and, optionally, no loops).
|
static double |
computeEuclideanDistance(Point2D point1,
Point2D point2)
Computes the Euclidean distance between two points.
|
static double |
computeHaversineDistanceInKm(Point2D point1,
Point2D point2)
Computes the Haversine distance between two points, that is, the shortest distance over the Earth's surface.
|
static double |
computeRoadDistanceInKm(double airlineDistanceInKm)
Applies a correction to a given airline distance (i.e.
|
static Quadruple<DoubleMatrix2D,DoubleMatrix1D,DoubleMatrix1D,List<Constants.RoutingCycleType>> |
convert_fde2xde(List<Node> nodes,
List<Link> links,
List<Demand> demands,
DoubleMatrix1D h_d,
DoubleMatrix2D f_de)
Given a forwarding rule mapping (fractions of traffic entering a node from demand 'd', leaving that node through link 'e'), and an offered traffic to the network,
it generates the resulting demand-link routing in the form x_de (amount of traffic from demand d, transmitted through link e).
|
static DoubleMatrix2D |
convert_fte2fde(List<Demand> demands,
DoubleMatrix2D f_te)
Given a destination-based routing in the form f_te (fractions of traffic in a node, that is forwarded through each of its output links), it generates the resulting demand-link routing in the form f_de (fractions of traffic in a node from demand d, transmitted through link e).
|
static Quadruple<DoubleMatrix2D,DoubleMatrix1D,DoubleMatrix1D,List<Constants.RoutingCycleType>> |
convert_fte2xde(List<Node> nodes,
List<Link> links,
List<Demand> demands,
DoubleMatrix2D f_te)
Given a destination-based routing in the form f_te (fractions of traffic in a node, that is forwarded through each of its output links), and an offered traffic to the network, it generates the resulting demand-link routing in the form x_de (amount of traffic from demand d, transmitted through link e).
|
static void |
convert_fte2xp(List<Node> nodes,
List<Link> links,
List<Demand> demands,
DoubleMatrix1D h_d,
DoubleMatrix2D f_te,
List<Demand> d_p,
List<Double> x_p,
List<List<Link>> pathList)
Given a destination-based routing in the form f_te (fractions of traffic in a node, that is forwarded through each of its
output links), and an offered traffic to the network, it generates the resulting set of paths that are produced.
|
static DoubleMatrix2D |
convert_fte2xte(List<Node> nodes,
List<Link> links,
List<Demand> demands,
DoubleMatrix2D f_te,
DoubleMatrix1D h_d)
Given a destination-based routing in the form f_te (fractions of traffic in a node, that is forwarded through each of its output links), and an offered traffic to the network, it generates the resulting destination-based routing in the form x_te (amount of traffic targeted to node t, transmitted through link e).
|
static DoubleMatrix2D |
convert_xde2fde(List<Node> nodes,
List<Link> links,
List<Demand> demands,
DoubleMatrix2D x_de)
Given a demand-link routing in the form x_de (amount of traffic from demand d, transmitted through link e), returns the equivalent forwarding rule mapping (fractions of traffic entering a node from demand 'd', leaving that node through link 'e').
|
static int |
convert_xde2xp(List<Node> nodes,
List<Link> links,
List<Demand> demands,
DoubleMatrix2D x_de,
List<Demand> d_p,
List<Double> x_p,
List<List<Link>> pathList)
Converts the routing in the form x_de into a set of loopless routes.
|
static DoubleMatrix2D |
convert_xde2xte(List<Node> nodes,
List<Link> links,
List<Demand> demands,
DoubleMatrix2D x_de)
Given a demand-link routing in the form x_de (amount of traffic from demand d, transmitted through link e), returns the equivalent forwarding rule mapping (fractions of traffic entering a node from demand 'd', leaving that node through link 'e').
|
static DoubleMatrix1D |
convert_xde2ye(DoubleMatrix2D x_de)
Returns the carried traffic per link.
|
static DoubleMatrix2D |
convert_xp2fte(List<Node> nodes,
List<Link> links,
List<Demand> demands,
List<Route> routes)
Given a set of traffic routes and their carried traffic returns a destination-based routing in the form fte (fractions of traffic in a node, that is forwarded through each of its output links).
|
static DoubleMatrix2D |
convert_xp2xde(List<Link> links,
List<Demand> demands,
List<Route> routes)
Given a path-based routing, returns the amount of traffic for each demand d traversing each link e.
|
static DoubleMatrix2D |
convert_xp2xte(List<Node> nodes,
List<Link> links,
List<Demand> demands,
List<Route> routes)
Given a set of traffic routes and their carried traffic returns a destination-based routing in the form x_te (amount of traffic targeted to node t, transmitted through link e).
|
static DoubleMatrix1D |
convert_xp2ye(List<Link> links,
List<Route> routes)
Returns the carried traffic per link.
|
static DoubleMatrix2D |
convert_xte2fte(List<Node> nodes,
List<Link> links,
DoubleMatrix2D x_te)
Given a destination-based routing in the form of an array x_te (amount of traffic targeted to node t, transmitted through link e), it returns the associated destination-based routing in the form of fractions f_te (fraction of the traffic targeted to node t that arrives (or is generated in) node a(e) (the initial node of link e), that is forwarded through link e).
|
static DoubleMatrix1D |
convert_xte2ye(DoubleMatrix2D x_te)
Returns the carried traffic per link.
|
static double |
convertPath2PathCost(List<Link> seqLinks,
DoubleMatrix1D linkCostMap)
Returns the total cost for a given path, which is equal to the sum of the cost of each traversed link.
|
static List<Double> |
convertPathList2PathCost(List<List<Link>> pathList,
DoubleMatrix1D linkCostMap)
Returns the total cost for a given a list of paths.
|
static List<Node> |
convertSequenceOfLinksToSequenceOfNodes(List<Link> seqLinks)
Converts a given sequence of links to the corresponding sequence of nodes.
|
static DoubleMatrix2D |
getAdjacencyMatrix(List<Node> nodes,
List<? extends NetworkElement> linkMap)
Given a map of links, it computes the adjacency matrix.
|
static List<List<Link>> |
getAllLooplessShortestPaths(List<Node> nodes,
List<Link> links,
Node originNode,
Node destinationNode,
Map<Link,Double> linkCostMap)
Returns all the loopless shortest paths between two nodes.
|
static DoubleMatrix2D |
getBidirectionalMatrix(List<Node> nodes,
List<Link> linkMap)
Given a map of links representing a bidirectional topology, with the same number of links on each direction for each node pair, it bundles into opposite link pairs and computes the bidirectional matrix.
|
static List<Link> |
getCapacitatedShortestPath(Collection<Node> nodes,
Collection<Link> links,
Node originNode,
Node destinationNode,
Map<Link,Double> linkCostMap,
Map<Link,Double> linkSpareCapacityMap,
double capacityGoal) |
static DoubleMatrix2D |
getIncidenceMatrix(List<Node> nodes,
List<? extends NetworkElement> elements)
Given a list of Network Elements, it computes the node-network element incidence matrix.
|
static DoubleMatrix2D |
getIncomingIncidenceMatrix(List<Node> nodes,
List<? extends NetworkElement> elements)
Given a list of Network Element, it computes the node-network element incoming incidence matrix.
|
static List<List<Link>> |
getKLooplessShortestPaths(List<Node> nodes,
List<Link> links,
Node originNode,
Node destinationNode,
Map<Link,Double> linkCostMap,
int K,
double maxLengthInKm,
int maxNumHops,
double maxPropDelayInMs,
double maxRouteCost,
double maxRouteCostFactorRespectToShortestPath,
double maxRouteCostRespectToShortestPath)
Returns the K-loopless shortest paths between two nodes, satisfying some user-defined constraints.
|
static List<Set<Link>> |
getKMinimumCostMulticastTrees(List<Link> links,
Node originNode,
Set<Node> destinationNodes,
DoubleMatrix2D Aout_ne,
DoubleMatrix2D Ain_ne,
DoubleMatrix1D linkCost,
String solverName,
String solverLibraryName,
double maxSolverTimeInSecondsPerTree,
int K,
int maxCopyCapability,
double maxE2ELengthInKm,
int maxE2ENumHops,
double maxE2EPropDelayInMs,
double maxTreeCost,
double maxTreeCostFactorRespectToMinimumCostTree,
double maxTreeCostRespectToMinimumCostTree)
Returns the K-minimum cost multicast trees starting in the originNode and ending in the set destinationNodes, satisfying some user-defined constraints.
|
static Set<Link> |
getMinimumCostMulticastTree(List<Link> links,
DoubleMatrix2D Aout_ne,
DoubleMatrix2D Ain_ne,
DoubleMatrix1D linkCost,
Node originNode,
Set<Node> destinationNodes,
int maxCopyCapability,
int maxE2ENumHops,
double maxE2ELengthInKm,
double maxE2EPropDelayInMs,
String solverName,
String solverLibraryName,
double maxSolverTimeInSeconds,
String... solverParam) |
static DoubleMatrix2D |
getOutgoingIncidenceMatrix(List<Node> nodes,
List<? extends NetworkElement> elements)
Given a list of Network elements, it computes the node-network element outgoing incidence matrix.
|
static List<Link> |
getShortestPath(Collection<Node> nodes,
Collection<Link> links,
Node originNode,
Node destinationNode,
Map<Link,Double> linkCostMap)
Obtains the sequence of links representing the (unidirectional) shortest path between two nodes.
|
static List<List<Link>> |
getTwoLinkDisjointPaths(Collection<Node> nodes,
Collection<Link> links,
Node originNode,
Node destinationNode,
Map<Link,Double> linkCostMap)
Returns the shortest pair of link-disjoint paths, where each item represents a path.
|
static List<List<Link>> |
getTwoNodeDisjointPaths(Collection<Node> nodes,
Collection<Link> links,
Node originNode,
Node destinationNode,
Map<Link,Double> linkCostMap)
Returns the shortest pair of node-disjoint paths, where each item represents a path.
|
static boolean |
isBidirectional(List<Node> nodes,
List<Link> links)
Checks whether the physical topology has the same number of links between each node pair in both directions (assuming multi-digraphs).
|
static boolean |
isConnected(List<Node> nodes,
List<Link> links)
Check whether the physical topology is connected, that is, if it is possible to connect every node to each other, but only in a subset of nodes (subgraph).
|
static boolean |
isSimple(List<Node> nodes,
List<Link> links)
Check whether the physical topology is simple, that is, if it has at most one unidirectional link from a node to each other.
|
static boolean |
isWeightedBidirectional(List<Node> nodes,
List<? extends NetworkElement> elements,
DoubleMatrix1D linkCostMap)
Checks whether the physical topology has the same number of links/demands between each node pair in both directions (assuming multi-digraphs) and same weights per direction.
|
static DoubleMatrix2D |
removeCyclesFrom_xde(List<Node> nodes,
List<Link> links,
List<Demand> demands,
DoubleMatrix2D x_de,
boolean xdeAsFractionRespecttoDemandOfferedTraffic,
String solverName,
String solverLibraryName,
double maxSolverTimeInSecondsPerDemand)
Removes open or closed cycles from the x_de routing matrix, for the given set of demands.
|
static DoubleMatrix2D |
removeCyclesFrom_xte(List<Node> nodes,
List<Link> links,
DoubleMatrix2D trafficMatrix,
DoubleMatrix2D x_te,
String solverName,
String solverLibraryName,
double maxSolverTimeInSecondsPerDestination)
Removes open or closed cycles from the x_de routing matrix, for the given set of demands.
|
static DoubleMatrix1D |
simplifyLinkMap(List<Link> links,
DoubleMatrix1D linkCostMap)
Given a list of links that may contain multiple links between some node pairs, returns a matrix where appears, for each node pair, the link having the lowest weight (links whose weight is equal to
Double.MAX_VALUE are included). |
public static void checkRouteContinuity(List<Link> seqLinks, Constants.CheckRoutingCycleType checkCycles)
Checks for validity of a given path (continuity and, optionally, no loops).
seqLinks
- Sequence of traversed linkscheckCycles
- Indicates whether (and how) or not to check if there are cyclespublic static double computeEuclideanDistance(Point2D point1, Point2D point2)
point1
- Point 1point2
- Point 2public static double computeHaversineDistanceInKm(Point2D point1, Point2D point2)
Important: It is assumed an Earth's radius equal to Constants.EARTH_RADIUS_IN_KM
Important: Coordinates are assumed to be given in degress, conversions to radians are made internally.
point1
- Point 1 (x-coord is equal to longitude, y-coord is equal to latitude)point2
- Point 2 (x-coord is equal to longitude, y-coord is equal to latitude)public static double computeRoadDistanceInKm(double airlineDistanceInKm)
airlineDistanceInKm
- Airline distance in km (i.e. Euclidean distance, Haversine distance...)public static Quadruple<DoubleMatrix2D,DoubleMatrix1D,DoubleMatrix1D,List<Constants.RoutingCycleType>> convert_fde2xde(List<Node> nodes, List<Link> links, List<Demand> demands, DoubleMatrix1D h_d, DoubleMatrix2D f_de)
ClosedCycleRoutingException
is thrownnodes
- List of nodeslinks
- List of linksdemands
- List of demandsh_d
- The amount of traffic offered for each demandf_de
- For each demand d (d = 0 refers to the first demand index, d = 1 refers to the second one, and so on), and each link e (e = 0 refers to the first link index, e = 1 refers to the second one, and so on), f_de[d][e]
sets the fraction of the traffic from demand d that arrives (or is generated in) node a(e) (the origin node of link e), that is forwarded through link e. It must hold that for every node n different of b(d), the sum of the fractions fde along its outgoing links must be lower or equal than 1 (unchecked)public static DoubleMatrix2D convert_fte2fde(List<Demand> demands, DoubleMatrix2D f_te)
demands
- List of demandsf_te
- For each destination node t (t = 0 refers to the first node index, t = 1 refers to the second one, and so on), and each link e (e = 0 refers to the first link index, e = 1 refers to the second one, and so on), f_te[t][e]
sets the fraction of the traffic targeted to node t that arrives (or is generated in) node a(e) (the origin node of link e), that is forwarded through link e. It must hold that for every node n different of t, the sum of the fractions fte along its outgoing links must be lower or equal than 1 (unchecked)public static Quadruple<DoubleMatrix2D,DoubleMatrix1D,DoubleMatrix1D,List<Constants.RoutingCycleType>> convert_fte2xde(List<Node> nodes, List<Link> links, List<Demand> demands, DoubleMatrix2D f_te)
ClosedCycleRoutingException
is thrownnodes
- List of nodeslinks
- List of linksdemands
- List of demandsf_te
- For each destination node t and each link e, f_te[t][e]
sets the fraction of the traffic targeted to node t that arrives (or is generated in) node a(e) (the origin node of link e), that is forwarded through link e. It must hold that for every node n different of t, the sum of the fractions fte along its outgoing links must be lower or equal than 1 (unchecked)public static void convert_fte2xp(List<Node> nodes, List<Link> links, List<Demand> demands, DoubleMatrix1D h_d, DoubleMatrix2D f_te, List<Demand> d_p, List<Double> x_p, List<List<Link>> pathList)
ClosedCycleRoutingException
is thrown. If the
routing has open cycles, they are removed from the routes, so that for every demand, the new routing uses the same or less
bandwidth in the traversed links.nodes
- List of nodes Net2Plan
objectlinks
- List of linksdemands
- List of demandsh_d
- The amount of traffic offered for each demandf_te
- For each destination node t (t = 0 refers to the first node in nodeIds
, t = 1 refers to the second one, and so on), and each link e (e = 0 refers to the first link in linkMap.keySet()
, e = 1 refers to the second one, and so on), f_te[t][e]
sets the fraction of the traffic targeted to node t that arrives (or is generated in) node a(e) (the origin node of link e), that is forwarded through link e. It must hold that for every node n different of t, the sum of the fractions fte along its outgoing links must be lower or equal than 1 (unchecked)d_p
- (Output parameter) Demand corresponding to each path. User should pass a initialized List
object (i.e. LinkedList
or ArrayList
)x_p
- (Output parameter) Carried traffic per path. User should pass a initialized List
object (i.e. LinkedList
or ArrayList
)pathList
- (Output parameter) List of paths, where each path is represented by its sequence of traversed links. User should pass a initialized List
object (i.e. LinkedList
or ArrayList
)public static DoubleMatrix2D convert_fte2xte(List<Node> nodes, List<Link> links, List<Demand> demands, DoubleMatrix2D f_te, DoubleMatrix1D h_d)
ClosedCycleRoutingException
is thrownnodes
- List of nodeslinks
- List of linksdemands
- List of demandsh_d
- The amount of traffic offered for each demandf_te
- For each destination node t (t = 0 refers to the first node index, t = 1 refers to the second one, and so on), and each link e (e = 0 refers to the first link index, e = 1 refers to the second one, and so on), f_te[t][e]
sets the fraction of the traffic targeted to node t that arrives (or is generated in) node a(e) (the origin node of link e), that is forwarded through link e. It must hold that for every node n different of t, the sum of the fractions fte along its outgoing links must be lower or equal than 1 (unchecked)public static DoubleMatrix2D convert_xde2fde(List<Node> nodes, List<Link> links, List<Demand> demands, DoubleMatrix2D x_de)
nodes
- List of nodeslinks
- List of linksdemands
- List of demandsx_de
- Demand-link routing in the form x_de (amount of traffic from demand d, transmitted through link e)public static int convert_xde2xp(List<Node> nodes, List<Link> links, List<Demand> demands, DoubleMatrix2D x_de, List<Demand> d_p, List<Double> x_p, List<List<Link>> pathList)
nodes
- List of nodeslinks
- List of linksdemands
- List of demandsx_de
- Demand-link routing in the form x_de (amount of traffic from demand d, transmitted through link e)d_p
- (Output parameter) Demand corresponding to each path. User should pass a initialized List
object (i.e. LinkedList
or ArrayList
)x_p
- (Output parameter) Carried traffic per path. User should pass a initialized List
object (i.e. LinkedList
or ArrayList
)pathList
- (Output parameter) List of paths, where each path is represented by its sequence of traversed links. User should pass a initialized List
object (i.e. LinkedList
or ArrayList
)public static DoubleMatrix2D convert_xde2xte(List<Node> nodes, List<Link> links, List<Demand> demands, DoubleMatrix2D x_de)
nodes
- List of nodeslinks
- List of linksdemands
- List of demandsx_de
- Demand-link routing in the form x_de (amount of traffic from demand d, transmitted through link e)public static DoubleMatrix1D convert_xde2ye(DoubleMatrix2D x_de)
x_de
- Demand-link routing in the form x_de (amount of traffic from demand d, transmitted through link e)public static DoubleMatrix2D convert_xp2fte(List<Node> nodes, List<Link> links, List<Demand> demands, List<Route> routes)
nodes
- List of nodeslinks
- List of linksdemands
- List of demandsroutes
- List of routespublic static DoubleMatrix2D convert_xp2xde(List<Link> links, List<Demand> demands, List<Route> routes)
links
- List of linksdemands
- List of demandsroutes
- List of rutespublic static DoubleMatrix2D convert_xp2xte(List<Node> nodes, List<Link> links, List<Demand> demands, List<Route> routes)
nodes
- List of nodeslinks
- List of linksdemands
- List of demandsroutes
- List of routespublic static DoubleMatrix1D convert_xp2ye(List<Link> links, List<Route> routes)
links
- List of linksroutes
- List of routespublic static DoubleMatrix2D convert_xte2fte(List<Node> nodes, List<Link> links, DoubleMatrix2D x_te)
nodes
- List of nodeslinks
- List of linksx_te
- For each destination node t (t = 0 refers to the first node in nodeIds
, t = 1 refers to the second one, and so on), and each link e (e = 0 refers to the first link in linkMap.keySet()
, e = 1 refers to the second one, and so on), f_te[t][e]
represents the traffic targeted to node t that arrives (or is generated in) node a(e) (the origin node of link e), that is forwarded through link epublic static DoubleMatrix1D convert_xte2ye(DoubleMatrix2D x_te)
x_te
- For each destination node t (t = 0 refers to the first node in nodeIds
, t = 1 refers to the second one, and so on), and each link e (e = 0 refers to the first link in linkMap.keySet()
, e = 1 refers to the second one, and so on), f_te[t][e]
represents the traffic targeted to node t that arrives (or is generated in) node a(e) (the origin node of link e), that is forwarded through link epublic static double convertPath2PathCost(List<Link> seqLinks, DoubleMatrix1D linkCostMap)
seqLinks
- Sequence of traversed linkslinkCostMap
- Cost per link arraypublic static List<Double> convertPathList2PathCost(List<List<Link>> pathList, DoubleMatrix1D linkCostMap)
pathList
- List of paths, where each path is represented by its sequence of traversed linkslinkCostMap
- Cost per link arraypublic static List<Node> convertSequenceOfLinksToSequenceOfNodes(List<Link> seqLinks)
seqLinks
- Sequence of traversed linkspublic static DoubleMatrix2D getAdjacencyMatrix(List<Node> nodes, List<? extends NetworkElement> linkMap)
Given a map of links, it computes the adjacency matrix. This is a matrix with as many rows and columns as nodes. Position (i,j) accounts for the number of links/demands/paths from node i (i = 0 refers to the first node in nodeIds
, i = 1 refers to the second one, and so on) to node j (j = 0 refers to the first node in nodeIds
, j = 1 refers to the second one, and so on).
The output is in the sparse DoubleMatrix2D
format, so that could be directly used along with the JOM library in order to solve optimization problems.
For users not interested in this format, a classical dense double[][]
matrix could be obtained via the command:
double[][] matrix = getAdjacencyMatrix(nodeIds, linkMap).toArray();
nodes
- List of nodeslinkMap
- Map of links, where the key is the unique link identifier and the value is a Pair
representing the origin node and the destination node of the link, respectivelypublic static List<List<Link>> getAllLooplessShortestPaths(List<Node> nodes, List<Link> links, Node originNode, Node destinationNode, Map<Link,Double> linkCostMap)
nodes
- List of nodeslinks
- List of linksoriginNode
- Origin nodedestinationNode
- Destination nodelinkCostMap
- Cost per link, where the key is the link identifier and the value is the cost of traversing the link. No special iteration-order (i.e. ascending) is requiredpublic static DoubleMatrix2D getBidirectionalMatrix(List<Node> nodes, List<Link> linkMap)
Given a map of links representing a bidirectional topology, with the same number of links on each direction for each node pair, it bundles into opposite link pairs and computes the bidirectional matrix. This is a matrix with as many rows as opposite link pairs (or bidirectional links) and columns as links. For each bidirectional link i, position (i,j) is equal to 1 for link j (e = 0 refers to the first link in linkMap.keySet()
, e = 1 refers to the second one, and so on) in one direction, -1 for the link j in the opposite direction, and zero otherwise. By convention, the selection order of links for each bidirectional link is given by the following scheme: first, for each node i (in ascending order), it iterates over all node j (in ascending order); then, for each node pair (i, j) it retrieves the identifiers of links from i to j, and viceversa. Finally, it adds a new row to the matrix for each bidirectional link consisting of a link from i to j and another one in the opposite direction (also, in ascending order).
The output is in the sparse DoubleMatrix2D
format, so that could be directly used along with the JOM library in order to solve optimization problems.
For users not interested in this format, a classical dense double[][]
matrix could be obtained via the command:
double[][] matrix = getBidirectionalMatrix(nodeIds, linkMap).toArray();
nodes
- List of nodeslinkMap
- Map of links, where the key is the unique link identifier and the value is a Pair
representing the origin node and the destination node of the link, respectively. It is mandatory that can be iterated in ascending order of link identifier (i.e. using TreeMap
or those Map
objects returned from Net2Plan
objectpublic static List<Link> getCapacitatedShortestPath(Collection<Node> nodes, Collection<Link> links, Node originNode, Node destinationNode, Map<Link,Double> linkCostMap, Map<Link,Double> linkSpareCapacityMap, double capacityGoal)
nodes
- List of nodeslinks
- List of linksoriginNode
- Origin nodedestinationNode
- Destination nodelinkCostMap
- Cost per link, where the key is the link identifier and the value is the cost of traversing the link. No special iteration-order (i.e. ascending) is required. If null
all the links have a weight of one.linkSpareCapacityMap
- Current available capacity per link, where the key is the link identifier and the value is the cost of traversing the link. No special iteration-order (i.e. ascending) is required. If null
the spare capacity of each link is its capacity minus its carried traffic (summing the regular traffic and the ones in the protection segments), truncated to zero (negative values are not admitted).capacityGoal
- Minimum capacity requiredpublic static DoubleMatrix2D getIncidenceMatrix(List<Node> nodes, List<? extends NetworkElement> elements)
Given a list of Network Elements, it computes the node-network element incidence matrix. This is a matrix with as many rows as nodes, and as many columns as elements. Position (n, e) has a 1 if element e (e = 0 refers to the first element}, e = 1 refers to the second one, and so on) is initiated in node n (n = 0 refers to the first node , n = 1 refers to the second one, and so on), -1 if it ends in node n, and 0 otherwise.
nodes
- List of nodeselements
- List of elementsNetworkLayer
public static DoubleMatrix2D getIncomingIncidenceMatrix(List<Node> nodes, List<? extends NetworkElement> elements)
Given a list of Network Element, it computes the node-network element incoming incidence matrix. This is a matrix with as many rows as nodes, and as many columns as network elements. Position (n, e) has a 1 if element e (e = 0 refers to the first element n elements
, e = 1 refers to the second one, and so on) is terminated in node n (n = 0 refers to the first node in nodes
, n = 1 refers to the second one, and so on), and 0 otherwise.
nodes
- List of nodeselements
- List of Network ElementsNetworkLayer
public static List<List<Link>> getKLooplessShortestPaths(List<Node> nodes, List<Link> links, Node originNode, Node destinationNode, Map<Link,Double> linkCostMap, int K, double maxLengthInKm, int maxNumHops, double maxPropDelayInMs, double maxRouteCost, double maxRouteCostFactorRespectToShortestPath, double maxRouteCostRespectToShortestPath)
nodes
- List of nodeslinks
- List of linksoriginNode
- Origin nodedestinationNode
- Destination nodelinkCostMap
- Cost per link, where the key is the link identifier and the value is the cost of traversing the link. No special iteration-order (i.e. ascending) is required. If null
, all links have weight oneK
- Desired nummber of paths (a lower number of paths may be returned if there are less than K
loop-less paths admissible)maxLengthInKm
- Maximum length of the path. If non-positive, no maximum limit is assumedmaxNumHops
- Maximum number of hops. If non-positive, no maximum limit is assumedmaxPropDelayInMs
- Maximum propagation delay of the path. If non-positive, no maximum limit is assumedmaxRouteCost
- Maximum route cost. If non-positive, no maximum limit is assumedmaxRouteCostFactorRespectToShortestPath
- Maximum route cost factor respect to the shortest path. If non-positive, no maximum limit is assumedmaxRouteCostRespectToShortestPath
- Maximum route cost respect to the shortest path. If non-positive, no maximum limit is assumedpublic static List<Set<Link>> getKMinimumCostMulticastTrees(List<Link> links, Node originNode, Set<Node> destinationNodes, DoubleMatrix2D Aout_ne, DoubleMatrix2D Ain_ne, DoubleMatrix1D linkCost, String solverName, String solverLibraryName, double maxSolverTimeInSecondsPerTree, int K, int maxCopyCapability, double maxE2ELengthInKm, int maxE2ENumHops, double maxE2EPropDelayInMs, double maxTreeCost, double maxTreeCostFactorRespectToMinimumCostTree, double maxTreeCostRespectToMinimumCostTree)
links
- the network linksoriginNode
- the origin node of all the multicast treesdestinationNodes
- the set of destination nodes of all the multicast treesAout_ne
- the outgoing incidence matrix: a matrix with one row per node, and one column per link. Coordinate (n,e) is 1 if link e is an outgoing link of node n, and 0 otherwise.Ain_ne
- the incoming incidence matrix: a matrix with one row per node, and one column per link. Coordinate (n,e) is 1 if link e is an incoming link of node n, and 0 otherwise.linkCost
- the cost to be associated to each linksolverName
- the name of the solver to call for the internal formulation of the algorithmsolverLibraryName
- the solver library namemaxSolverTimeInSecondsPerTree
- the maximum time the solver is allowed for each of the internal formulations (one for each new tree). The best solution found so far is returned. If non-positive, no time limit is setK
- Desired nummber of trees (a lower number of trees may be returned if there are less than K
multicast trees admissible)maxCopyCapability
- the maximum number of copies of an input traffic a node can make. Then, a node can have at most this number of ouput links carrying traffic of a multicast treemaxE2ELengthInKm
- Maximum path length measured in kilometers allowed for any tree, from the origin node, to any destination nodemaxE2ENumHops
- Maximum number of hops allowed for any tree, from the origin node, to any destination nodemaxE2EPropDelayInMs
- Maximum propagation delay in miliseconds allowed in a path, for any tree, from the origin node, to any destination nodemaxTreeCost
- Maximum tree weight allowed, summing the weights of the linksmaxTreeCostFactorRespectToMinimumCostTree
- Trees with higher weight (cost) than the cost of the minimum cost tree, multiplied by this factor, are not returnedmaxTreeCostRespectToMinimumCostTree
- Trees with higher weight (cost) than the cost of the minimum cost tree, plus this factor, are not returned. While the previous one is a multiplicative factor, this one is an additive factorpublic static Set<Link> getMinimumCostMulticastTree(List<Link> links, DoubleMatrix2D Aout_ne, DoubleMatrix2D Ain_ne, DoubleMatrix1D linkCost, Node originNode, Set<Node> destinationNodes, int maxCopyCapability, int maxE2ENumHops, double maxE2ELengthInKm, double maxE2EPropDelayInMs, String solverName, String solverLibraryName, double maxSolverTimeInSeconds, String... solverParam)
public static DoubleMatrix2D getOutgoingIncidenceMatrix(List<Node> nodes, List<? extends NetworkElement> elements)
Given a list of Network elements, it computes the node-network element outgoing incidence matrix. This is a matrix with as many rows as nodes, and as many columns as elements. Position (n, e) has a 1 if element e (e = 0 refers to the first element, e = 1 refers to the second one, and so on) is initiated in node n (n = 0 refers to the first node , n = 1 refers to the second one, and so on), and 0 otherwise.
nodes
- List of nodeselements
- List of elementsNetworkElement
public static List<Link> getShortestPath(Collection<Node> nodes, Collection<Link> links, Node originNode, Node destinationNode, Map<Link,Double> linkCostMap)
nodes
- Collection of nodeslinks
- Collection of linksoriginNode
- Origin nodedestinationNode
- Destination nodelinkCostMap
- Cost per link, where the key is the link identifier and the value is the cost of traversing the link. No special iteration-order (i.e. ascending) is required. If null
, the shortest path in number of traversed links is returned,public static List<List<Link>> getTwoLinkDisjointPaths(Collection<Node> nodes, Collection<Link> links, Node originNode, Node destinationNode, Map<Link,Double> linkCostMap)
size()
= 1, only one path was found; and when size()
= 2, the link-disjoint paths were found. Internally it uses the Suurballe-Tarjan algorithm.nodes
- Collection of nodeslinks
- Collection of linksoriginNode
- Origin nodedestinationNode
- Destination nodelinkCostMap
- Cost per link, where the key is the link identifier and the value is the cost of traversing the link. No special iteration-order (i.e. ascending) is requiredpublic static List<List<Link>> getTwoNodeDisjointPaths(Collection<Node> nodes, Collection<Link> links, Node originNode, Node destinationNode, Map<Link,Double> linkCostMap)
size()
= 1, only one path was found; and when size()
= 2, the node-disjoint paths were found. Internally it uses the Suurballe-Tarjan algorithm.nodes
- Collection of nodeslinks
- Collection of linksoriginNode
- Origin nodedestinationNode
- Destination nodelinkCostMap
- Cost per link, where the key is the link identifier and the value is the cost of traversing the link. No special iteration-order (i.e. ascending) is requiredpublic static boolean isBidirectional(List<Node> nodes, List<Link> links)
links
- List of linksnodes
- List of nodestrue
if the physical topology is bidirectional, and false otherwisepublic static boolean isConnected(List<Node> nodes, List<Link> links)
nodes
- List of nodeslinks
- List of linkstrue
if the subgraph is connected, and false otherwisepublic static boolean isSimple(List<Node> nodes, List<Link> links)
links
- List of linksnodes
- List of nodestrue
if the physical topology is simple, and false otherwisepublic static boolean isWeightedBidirectional(List<Node> nodes, List<? extends NetworkElement> elements, DoubleMatrix1D linkCostMap)
nodes
- List of nodeselements
- List of network elements (must be type Link or Demand)linkCostMap
- Cost per link, where the key is the link identifier and the value is the cost of traversing the link. No special iteration-order (i.e. ascending) is required (only used when elements
are links)true
if the physical topology is bidirectional and symmetric, and false otherwisepublic static DoubleMatrix2D removeCyclesFrom_xde(List<Node> nodes, List<Link> links, List<Demand> demands, DoubleMatrix2D x_de, boolean xdeAsFractionRespecttoDemandOfferedTraffic, String solverName, String solverLibraryName, double maxSolverTimeInSecondsPerDemand)
nodes
- List of nodeslinks
- List of linksdemands
- List of demands to which I want to remove the loopsx_de
- Demand-link routing matrix, with one row per demnad, and one column per link. Contains the traffic of demand d in link e, or the fraction of the traffic respect to the demand offered trafficxdeAsFractionRespecttoDemandOfferedTraffic
- true is the matrix is in the fractional form, false otherwisesolverName
- the name of the solver to call for the internal formulation of the algorithmsolverLibraryName
- the solver library namemaxSolverTimeInSecondsPerDemand
- the maximum time the solver is allowed for each of the internal formulations (one for each demand).public static DoubleMatrix2D removeCyclesFrom_xte(List<Node> nodes, List<Link> links, DoubleMatrix2D trafficMatrix, DoubleMatrix2D x_te, String solverName, String solverLibraryName, double maxSolverTimeInSecondsPerDestination)
nodes
- List of nodeslinks
- List of linksdemands
- List of demands to which I want to remove the loopsx_de
- Demand-link routing matrix, with one row per demnad, and one column per link. Contains the traffic of demand d in link e, or the fraction of the traffic respect to the demand offered trafficxdeAsFractionRespecttoDemandOfferedTraffic
- true is the matrix is in the fractional form, false otherwisesolverName
- the name of the solver to call for the internal formulation of the algorithmsolverLibraryName
- the solver library namemaxSolverTimeInSecondsPerDemand
- the maximum time the solver is allowed for each of the internal formulations (one for each demand).public static DoubleMatrix1D simplifyLinkMap(List<Link> links, DoubleMatrix1D linkCostMap)
Double.MAX_VALUE
are included). Ties are broken arbitrarely.links
- List of linkslinkCostMap
- Cost per link, where the key is the link identifier and the value is the cost of traversing the link. No special iteration-order (i.e. ascending) is required