public class GraphUtils
extends Object
Auxiliary static methods to work with graphs.
These methods make intensive use of several Java libraries (i.e. JOM, JGraphT or JUNG) hiding low-level details to users.
Modifier and Type | Class and Description |
---|---|
static class |
GraphUtils.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 int |
checkRouting_fte(int[][] linkTable,
double[][] f_te)
This function checks the validity of a destination-based routing (i.e IP routing).
|
static com.jom.DoubleMatrixND |
computeDemand2PathAssignmentMatrix(NetPlan netPlan) |
static com.jom.DoubleMatrixND |
computeLink2PathAssignmentMatrix(List<int[]> seqLinks,
int E) |
static com.jom.DoubleMatrixND |
computeLink2PathAssignmentMatrix(NetPlan netPlan) |
static void |
convert_fte2xp(int[][] linkTable,
int[][] demandTable,
double[] h_d,
double[][] f_te,
List<Integer> demands_p,
List<int[]> seqLinks_p,
List<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 void |
convert_xde2xp(int[][] linkTable,
int[][] demandTable,
double[][] x_de,
List<Integer> d_p,
List<int[]> sequenceOfLinks,
List<Double> x_p) |
static double[] |
convert_xde2ye(int[][] linkTable,
int[][] demandTable,
double[][] x_de) |
static double[][] |
convert_xp2fte(int[][] linkTable,
int[][] demandTable,
int[] d_p,
double[] x_p,
List<int[]> allSeqLinks,
int N) |
static double[][] |
convert_xp2xde(int[][] linkTable,
double[] x_p,
int[] d_p,
List<int[]> sequenceOfLinks) |
static double[][] |
convert_xp2xte(int[][] linkTable,
int[][] demandTable,
int[] d_p,
double[] x_p,
List<int[]> allSeqLinks,
int N) |
static double[] |
convert_xp2ye(double[] x_p,
List<int[]> seqLinks,
int E) |
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 int[] |
convertSeqLinks2seqNodes(int[] seqLinks,
int[][] linkTable) |
static List<int[]> |
getAllLooplessShortestPaths(int[][] linkTable,
int originNodeId,
int destinationNodeId,
int N,
double[] weights) |
static int[] |
getCapacitatedShortestPath(int[][] linkTable,
int originNodeId,
int destinationNodeId,
double[] costVector,
double[] capacityVector,
double capacityGoal) |
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 List<int[]> |
getKLooplessShortestPaths(int[][] linkTable,
int originNodeId,
int destinationNodeId,
int N,
int K) |
static List<int[]> |
getKLooplessShortestPaths(int[][] linkTable,
int originNodeId,
int destinationNodeId,
int N,
int K,
double[] weights) |
static com.jom.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 com.jom.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 com.jom.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) |
static int[][] |
getTwoLinkDisjointPaths(int src,
int dst,
int[][] linkTable,
double[] costVector,
int N) |
static int[][] |
getTwoNodeDisjointPaths(int src,
int dst,
int[][] linkTable,
double[] costVector,
int N) |
static boolean |
isBidirectional(NetPlan netPlan)
Check 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(NetPlan netPlan,
double[] linkWeight)
Check 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 double[] convert_xde2ye(int[][] linkTable, int[][] demandTable, double[][] x_de)
public static double[][] convert_xp2xte(int[][] linkTable, int[][] demandTable, int[] d_p, double[] x_p, List<int[]> allSeqLinks, int N)
public static double[][] convert_xp2fte(int[][] linkTable, int[][] demandTable, int[] d_p, double[] x_p, List<int[]> allSeqLinks, int N)
public static double[] convert_xp2ye(double[] x_p, List<int[]> seqLinks, int E)
public static int[] convertSeqLinks2seqNodes(int[] seqLinks, int[][] linkTable)
public static int[][] getTwoLinkDisjointPaths(int src, int dst, int[][] linkTable, double[] costVector, int N)
public static int[][] getTwoNodeDisjointPaths(int src, int dst, int[][] linkTable, double[] costVector, int N)
public static List<int[]> getAllLooplessShortestPaths(int[][] linkTable, int originNodeId, int destinationNodeId, int N, double[] weights)
public static List<int[]> getKLooplessShortestPaths(int[][] linkTable, int originNodeId, int destinationNodeId, int N, int K)
public static List<int[]> getKLooplessShortestPaths(int[][] linkTable, int originNodeId, int destinationNodeId, int N, int K, double[] weights)
public static void convert_xde2xp(int[][] linkTable, int[][] demandTable, double[][] x_de, List<Integer> d_p, List<int[]> sequenceOfLinks, List<Double> x_p)
public static double[][] convert_xte2fte(int[][] linkTable, double[][] x_te)
linkTable
- The table of links of the network: one row per link, first column input node, second column output nodex_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
- The table of links of the network: one row per link, first column input node, second column output nodef_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[][] 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, List<Integer> demands_p, List<int[]> seqLinks_p, List<Double> x_p)
linkTable
- The table of links of the network: one row per link, first column input node, second column output nodedemandTable
- 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
- The link tablenode
- The nodepublic static int[] getIncomingLinks(int[][] linkTable, int node)
linkTable
- The link tablenode
- The nodepublic static double[][] convert_xp2xde(int[][] linkTable, double[] x_p, int[] d_p, List<int[]> sequenceOfLinks)
public static int[] getCapacitatedShortestPath(int[][] linkTable, int originNodeId, int destinationNodeId, double[] costVector, double[] capacityVector, double capacityGoal)
public static com.jom.DoubleMatrixND computeDemand2PathAssignmentMatrix(NetPlan netPlan)
public 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).
public static com.jom.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();
public static com.jom.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();
public static com.jom.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();
public static com.jom.DoubleMatrixND computeLink2PathAssignmentMatrix(List<int[]> seqLinks, int E)
public static com.jom.DoubleMatrixND computeLink2PathAssignmentMatrix(NetPlan netPlan)
public static boolean isBidirectional(NetPlan netPlan)
netPlan
- A network plantrue
if the physical topology is bidirectional, and false otherwise. By convention, if netPlan is empty returns false
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)