public class GraphUtils
extends java.lang.Object
Auxiliary static methods to work with graphs.
These methods make intensive use of several Java libraries (i.e. JOM, JGraphT or JUNG) hiding low-level details to users.
Modifier and Type | Class and Description |
---|---|
static class |
GraphUtils.CheckRoutingCycleType
Indicates whether (and how) or not to check routing cycles.
|
static class |
GraphUtils.JGraphTUtils
Auxiliary class to work with the graph library JGraphT.
|
static class |
GraphUtils.JUNGUtils
Auxiliary class to work with the graph library JUNG.
|
Constructor and Description |
---|
GraphUtils() |
Modifier and Type | Method and Description |
---|---|
static void |
checkRouteContinuity(int[][] linkTable,
int[] sequenceOfLinks,
GraphUtils.CheckRoutingCycleType checkCycles)
Checks for validity of a given path (continuity and, optionally, no loops).
|
static int |
checkRouting_fte(int[][] linkTable,
double[][] f_te)
This function checks the validity of a destination-based routing (i.e IP routing).
|
static DoubleMatrixND |
computeDemand2PathAssignmentMatrix(NetPlan netPlan)
Returns the demand-path incidence matrix (a DxP matrix in which an element δdp is equal to 1 if traffic route p is able to carry traffic from demand d).
|
static DoubleMatrixND |
computeLink2PathAssignmentMatrix(java.util.List<int[]> seqLinks,
int E)
Returns the link-path incidence matrix (an ExP matrix in which an element δep is equal to the number of times which traffic route p traverses link e).
|
static DoubleMatrixND |
computeLink2PathAssignmentMatrix(NetPlan netPlan)
Returns the link-path incidence matrix (an ExP matrix in which an element δep is equal to the number of times which traffic route p traverses link e).
|
static void |
convert_fte2xp(int[][] linkTable,
int[][] demandTable,
double[] h_d,
double[][] f_te,
java.util.List<java.lang.Integer> demands_p,
java.util.List<int[]> seqLinks_p,
java.util.List<java.lang.Double> x_p)
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 double[][] |
convert_fte2xte(int[][] linkTable,
double[][] f_te,
double[][] trafficMatrix) |
static int |
convert_xde2xp(int[][] linkTable,
int[][] demandTable,
double[][] x_de,
java.util.List<java.lang.Integer> d_p,
java.util.List<int[]> sequenceOfLinks,
java.util.List<java.lang.Double> x_p)
Given the amount of traffic for each demand d traversing link e, it computes
the equivalent path-based routing.
|
static double[] |
convert_xde2ye(int[][] linkTable,
int[][] demandTable,
double[][] x_de)
Returns the carried traffic per link.
|
static double[][] |
convert_xp2fte(int[][] linkTable,
int[][] demandTable,
int[] d_p,
double[] x_p,
java.util.List<int[]> allSeqLinks,
int N)
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).
|
static double[][] |
convert_xp2xde(int[][] linkTable,
double[] x_p,
int[] d_p,
java.util.List<int[]> sequenceOfLinks)
Given a path-based routing, returns the amount of traffic for each demand d
traversing each link e.
|
static double[][] |
convert_xp2xte(int[][] linkTable,
int[][] demandTable,
int[] d_p,
double[] x_p,
java.util.List<int[]> allSeqLinks,
int N)
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 node e).
|
static double[] |
convert_xp2ye(java.util.List<java.lang.Double> x_p,
java.util.List<int[]> seqLinks,
int E)
Returns the carried traffic per link.
|
static double[][] |
convert_xte2fte(int[][] linkTable,
double[][] x_te)
Given a destination-based routing in the form of an array x_te (amount of traffic targeted to node t, transmitted through node 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 double[] |
convert_xte2ye(double[][] x_te) |
static double |
convertPath2PathCost(int[] seqLinks,
double[] costVector)
Returns the total cost for a given path.
|
static double[] |
convertPathList2PathCost(java.util.List<int[]> pathList,
double[] costVector)
Returns the total cost for a given a list of paths.
|
static int[] |
convertSeqLinks2seqNodes(int[] seqLinks,
int[][] linkTable)
Converts a given sequence of links to the corresponding sequence of nodes.
|
static java.util.List<int[]> |
getAllLooplessShortestPaths(int[][] linkTable,
int originNodeId,
int destinationNodeId,
int N,
double[] weights)
Returns all the loopless shortest paths between two nodes.
|
static int[] |
getCapacitatedShortestPath(int[][] linkTable,
int originNodeId,
int destinationNodeId,
double[] costVector,
double[] capacityVector,
double capacityGoal)
Returns the shortest path that fulfills a given minimum capacity requirement
along its traversed links.
|
static int[] |
getCapacitatedShortestPath(int[][] linkTable,
int originNodeId,
int destinationNodeId,
double[] costVector,
int[] capacityVector,
double capacityGoal)
Returns the shortest path that fulfills a given minimum capacity requirement
along its traversed links.
|
static int[] |
getDemandPathVector(NetPlan netPlan)
Returns the demand-path vector (a 1xP vector in which an element d(p) is equal to the demand identifier for path p).
|
static double[][] |
getIncidenceMatrix(int[][] anyTable,
int N)
Given a table of links, demands or paths, where first column is the link/demand/path inital node, and second column the target node,
it computes the incidence matrix.
|
static int[] |
getIncomingLinks(int[][] linkTable,
int node)
Given a link table, with a row per link and two columns (first the origin node, second the destination node), and given a node n, it
returns the links that enter the node.
|
static java.util.List<int[]> |
getKLooplessShortestPaths(int[][] linkTable,
int originNodeId,
int destinationNodeId,
int N,
int K,
double[] weights)
Returns the K-loopless shortest paths between two nodes.
|
static DoubleMatrixND |
getNodeAdjacencyMatrix(NetPlan netPlan)
Returns the node adjacency matrix (a NxN matrix in which an element aij is equal to the number of links from node i to node j).
|
static DoubleMatrixND |
getNodeDemandIncidenceMatrix(NetPlan netPlan)
Returns the node-demand incidence matrix (a NxD matrix in which an element wnd is equal to 1 if node n is the ingress node of demand d, -1 if node n is the egress node of demand d, and zero otherwise).
|
static DoubleMatrixND |
getNodeLinkIncidenceMatrix(NetPlan netPlan)
Returns the node-link incidence matrix (a NxE matrix in which an element ane is equal to 1 if node n is the origin node of link e, -1 if node n is the destination node of link e, and zero otherwise).
|
static int[] |
getOutgoingLinks(int[][] linkTable,
int node)
Given a link table, with a row per link and two columns (first the origin node, second the destination node), and given a node n, it
returns the links that leave the node.
|
static int[] |
getShortestPath(int[][] linkTable,
int originNodeId,
int destinationNodeId,
double[] costVector)
Obtains the sequence of links representing the (unidirectional) shortest path between two nodes.
|
static int[][] |
getTwoLinkDisjointPaths(int src,
int dst,
int[][] linkTable,
double[] costVector,
int N)
Returns the shortest pair of link-disjoint paths.
|
static int[][] |
getTwoNodeDisjointPaths(int src,
int dst,
int[][] linkTable,
double[] costVector,
int N)
Returns the shortest pair of node-disjoint paths.
|
static boolean |
hasRoutingLoops(NetPlan netPlan,
GraphUtils.CheckRoutingCycleType checkCycles)
Indicates whether routing has loops (a node is visited more than once).
|
static boolean |
isBidirectional(int[][] linkTable,
int N)
Checks whether the physical topology has the same number of links between each node pair in both directions (assuming multi-digraphs).
|
static boolean |
isBidirectional(NetPlan netPlan)
Checks whether the physical topology has the same number of links between each node pair in both directions (assuming multi-digraphs).
|
static boolean |
isConnected(NetPlan netPlan)
Check whether the physical topology is connected, that is, if it is possible to connect every node to each other.
|
static boolean |
isConnected(NetPlan netPlan,
int[] nodes)
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(NetPlan netPlan)
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(int[][] linkTable,
double[] linkWeight,
int N)
Checks whether the physical topology has the same number of links between each node pair in both directions (assuming multi-digraphs) and same weights per direction.
|
static boolean |
isWeightedBidirectional(NetPlan netPlan,
double[] linkWeight)
Checks whether the physical topology has the same number of links between each node pair in both directions (assuming multi-digraphs) and same weights per direction.
|
public static void checkRouteContinuity(int[][] linkTable, int[] sequenceOfLinks, GraphUtils.CheckRoutingCycleType checkCycles)
Checks for validity of a given path (continuity and, optionally, no loops).
linkTable
- Set of installed links (first column: origin node, second column: destination node)sequenceOfLinks
- Sequence of traversed linkscheckCycles
- Indicates whether (and how) or not to check if there are cyclespublic static double convertPath2PathCost(int[] seqLinks, double[] costVector)
seqLinks
- Sequence of traversed links per each routecostVector
- Link weightspublic static double[] convertPathList2PathCost(java.util.List<int[]> pathList, double[] costVector)
pathList
- List of pathscostVector
- Link weightspublic static double[] convert_xde2ye(int[][] linkTable, int[][] demandTable, double[][] x_de)
linkTable
- Set of installed links (first column: origin node, second column: destination node)demandTable
- The table of demands in the network: one row per demand, first column input node, second column output nodex_de
- Array containing the amount of traffic from demand d which traverses link epublic static double[][] convert_xp2xte(int[][] linkTable, int[][] demandTable, int[] d_p, double[] x_p, java.util.List<int[]> allSeqLinks, int N)
linkTable
- Set of installed links (first column: origin node, second column: destination node)demandTable
- The table of demands in the network: one row per demand, first column input node, second column output noded_p
- This is the form in which the demands for each path are returned. The user should pass an empty array to the function, and this array is internally filled with the correct data.x_p
- This is the form in which the amounts of traffic in each path are returned. The user should pass an empty array to the function, and this array is internally filled with the correct data.allSeqLinks
- Sequence of traversed links per each routeN
- Number of nodespublic static double[][] convert_xp2fte(int[][] linkTable, int[][] demandTable, int[] d_p, double[] x_p, java.util.List<int[]> allSeqLinks, int N)
linkTable
- Set of installed links (first column: origin node, second column: destination node)demandTable
- The table of demands in the network: one row per demand, first column input node, second column output noded_p
- This is the form in which the demands for each path are returned. The user should pass an empty array to the function, and this array is internally filled with the correct data.x_p
- This is the form in which the amounts of traffic in each path are returned. The user should pass an empty array to the function, and this array is internally filled with the correct data.allSeqLinks
- Sequence of traversed links per each routeN
- Number of nodespublic static double[] convert_xte2ye(double[][] x_te)
public static double[] convert_xp2ye(java.util.List<java.lang.Double> x_p, java.util.List<int[]> seqLinks, int E)
x_p
- This is the form in which the amounts of traffic in each path are returned. The user should pass an empty array to the function, and this array is internally filled with the correct data.seqLinks
- Sequence of traversed links per each routeE
- Number of linkspublic static int[] convertSeqLinks2seqNodes(int[] seqLinks, int[][] linkTable)
seqLinks
- Sequence of linkslinkTable
- Set of installed links (first column: origin node, second column: destination node)public static int[][] getTwoLinkDisjointPaths(int src, int dst, int[][] linkTable, double[] costVector, int N)
src
- Origin nodedst
- Destination nodelinkTable
- Set of installed links (first column: origin node, second column: destination node)costVector
- Link weightsN
- Number of nodespublic static int[][] getTwoNodeDisjointPaths(int src, int dst, int[][] linkTable, double[] costVector, int N)
src
- Origin nodedst
- Destination nodelinkTable
- Set of installed links (first column: origin node, second column: destination node)costVector
- Link weightsN
- Number of nodespublic static java.util.List<int[]> getAllLooplessShortestPaths(int[][] linkTable, int originNodeId, int destinationNodeId, int N, double[] weights)
linkTable
- Set of installed links (first column: origin node, second column: destination node)originNodeId
- Origin nodedestinationNodeId
- Destination nodeN
- Number of nodesweights
- Link weightspublic static java.util.List<int[]> getKLooplessShortestPaths(int[][] linkTable, int originNodeId, int destinationNodeId, int N, int K, double[] weights)
linkTable
- Set of installed links (first column: origin node, second column: destination node)originNodeId
- Origin nodedestinationNodeId
- Destination nodeN
- Number of nodesK
- Number of different pathsweights
- Link weightspublic static int convert_xde2xp(int[][] linkTable, int[][] demandTable, double[][] x_de, java.util.List<java.lang.Integer> d_p, java.util.List<int[]> sequenceOfLinks, java.util.List<java.lang.Double> x_p)
linkTable
- Set of installed links (first column: origin node, second column: destination node)demandTable
- The table of demands in the network: one row per demand, first column input node, second column output nodex_de
- Array containing the amount of traffic from demand d which traverses link ed_p
- This is the form in which the demands for each path are returned. The user should pass an empty array to the function, and this array is internally filled with the correct data.sequenceOfLinks
- Sequence of traversed links per each routex_p
- This is the form in which the amounts of traffic in each path are returned. The user should pass an empty array to the function, and this array is internally filled with the correct data.public static double[][] convert_xte2fte(int[][] linkTable, double[][] x_te)
linkTable
- Set of installed links (first column: origin node, second column: destination node)x_te
- Array containing the amount of traffic targeted to node t, transmitted through node epublic static int checkRouting_fte(int[][] linkTable, double[][] f_te)
linkTable
- Set of installed links (first column: origin node, second column: destination node)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 initial 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 1. For every destination t, f_te = 0 for all the links e that are outgoing links of tpublic static double[][] convert_fte2xte(int[][] linkTable, double[][] f_te, double[][] trafficMatrix)
public static double[][] getIncidenceMatrix(int[][] anyTable, int N)
anyTable
- The table of links, deamnds, paths etc. where we extract the incidence matrixN
- The number of nodes in the networkpublic static void convert_fte2xp(int[][] linkTable, int[][] demandTable, double[] h_d, double[][] f_te, java.util.List<java.lang.Integer> demands_p, java.util.List<int[]> seqLinks_p, java.util.List<java.lang.Double> x_p)
linkTable
- Set of installed links (first column: origin node, second column: destination node)demandTable
- The table of demands in the network: one row per demand, first column input node, second column output nodeh_d
- The amount of traffic offered for each demandf_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 initial 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 1. For every destination t, f_te = 0 for all the links e that are outgoing links of tdemands_p
- This is the form in which the demands for each path are returned. The user should pass an empty array to the function, and this array is internally filled with the correct data.seqLinks_p
- This is the form in which the sequence of links for each path are returned. The user should pass an empty array to the function, and this array is internally filled with the correct data.x_p
- This is the form in which the amounts of traffic in each path are returned. The user should pass an empty array to the function, and this array is internally filled with the correct data.public static int[] getOutgoingLinks(int[][] linkTable, int node)
linkTable
- Set of installed links (first column: origin node, second column: destination node)node
- Node identifierpublic static int[] getIncomingLinks(int[][] linkTable, int node)
linkTable
- Set of installed links (first column: origin node, second column: destination node)node
- Node identifierpublic static double[][] convert_xp2xde(int[][] linkTable, double[] x_p, int[] d_p, java.util.List<int[]> sequenceOfLinks)
linkTable
- Set of installed links (first column: origin node, second column: destination node)x_p
- This is the form in which the amounts of traffic in each path are returned. The user should pass an empty array to the function, and this array is internally filled with the correct data.d_p
- This is the form in which the demands for each path are returned. The user should pass an empty array to the function, and this array is internally filled with the correct data.sequenceOfLinks
- Sequence of traversed links per each routepublic static int[] getCapacitatedShortestPath(int[][] linkTable, int originNodeId, int destinationNodeId, double[] costVector, double[] capacityVector, double capacityGoal)
linkTable
- Set of installed links (first column: origin node, second column: destination node)originNodeId
- Origin nodedestinationNodeId
- Destination nodecostVector
- Link weightscapacityVector
- Link capacity vectorcapacityGoal
- Minimum capacity requiredpublic static int[] getCapacitatedShortestPath(int[][] linkTable, int originNodeId, int destinationNodeId, double[] costVector, int[] capacityVector, double capacityGoal)
linkTable
- Set of installed links (first column: origin node, second column: destination node)originNodeId
- Origin nodedestinationNodeId
- Destination nodecostVector
- Link weightscapacityVector
- Link capacity vectorcapacityGoal
- Minimum capacity requiredpublic static DoubleMatrixND computeDemand2PathAssignmentMatrix(NetPlan netPlan)
netPlan
- Network planpublic static int[] getDemandPathVector(NetPlan netPlan)
Returns the demand-path vector (a 1xP vector in which an element d(p) is equal to the demand identifier for path p).
netPlan
- Network planpublic static DoubleMatrixND getNodeAdjacencyMatrix(NetPlan netPlan)
Returns the node adjacency matrix (a NxN matrix in which an element aij is equal to the number of links from node i to node j).
The output is in the sparse DoubleMatrixND
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 = (double[][]) getNodeAdjacencyMatrix(netPlan).toArray();
netPlan
- Network planpublic static DoubleMatrixND getNodeDemandIncidenceMatrix(NetPlan netPlan)
Returns the node-demand incidence matrix (a NxD matrix in which an element wnd is equal to 1 if node n is the ingress node of demand d, -1 if node n is the egress node of demand d, and zero otherwise).
The output is in the sparse DoubleMatrixND
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 = (double[][]) getNodeDemandIncidenceMatrix(netPlan).toArray();
netPlan
- Network planpublic static DoubleMatrixND getNodeLinkIncidenceMatrix(NetPlan netPlan)
The output is in the sparse DoubleMatrixND
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 = (double[][]) getNodeLinkIncidenceMatrix(netPlan).toArray();
netPlan
- Network planpublic static DoubleMatrixND computeLink2PathAssignmentMatrix(java.util.List<int[]> seqLinks, int E)
seqLinks
- Sequence of traversed links per each routeE
- Number of links within the networkpublic static DoubleMatrixND computeLink2PathAssignmentMatrix(NetPlan netPlan)
netPlan
- Network planpublic static boolean isBidirectional(NetPlan netPlan)
netPlan
- A network plantrue
if the physical topology is bidirectional, and false otherwisepublic static boolean isBidirectional(int[][] linkTable, int N)
linkTable
- Set of installed links (first column: origin node, second column: destination node)N
- Number of nodestrue
if the physical topology is bidirectional, and false otherwisepublic static boolean isWeightedBidirectional(int[][] linkTable, double[] linkWeight, int N)
linkTable
- Set of installed links (first column: origin node, second column: destination node)linkWeight
- Link weight vectorN
- Number of nodestrue
if the physical topology is bidirectional and symmetric, and false otherwisepublic static boolean hasRoutingLoops(NetPlan netPlan, GraphUtils.CheckRoutingCycleType checkCycles)
netPlan
- Network designcheckCycles
- Indicates whether (and how) or not to check if there are cyclestrue
if there are routing loops, and false
otherwise. By convention, it returns false
for designs without routing.public static boolean isWeightedBidirectional(NetPlan netPlan, double[] linkWeight)
netPlan
- A network planlinkWeight
- Link weight vectortrue
if the physical topology is weighted-bidirectional, and false otherwisepublic static boolean isConnected(NetPlan netPlan)
netPlan
- A network plantrue
if the physical topology is connected, and false otherwisepublic static boolean isConnected(NetPlan netPlan, int[] nodes)
netPlan
- A network plannodes
- Vector of nodestrue
if the subgraph is connected, and false otherwisepublic static boolean isSimple(NetPlan netPlan)
netPlan
- A network plantrue
if the physical topology is simple, and false otherwisepublic static int[] getShortestPath(int[][] linkTable, int originNodeId, int destinationNodeId, double[] costVector)
linkTable
- Set of installed links (first column: origin node, second column: destination node)originNodeId
- Origin nodedestinationNodeId
- Destination nodecostVector
- Link weights