com.net2plan.libraries

Class GraphUtils

java.lang.Object

com.net2plan.libraries.GraphUtils

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.

Since:

0.2.0

See Also:

Java Optimization Modeler (JOM) website, JGraphT website, Java Universal Network/Graph Framework (JUNG) website

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
static class	GraphUtils.ClosedCycleRoutingException Exception thrown when hop-by-hop routing includes closed cycles.
static class	GraphUtils.JUNGUtils Auxiliary class to work with the graph library JUNG.

Method Summary

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 hop-by-hop 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 demand-link 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 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(int numNodes, int numDemandsInLayer, List<Link> links, SortedSet<Demand> demandsToConvert, 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, 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 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, SortedSet<Demand> demandsToConsider, 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<Link> links, 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, 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 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 SortedMap<Demand,SortedMap<Link,Double>>	convert_xp2fdeMap(Collection<Route> routes) Given a path-based 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 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(int D, int E, 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, 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 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<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 K-minimum cost multicast trees starting in the originNode and ending in the set destinationNodes, satisfying some user-defined 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 user-defined 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 user-defined constraints.
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>>	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 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(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).

Methods inherited from class java.lang.Object

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

Method Detail

checkRouteContinuity

public static void checkRouteContinuity(List<Link> seqLinks,
                                        Constants.CheckRoutingCycleType checkCycles)

Checks for validity of a given path (continuity and, optionally, no loops).

Parameters:

seqLinks - Sequence of traversed links

checkCycles - Indicates whether (and how) or not to check if there are cycles

computeEuclideanDistance

public static double computeEuclideanDistance(Point2D point1,
                                              Point2D point2)

Computes the Euclidean distance between two points.

Parameters:

point1 - Point 1

point2 - Point 2

Returns:

Euclidean distance between two points

computeHaversineDistanceInKm

public static double computeHaversineDistanceInKm(Point2D point1,
                                                  Point2D point2)

Computes the Haversine distance between two points, that is, the shortest distance over the Earth's surface.

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.

Parameters:

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)

Returns:

Haversine distance between two points

See Also:

Calculate distance, bearing and more between Latitude/Longitude points

computeRoadDistanceInKm

public static double computeRoadDistanceInKm(double airlineDistanceInKm)

Applies a correction to a given airline distance (i.e. Euclidean distance, Haversine distance...) considering cable (i.e. optical fiber) deployment issues to predict a more realistic cable length. For undersea cables, the airline distance is considered as valid.

Parameters:

airlineDistanceInKm - Airline distance in km (i.e. Euclidean distance, Haversine distance...)

Returns:

Cable length in km

See Also:

ETSI, "Network Aspects (NA): Availability performance of path elements of international digital paths," European Standard EN 300 416 V1.2.1, August 1998.

computeRoutingFundamentalVector

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 hop-by-hop routing, for the given ingress node.

Returns a Triple object where:

1. the row associated to the ingress node fundamental matrix (1xN, where N is the number of nodes)
2. the type of routing of the demand (loopless, or close cycles. Open cycles are not detected)
3. the fraction of demand traffic that arrives to the destination node and is absorbed there (it may be less than one if the routing has cycles that involve the destination node)

Parameters:

frs - the forwarding rules applicable

outFrs - output forwarding rule

ingressNode - the ingress node

egressNode - the egress node

Returns:

See description above

computeWorstCasePropagationDelayAndLengthInKmMsForLoopLess

public 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). If the traffic does not arrive to the destination, Double.MAX_VALUE is returned. The function assumes that the routing has no cycles (open nor closed). If that is not the case, results can be invalid

Parameters:

frs - forwarding rules to apply

outFrs - if not null, provides information on the forwarding rules that can exist outgoing from each node (useful for improving the running time)

ingressNode - ingress node

egressNode - egress node

Returns:

see above

convert_fde2xde

public 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 demand-link routing in the form x_de (amount of traffic from demand d, transmitted through link e). When a demand has a closed routing loop, the traffic in the link would be infinite. Then, a ClosedCycleRoutingException is thrown

Parameters:

numNodes - Number of nodes

links - List of links

demandsToConvert - List of demands to convert

h_d - The amount of traffic offered for each demand, a vector of as many elements as demands in the layer

f_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)

Returns:

Demand-link routing in the form x_de (amount of traffic from demand d, transmitted through link e), total carried traffic per demand, carried traffic per link, and routing cycle type (loopless, with open cycles...) per demand

convert_fte2fde

public static DoubleMatrix2D convert_fte2fde(int numDemandsInLayer,
                                             SortedSet<Demand> demandsToConvert,
                                             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).

Parameters:

numDemandsInLayer - Number of demands in the layer.

demandsToConvert - List of demands in the layer to apply conversion, the rest are untouched

f_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)

Returns:

Demand-link routing in the form f_de (fractions of traffic in a node from demand d, transmitted through link e)

convert_fte2xde

public 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 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). If the routing of a demand has closed loops a ClosedCycleRoutingException is thrown

Parameters:

numNodes - Number of nodes

numDemandsInLayer - Number of demand in the layer

links - List of links

demandsToConvert - List of demands

f_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)

Returns:

Demand-link routing in the form x_de (amount of traffic from demand d, transmitted through link e), total carried traffic per demand, carried traffic per link, and routing cycle type (loopless, with open cycles...) per demand

convert_fte2xp

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)

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. In the routing has open cycles, they are removed from the routing so the traffic of that demand uses the same or less capacity in the traversed links. If the routing has closed cycles, a 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.

Parameters:

nodes - List of nodes Net2Plan object

links - List of links

numDemandsInLayer - Number of demands in the layer

h_d - The amount of traffic offered for each demand

f_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 demands

Since:

0.3.1

convert_fte2xte

public static DoubleMatrix2D convert_fte2xte(List<Node> nodes,
                                             List<Link> links,
                                             SortedSet<Demand> demandsToConsider,
                                             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). If the routing has closed loops a ClosedCycleRoutingException is thrown

Parameters:

nodes - List of nodes

links - List of links

demandsToConsider - List of demands

h_d - The amount of traffic offered for each demand

f_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)

Returns:

Destination-based routing in the form f_te (fractions of traffic in a node, that is forwarded through each of its output links)

convert_xde2fde

public static DoubleMatrix2D convert_xde2fde(List<Link> links,
                                             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').

Parameters:

links - List of links

x_de - Demand-link routing in the form x_de (amount of traffic from demand d, transmitted through link e)

Returns:

Forwarding rule mapping (fractions of traffic entering a node from demand 'd', leaving that node through link 'e')

convert_xde2xp

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)

Converts the routing in the form x_de into a set of loopless routes, just for the indicated demands. If the x_de matrix has open or closed loops, they are removed from the routing. The resulting routing (after removing the cycles if any) of each demand uses the same of less bandwidth than the original routing.

Parameters:

nodes - List of nodes

links - List of links

demandsToConvert - List of demands

x_de - Demand-link 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)

Returns:

Number of new paths

convert_xde2xte

public static DoubleMatrix2D convert_xde2xte(int numNodes,
                                             SortedSet<Demand> demandsToConsider,
                                             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').

Parameters:

numNodes - Number of nodes

demandsToConsider - List of demands

x_de - Demand-link routing in the form x_de (amount of traffic from demand d, transmitted through link e)

Returns:

Forwarding rule matrix (a NxE matrix where each element δ_ne equals the fraction of traffic entering a node 'n' from demand 'd', leaving that node through link 'e')

convert_xde2ye

public static DoubleMatrix1D convert_xde2ye(DoubleMatrix2D x_de)

Returns the carried traffic per link.

Parameters:

x_de - Demand-link routing in the form x_de (amount of traffic from demand d, transmitted through link e)

Returns:

Carried traffic per link

convert_xp2fdeMap

public static SortedMap<Demand,SortedMap<Link,Double>> convert_xp2fdeMap(Collection<Route> routes)

Given a path-based 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. The link occupation information is not used, only the route carried traffic (the one if the network had no failures)

Parameters:

routes - List of routes

Returns:

see above

convert_xp2fte

public 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 f_te (fractions of traffic in a node, that is forwarded through each of its output links).

Parameters:

nodes - List of nodes

links - List of links

demands - List of demands

routes - List of routes

Returns:

Destination-based routing in the form f_te (fractions of traffic in a node, that is forwarded through each of its output links)

convert_xp2xde

public static DoubleMatrix2D convert_xp2xde(int D,
                                            int E,
                                            List<Route> routes)

Given a path-based routing, returns the amount of traffic for each demand d traversing each link e. The link occupation information is not used, only the route carried traffic (recall that a route carried traffic is zero if it traverses a failed link/node)

Parameters:

E - Number of links

D - Number of demands

routes - List of routes

Returns:

Demand-link routing in the form x_de (amount of traffic from demand d, transmitted through link e)

convert_xp2xte

public 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).

Parameters:

nodes - List of nodes

links - List of links

demands - List of demands

routes - List of routes

Returns:

Destination-based routing in the form x_te (amount of traffic targeted to node t, transmitted through link e)

convert_xp2ye

public static DoubleMatrix1D convert_xp2ye(List<Link> links,
                                           List<Route> routes)

Returns the carried traffic per link.

Parameters:

links - List of links

routes - List of routes

Returns:

Carried traffic per link

convert_xte2fte

public 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). If a node n does not forward any traffic to a destination t, it is not possible to determine the f_te fractions for the output links of the node. Then, the function arbitrarily assumes that the 100% of the traffic to node t, would be forwarded through the shortest path (in number of hops) from n to t. Finally note that for every destination t, f_te = 0 for all the links e outgoing of node t.

Parameters:

nodes - List of nodes

links - List of links

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 e

Returns:

The f_te matrix created

convert_xte2ye

public static DoubleMatrix1D convert_xte2ye(DoubleMatrix2D x_te)

Returns the carried traffic per link.

Parameters:

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 e

Returns:

Carried traffic per link

convertPath2PathCost

public 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.

Parameters:

seqLinks - Sequence of traversed links

linkCostMap - Cost per link array

Returns:

Cost of the path

convertPathList2PathCost

public static List<Double> convertPathList2PathCost(List<List<Link>> pathList,
                                                    DoubleMatrix1D linkCostMap)

Returns the total cost for a given a list of paths.

Parameters:

pathList - List of paths, where each path is represented by its sequence of traversed links

linkCostMap - Cost per link array

Returns:

Cost per path

convertSequenceOfLinksToSequenceOfNodes

public static List<Node> convertSequenceOfLinksToSequenceOfNodes(List<Link> seqLinks)

Converts a given sequence of links to the corresponding sequence of nodes.

Parameters:

seqLinks - Sequence of traversed links

Returns:

Sequence of nodes

getAdjacencyMatrix

public 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();

Parameters:

nodes - List of nodes

linkMap - 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

Returns:

Adjacency matrix

Since:

0.3.1

See Also:

Java Optimization Modeler (JOM) website

getAllLooplessShortestPaths

public 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. All these paths have the same total cost. Links with cost Double.MAX_VALUE are not considered.

Parameters:

nodes - List of nodes

links - List of links

originNode - Origin node

destinationNode - Destination node

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

Returns:

All loopless shortest paths

getBidirectionalMatrix

public 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();

Parameters:

nodes - List of nodes

linkMap - 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 object

Returns:

Bidirectional matrix

Since:

0.3.1

See Also:

Java Optimization Modeler (JOM) website

getCapacitatedShortestPath

public static List<Link> getCapacitatedShortestPath(Collection<Node> nodes,
                                                    Collection<Link> links,
                                                    Node originNode,
                                                    Node destinationNode,
                                                    SortedMap<Link,Double> linkCostMap,
                                                    SortedMap<Link,Double> linkSpareCapacityMap,
                                                    double capacityGoal)

Parameters:

nodes - List of nodes

links - List of links

originNode - Origin node

destinationNode - Destination node

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. 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 required

Returns:

Shortest path fulfilling a minimum capacity requirement

getConnectedComponents

public static List<Set<Node>> getConnectedComponents(Collection<Node> nodes,
                                                     List<Link> links)

Returns the connected components of the given graph

Parameters:

nodes - List of nodes

links - List of links

Returns:

see above

getIncidenceMatrix

public 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.

Parameters:

nodes - List of nodes

elements - List of elements

Returns:

Incidence matrix

See Also:

NetworkLayer

getIncomingIncidenceMatrix

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.

Parameters:

nodes - List of nodes

elements - List of Network Elements

Returns:

Node-link incoming incidence matrix

See Also:

NetworkLayer

getKLooplessShortestPaths

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)

Returns the K-loopless shortest paths between two nodes, satisfying some user-defined constraints. If only n shortest path are found (n<K), those are returned.

Parameters:

nodes - List of nodes

links - List of links

originNode - Origin node

destinationNode - Destination node

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. If null, all links have weight one. A value of Double.MAX_VALUE means that the link cannot be used

K - 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 assumed

maxNumHops - Maximum number of hops. If non-positive, no maximum limit is assumed

maxPropDelayInMs - Maximum propagation delay of the path. If non-positive, no maximum limit is assumed

maxRouteCost - Maximum route cost. If non-positive, no maximum limit is assumed

maxRouteCostFactorRespectToShortestPath - Maximum route cost factor respect to the shortest path. If non-positive, no maximum limit is assumed

maxRouteCostRespectToShortestPath - Maximum route cost respect to the shortest path. If non-positive, no maximum limit is assumed

Returns:

K-shortest paths

getKMinimumCostMulticastTrees

public 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 K-minimum cost multicast trees starting in the originNode and ending in the set destinationNodes, satisfying some user-defined constraints. If only n multicast trees are found (n<K), those are returned.

Parameters:

layer - the layer where to pick the network links. If null, picks the default layer

originNode - the origin node of all the multicast trees

destinationNodes - the set of destination nodes of all the multicast trees

Aout_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 uneligible

solverName - the name of the solver to call for the internal formulation of the algorithm

solverLibraryName - the solver library name

maxSolverTimeInSecondsPerTree - 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 set

K - 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 tree

maxE2ELengthInKm - Maximum path length measured in kilometers allowed for any tree, from the origin node, to any destination node

maxE2ENumHops - Maximum number of hops allowed for any tree, from the origin node, to any destination node

maxE2EPropDelayInMs - Maximum propagation delay in milliseconds allowed in a path, for any tree, from the origin node, to any destination node

maxTreeCost - Maximum tree weight allowed, summing the weights of the links

maxTreeCostFactorRespectToMinimumCostTree - Trees with higher weight (cost) than the cost of the minimum cost tree, multiplied by this factor, are not returned

maxTreeCostRespectToMinimumCostTree - 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 factor

Returns:

the list of k-minimum cost multicast trees constrained according to the method inputs

getKMinimumCostServiceChains

public 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 user-defined constraints. If only n shortest path are found (n<K), those are returned. If none is found an empty list is returned. The subpaths (the set of links between two resources, or the first(last) resource and the origin (destination) node, are constrained to be loopless (the algorithm uses Yen's scheme for subpaths enumeration).

Parameters:

links - The set of links which can be used for the chain

originNode - The origin node of the chain

destinationNode - The destination node of the chain (could be the same as the origin node)

sequenceOfResourceTypesToTraverse - the types of the sequence of resources to traverse

linkCost - the cost of each link (if null, all links have cost one), all numbers must be strictly positive

resourceCost - 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 enumerated

maxLengthInKmPerSubpath - The maximum length in km in each subpath. Service chains not satisfying this are not enumerated

maxNumHopsPerSubpath - The maximum number of traversed links in each subpath. Service chains not satisfying this are not enumerated

maxPropDelayInMsPerSubpath - The propagation delay summing the links in each subpath. Service chains not satisfying this are not enumerated

cacheSubpathLists - A map which associated to node pairs, the k-shortest paths (only considering links) already computed to be used. The algorithm will add new entries here for those pairs of nodes for which no per-computed 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.

Returns:

the (at most) K minimum cost service chains.

getMinimumCostMulticastTree

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)

getMinimumCostServiceChain

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)

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 user-defined constraints. If none is found an empty list is returned, with cost equal to Double.MAX_VALUE. It makes so, calling to the method 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).

Parameters:

links - The set of links which can be used for the chain

originNode - The origin node of the chain

destinationNode - The destination node of the chain (could be the same as the origin node)

sequenceOfResourceTypesToTraverse - the types of the sequence of resources to traverse

linkCost - the cost of each link (if null, all links have cost one), all numbers must be strictly positive

resourceCost - 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)

Returns:

the (at most) K minimum cost service chains.

getOutgoingIncidenceMatrix

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.

Parameters:

nodes - List of nodes

elements - List of elements

Returns:

Node-link outgoing incidence matrix

See Also:

NetworkElement

getShortestPath

public 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. Links with cost Double.MAX_VALUE are not considered.

Parameters:

nodes - Collection of nodes

links - Collection of links

originNode - Origin node

destinationNode - Destination node

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. If null, the shortest path in number of traversed links is returned,

Returns:

Sequence of links in the shortest path (empty, if destination not reachable from origin)

getTwoLinkDisjointPaths

public 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. Links with cost Double.MAX_VALUE are not considered The number of returned items will be equal to the number of paths found: when empty, no path was found; when size() = 1, only one path was found; and when size() = 2, the link-disjoint paths were found. Internally it uses the Suurballe-Tarjan algorithm.

Parameters:

nodes - Collection of nodes

links - Collection of links

originNode - Origin node

destinationNode - Destination node

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

Returns:

Shortest pair of link-disjoint paths

getTwoMaximumLinkAndNodeDisjointPaths

public static List<List<Link>> getTwoMaximumLinkAndNodeDisjointPaths(Collection<Node> nodes,
                                                                     Collection<Link> links,
                                                                     Node originNode,
                                                                     Node destinationNode,
                                                                     SortedMap<Link,Double> linkCostMap)

getTwoNodeDisjointPaths

public static List<List<Link>> getTwoNodeDisjointPaths(Collection<Node> nodes,
                                                       Collection<Link> links,
                                                       Node originNode,
                                                       Node destinationNode,
                                                       SortedMap<Link,Double> linkCostMap)

Returns the shortest pair of node-disjoint paths, where each item represents a path. Links with cost Double.MAX_VALUE are not considered The number of returned items will be equal to the number of paths found: when empty, no path was found; when size() = 1, only one path was found; and when size() = 2, the node-disjoint paths were found. Internally it uses the Suurballe-Tarjan algorithm.

Parameters:

nodes - Collection of nodes

links - Collection of links

originNode - Origin node

destinationNode - Destination node

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

Returns:

Shortest pair of node-disjoint paths

isBidirectional

public 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).

Parameters:

links - List of links

nodes - List of nodes

Returns:

true if the physical topology is bidirectional, and false otherwise

isConnected

public 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).

Parameters:

nodes - List of nodes

links - List of links

Returns:

true if the subgraph is connected, and false otherwise

isSimple

public 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.

Parameters:

links - List of links

nodes - List of nodes

Returns:

true if the physical topology is simple, and false otherwise

isWeightedBidirectional

public 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.

Parameters:

nodes - List of nodes

elements - 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)

Returns:

true if the physical topology is bidirectional and symmetric, and false otherwise

Since:

0.3.0

removeCyclesFrom_xde

public 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. The x_de matrix can be in the form of traffic in each link, or fraction of traffic respect to demand offered traffic, carried in each link. The cycles are removed guaranteeing that the new routing has the same or less traffic of each demand in each link This is specified in the xdeAsFractionRespecttoDemandOfferedTraffic parameter.

Parameters:

numNodes - Number of nodes

links - List of links

demandsToConsider - List of demands to which I want to remove the loops

x_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 traffic

xdeAsFractionRespecttoDemandOfferedTraffic - true is the matrix is in the fractional form, false otherwise

solverName - the name of the solver to call for the internal formulation of the algorithm

solverLibraryName - the solver library name

maxSolverTimeInSecondsPerDemand - the maximum time the solver is allowed for each of the internal formulations (one for each demand).

Returns:

The new x_de matrix )

removeCyclesFrom_xte

public 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. The x_de matrix can be in the form of traffic in each link, or fraction of traffic respect to demand offered traffic, carried in each link. The cycles are removed guaranteeing that the new routing has the same or less traffic of each demand in each link This is specified in the xdeAsFractionRespecttoDemandOfferedTraffic parameter.

Parameters:

nodes - List of nodes

links - List of links

trafficMatrix - List of demands to which I want to remove the loops

x_te - Demand-link 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 traffic

solverName - the name of the solver to call for the internal formulation of the algorithm

solverLibraryName - the solver library name

maxSolverTimeInSecondsPerDestination - the maximum time the solver is allowed for each of the internal formulations (one for each demand).

Returns:

The new x_de matrix )

simplifyLinkMap

public 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). Ties are broken arbitrarely.

Parameters:

links - List of links

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

Returns:

Matrix with the lower links weight between node pairs