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 lowlevel details to users.
Modifier and Type  Class and Description 

static class 
GraphUtils.ClosedCycleRoutingException
Exception thrown when hopbyhop routing includes closed cycles.

static class 
GraphUtils.JUNGUtils
Auxiliary class to work with the graph library JUNG.

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 Quintuple<DoubleMatrix1D,Constants.RoutingCycleType,Double,Double,Double> 
computeRoutingFundamentalVector(SortedMap<Link,Double> frs,
SortedMap<Node,SortedSet<Link>> outFrs,
Node ingressNode,
Node egressNode)
Computes the row of the fundamental matrix of the absorbing Markov chain in the current hopbyhop routing, for the
given ingress node.

static Pair<Double,Double> 
computeWorstCasePropagationDelayAndLengthInKmMsForLoopLess(SortedMap<Link,Double> frs,
SortedMap<Node,SortedSet<Link>> outFrs,
Node ingressNode,
Node egressNode)
Computes the worst case propagation delay in ms for the given forwarding rules, from the ingress to the
egress node (assuming there is traffic between the end nodes).

static Quadruple<DoubleMatrix2D,DoubleMatrix1D,DoubleMatrix1D,List<Constants.RoutingCycleType>> 
convert_fde2xde(int numNodes,
List<Link> links,
SortedSet<Demand> demandsToConvert,
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 demandlink routing in the form x_de (amount of traffic from demand d, transmitted through link e).

static DoubleMatrix2D 
convert_fte2fde(int numDemandsInLayer,
SortedSet<Demand> demandsToConvert,
DoubleMatrix2D f_te)
Given a destinationbased 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 demandlink 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(int numNodes,
int numDemandsInLayer,
List<Link> links,
SortedSet<Demand> demandsToConvert,
DoubleMatrix2D f_te)
Given a destinationbased 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 demandlink 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,
int numDemandsInLayer,
SortedSet<Demand> demandsToConvert,
DoubleMatrix1D h_d,
DoubleMatrix2D f_te,
List<Demand> d_p,
List<Double> x_p,
List<List<Link>> pathList)
Given a destinationbased 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,
SortedSet<Demand> demandsToConsider,
DoubleMatrix2D f_te,
DoubleMatrix1D h_d)
Given a destinationbased 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 destinationbased routing in the form x_te (amount of traffic targeted to node t, transmitted through link e).

static DoubleMatrix2D 
convert_xde2fde(List<Link> links,
DoubleMatrix2D x_de)
Given a demandlink 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,
Set<Demand> demandsToConvert,
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, just for the indicated demands.

static DoubleMatrix2D 
convert_xde2xte(int numNodes,
SortedSet<Demand> demandsToConsider,
DoubleMatrix2D x_de)
Given a demandlink 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 SortedMap<Demand,SortedMap<Link,Double>> 
convert_xp2fdeMap(Collection<Route> routes)
Given a pathbased routing, returns the forwarding rules map: fraction of traffic for each demand incoming to the link
initial node (or produced in it) forwarded to the 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 destinationbased routing in the form f_{te} (fractions of traffic in a node, that is forwarded through each of its output links).

static DoubleMatrix2D 
convert_xp2xde(int D,
int E,
List<Route> routes)
Given a pathbased 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 destinationbased 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 destinationbased routing in the form of an array x_te (amount of traffic targeted to node t, transmitted through link e), it returns the associated destinationbased 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,
SortedMap<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,
SortedMap<Link,Double> linkCostMap,
SortedMap<Link,Double> linkSpareCapacityMap,
double capacityGoal) 
static List<Set<Node>> 
getConnectedComponents(Collection<Node> nodes,
List<Link> links)
Returns the connected components of the given graph

static DoubleMatrix2D 
getIncidenceMatrix(List<Node> nodes,
List<? extends NetworkElement> elements)
Given a list of Network Elements, it computes the nodenetwork element incidence matrix.

static DoubleMatrix2D 
getIncomingIncidenceMatrix(List<Node> nodes,
List<? extends NetworkElement> elements)
Given a list of Network Element, it computes the nodenetwork 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 Kloopless shortest paths between two nodes, satisfying some userdefined constraints.

static List<SortedSet<Link>> 
getKMinimumCostMulticastTrees(NetworkLayer layer,
Node originNode,
SortedSet<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 Kminimum cost multicast trees starting in the originNode and ending in the set destinationNodes, satisfying some userdefined constraints.

static List<Pair<List<NetworkElement>,Double>> 
getKMinimumCostServiceChains(List<Link> links,
Node originNode,
Node destinationNode,
List<String> sequenceOfResourceTypesToTraverse,
DoubleMatrix1D linkCost,
Map<Resource,Double> resourceCost,
int K,
double maxCostServiceChain,
double maxLengthInKmPerSubpath,
int maxNumHopsPerSubpath,
double maxPropDelayInMsPerSubpath,
Map<Pair<Node,Node>,List<Pair<List<Link>,Double>>> cacheSubpathLists)
Returns the K minimum cost service chains between two nodes (summing costs of links and resources traversed), traversing a given set of resource types, satisfying some userdefined constraints.

static SortedSet<Link> 
getMinimumCostMulticastTree(NetworkLayer layer,
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 Pair<List<NetworkElement>,Double> 
getMinimumCostServiceChain(List<Link> links,
Node originNode,
Node destinationNode,
List<String> sequenceOfResourceTypesToTraverse,
DoubleMatrix1D linkCost,
Map<Resource,Double> resourceCost,
double maxLengthInKmPerSubpath,
int maxNumHopsPerSubpath,
double maxPropDelayInMsPerSubpath)
Returns the minimum cost service chain between two nodes (summing costs of links and resources traversed), traversing a given set of resource types, satisfying some userdefined constraints.

static DoubleMatrix2D 
getOutgoingIncidenceMatrix(List<Node> nodes,
List<? extends NetworkElement> elements)
Given a list of Network elements, it computes the nodenetwork 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 linkdisjoint paths, where each item represents a path.

static List<List<Link>> 
getTwoMaximumLinkAndNodeDisjointPaths(Collection<Node> nodes,
Collection<Link> links,
Node originNode,
Node destinationNode,
SortedMap<Link,Double> linkCostMap) 
static List<List<Link>> 
getTwoNodeDisjointPaths(Collection<Node> nodes,
Collection<Link> links,
Node originNode,
Node destinationNode,
SortedMap<Link,Double> linkCostMap)
Returns the shortest pair of nodedisjoint 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 multidigraphs).

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 multidigraphs) and same weights per direction.

static DoubleMatrix2D 
removeCyclesFrom_xde(int numNodes,
List<Link> links,
Set<Demand> demandsToConsider,
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 (xcoord is equal to longitude, ycoord is equal to latitude)point2
 Point 2 (xcoord is equal to longitude, ycoord is equal to latitude)public static double computeRoadDistanceInKm(double airlineDistanceInKm)
airlineDistanceInKm
 Airline distance in km (i.e. Euclidean distance, Haversine distance...)public static Quintuple<DoubleMatrix1D,Constants.RoutingCycleType,Double,Double,Double> computeRoutingFundamentalVector(SortedMap<Link,Double> frs, SortedMap<Node,SortedSet<Link>> outFrs, Node ingressNode, Node egressNode)
Computes the row of the fundamental matrix of the absorbing Markov chain in the current hopbyhop routing, for the given ingress node.
Returns a Triple
object where:
frs
 the forwarding rules applicableoutFrs
 output forwarding ruleingressNode
 the ingress nodeegressNode
 the egress nodepublic static Pair<Double,Double> computeWorstCasePropagationDelayAndLengthInKmMsForLoopLess(SortedMap<Link,Double> frs, SortedMap<Node,SortedSet<Link>> outFrs, Node ingressNode, Node egressNode)
frs
 forwarding rules to applyoutFrs
 if not null, provides information on the forwarding rules that can exist outgoing from each node (useful for improving the running time)ingressNode
 ingress nodeegressNode
 egress nodepublic static Quadruple<DoubleMatrix2D,DoubleMatrix1D,DoubleMatrix1D,List<Constants.RoutingCycleType>> convert_fde2xde(int numNodes, List<Link> links, SortedSet<Demand> demandsToConvert, DoubleMatrix1D h_d, DoubleMatrix2D f_de)
ClosedCycleRoutingException
is thrownnumNodes
 Number of nodeslinks
 List of linksdemandsToConvert
 List of demands to converth_d
 The amount of traffic offered for each demand, a vector of as many elements as demands in the layerf_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 f_{de} along its outgoing links must be lower or equal than 1 (unchecked)public static DoubleMatrix2D convert_fte2fde(int numDemandsInLayer, SortedSet<Demand> demandsToConvert, DoubleMatrix2D f_te)
numDemandsInLayer
 Number of demands in the layer.demandsToConvert
 List of demands in the layer to apply conversion, the rest are untouchedf_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 f_{te} along its outgoing links must be lower or equal than 1 (unchecked)public static Quadruple<DoubleMatrix2D,DoubleMatrix1D,DoubleMatrix1D,List<Constants.RoutingCycleType>> convert_fte2xde(int numNodes, int numDemandsInLayer, List<Link> links, SortedSet<Demand> demandsToConvert, DoubleMatrix2D f_te)
ClosedCycleRoutingException
is thrownnumNodes
 Number of nodesnumDemandsInLayer
 Number of demand in the layerlinks
 List of linksdemandsToConvert
 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 f_{te} along its outgoing links must be lower or equal than 1 (unchecked)public static void convert_fte2xp(List<Node> nodes, List<Link> links, int numDemandsInLayer, SortedSet<Demand> demandsToConvert, 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 linksnumDemandsInLayer
 Number of demands in the layerh_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 f_{te} 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
)demandsToConvert
 List of demandspublic static DoubleMatrix2D convert_fte2xte(List<Node> nodes, List<Link> links, SortedSet<Demand> demandsToConsider, DoubleMatrix2D f_te, DoubleMatrix1D h_d)
ClosedCycleRoutingException
is thrownnodes
 List of nodeslinks
 List of linksdemandsToConsider
 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 f_{te} along its outgoing links must be lower or equal than 1 (unchecked)public static DoubleMatrix2D convert_xde2fde(List<Link> links, DoubleMatrix2D x_de)
links
 List of linksx_de
 Demandlink 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, Set<Demand> demandsToConvert, DoubleMatrix2D x_de, List<Demand> d_p, List<Double> x_p, List<List<Link>> pathList)
nodes
 List of nodeslinks
 List of linksdemandsToConvert
 List of demandsx_de
 Demandlink routing in the form x_de (amount of traffic from demand d, transmitted through link e), one row for each demand in layer (can be more than the demands in the matrix)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(int numNodes, SortedSet<Demand> demandsToConsider, DoubleMatrix2D x_de)
numNodes
 Number of nodesdemandsToConsider
 List of demandsx_de
 Demandlink 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
 Demandlink routing in the form x_de (amount of traffic from demand d, transmitted through link e)public static SortedMap<Demand,SortedMap<Link,Double>> convert_xp2fdeMap(Collection<Route> routes)
routes
 List of routespublic 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(int D, int E, List<Route> routes)
E
 Number of linksD
 Number of demandsroutes
 List of routespublic 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
 SortedMap 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, SortedMap<Link,Double> linkCostMap)
Double.MAX_VALUE
are not considered.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 iterationorder (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
 SortedMap 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 SortedMap
objects returned from Net2Plan
objectpublic static List<Link> getCapacitatedShortestPath(Collection<Node> nodes, Collection<Link> links, Node originNode, Node destinationNode, SortedMap<Link,Double> linkCostMap, SortedMap<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 iterationorder (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 iterationorder (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 List<Set<Node>> getConnectedComponents(Collection<Node> nodes, List<Link> links)
nodes
 List of nodeslinks
 List of linkspublic static DoubleMatrix2D getIncidenceMatrix(List<Node> nodes, List<? extends NetworkElement> elements)
Given a list of Network Elements, it computes the nodenetwork 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 nodenetwork 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 iterationorder (i.e. ascending) is required. If null
, all links have weight one. A value of Double.MAX_VALUE means that the link cannot be usedK
 Desired nummber of paths (a lower number of paths may be returned if there are less than K
loopless paths admissible)maxLengthInKm
 Maximum length of the path. If nonpositive, no maximum limit is assumedmaxNumHops
 Maximum number of hops. If nonpositive, no maximum limit is assumedmaxPropDelayInMs
 Maximum propagation delay of the path. If nonpositive, no maximum limit is assumedmaxRouteCost
 Maximum route cost. If nonpositive, no maximum limit is assumedmaxRouteCostFactorRespectToShortestPath
 Maximum route cost factor respect to the shortest path. If nonpositive, no maximum limit is assumedmaxRouteCostRespectToShortestPath
 Maximum route cost respect to the shortest path. If nonpositive, no maximum limit is assumedpublic static List<SortedSet<Link>> getKMinimumCostMulticastTrees(NetworkLayer layer, Node originNode, SortedSet<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)
layer
 the layer where to pick the network links. If null, picks the default layeroriginNode
 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 link. A cost equal to Double.MAX_VALUE makes the link uneligiblesolverName
 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 nonpositive, no time limit is setK
 Desired number 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 output 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 milliseconds 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 List<Pair<List<NetworkElement>,Double>> getKMinimumCostServiceChains(List<Link> links, Node originNode, Node destinationNode, List<String> sequenceOfResourceTypesToTraverse, DoubleMatrix1D linkCost, Map<Resource,Double> resourceCost, int K, double maxCostServiceChain, double maxLengthInKmPerSubpath, int maxNumHopsPerSubpath, double maxPropDelayInMsPerSubpath, Map<Pair<Node,Node>,List<Pair<List<Link>,Double>>> cacheSubpathLists)
links
 The set of links which can be used for the chainoriginNode
 The origin node of the chaindestinationNode
 The destination node of the chain (could be the same as the origin node)sequenceOfResourceTypesToTraverse
 the types of the sequence of resources to traverselinkCost
 the cost of each link (if null, all links have cost one), all numbers must be strictly positiveresourceCost
 a map with the cost of each resource (if null, all resources have cost zero). A resources with Double.MAX_VALUE cost cannot be traversed (as if it was not there). All costs must be nonnegative. If a resource is not present in the map, its cost is zero.K
 The maximum number of service chains to return (less than K may be returned if there are no different paths).maxCostServiceChain
 Service chains with a cost higher than this are not enumeratedmaxLengthInKmPerSubpath
 The maximum length in km in each subpath. Service chains not satisfying this are not enumeratedmaxNumHopsPerSubpath
 The maximum number of traversed links in each subpath. Service chains not satisfying this are not enumeratedmaxPropDelayInMsPerSubpath
 The propagation delay summing the links in each subpath. Service chains not satisfying this are not enumeratedcacheSubpathLists
 A map which associated to node pairs, the kshortest paths (only considering links) already computed to be used.
The algorithm will add new entries here for those pairs of nodes for which no percomputed values exist, and that are needed in the algorithm
(e.g. for origin node to all nodes of the first resource type, nodes of the first resource type to the second...). If null, then no entries are
precomputed AND also no new entries are returned.public static SortedSet<Link> getMinimumCostMulticastTree(NetworkLayer layer, 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 Pair<List<NetworkElement>,Double> getMinimumCostServiceChain(List<Link> links, Node originNode, Node destinationNode, List<String> sequenceOfResourceTypesToTraverse, DoubleMatrix1D linkCost, Map<Resource,Double> resourceCost, double maxLengthInKmPerSubpath, int maxNumHopsPerSubpath, double maxPropDelayInMsPerSubpath)
getKMinimumCostServiceChains(java.util.List<com.net2plan.interfaces.networkDesign.Link>, com.net2plan.interfaces.networkDesign.Node, com.net2plan.interfaces.networkDesign.Node, java.util.List<java.lang.String>, cern.colt.matrix.tdouble.DoubleMatrix1D, java.util.Map<com.net2plan.interfaces.networkDesign.Resource, java.lang.Double>, int, double, double, int, double, java.util.Map<com.net2plan.utils.Pair<com.net2plan.interfaces.networkDesign.Node, com.net2plan.interfaces.networkDesign.Node>, java.util.List<com.net2plan.utils.Pair<java.util.List<com.net2plan.interfaces.networkDesign.Link>, java.lang.Double>>>)
with parameter k = 1
(see more information in that method).links
 The set of links which can be used for the chainoriginNode
 The origin node of the chaindestinationNode
 The destination node of the chain (could be the same as the origin node)sequenceOfResourceTypesToTraverse
 the types of the sequence of resources to traverselinkCost
 the cost of each link (if null, all links have cost one), all numbers must be strictly positiveresourceCost
 a map with the cost of each resource (if null, all resources have cost zero). A resources with Double.MAX_VALUE cost cannot be traversed (as if it was not there). All costs must be nonnegative. If a resource is not present in the map, its cost is zero.maxLengthInKmPerSubpath
 The maximum length in km in each subpath. Service chains not satisfying this are not enumerated (negative number means no limit)maxNumHopsPerSubpath
 The maximum number of traversed links in each subpath. Service chains not satisfying this are not enumerated (negative number means no limit)maxPropDelayInMsPerSubpath
 The propagation delay summing the links in each subpath. Service chains not satisfying this are not enumerated (negative number means no limit)public static DoubleMatrix2D getOutgoingIncidenceMatrix(List<Node> nodes, List<? extends NetworkElement> elements)
Given a list of Network elements, it computes the nodenetwork 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)
Double.MAX_VALUE
are not considered.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 iterationorder (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 linkdisjoint paths were found.
Internally it uses the SuurballeTarjan 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 iterationorder (i.e. ascending) is requiredpublic static List<List<Link>> getTwoMaximumLinkAndNodeDisjointPaths(Collection<Node> nodes, Collection<Link> links, Node originNode, Node destinationNode, SortedMap<Link,Double> linkCostMap)
public static List<List<Link>> getTwoNodeDisjointPaths(Collection<Node> nodes, Collection<Link> links, Node originNode, Node destinationNode, SortedMap<Link,Double> linkCostMap)
size()
= 1, only one path was found;
and when size()
= 2, the nodedisjoint paths were found.
Internally it uses the SuurballeTarjan 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 iterationorder (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 iterationorder (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(int numNodes, List<Link> links, Set<Demand> demandsToConsider, DoubleMatrix2D x_de, boolean xdeAsFractionRespecttoDemandOfferedTraffic, String solverName, String solverLibraryName, double maxSolverTimeInSecondsPerDemand)
numNodes
 Number of nodeslinks
 List of linksdemandsToConsider
 List of demands to which I want to remove the loopsx_de
 Demandlink 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 linkstrafficMatrix
 List of demands to which I want to remove the loopsx_te
 Demandlink routing matrix, with one row per demand, 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 trafficsolverName
 the name of the solver to call for the internal formulation of the algorithmsolverLibraryName
 the solver library namemaxSolverTimeInSecondsPerDestination
 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 iterationorder (i.e. ascending) is requiredCopyright © 2018. All rights reserved.