com.net2plan.libraries

Class GraphUtils.JUNGUtils

Object

com.net2plan.libraries.GraphUtils.JUNGUtils

Enclosing class:

GraphUtils

public static class GraphUtils.JUNGUtils
extends Object

Auxiliary class to work with the graph library JUNG.

Since:

0.2.0

Author:

Pablo Pavon-Marino, Jose-Luis Izquierdo-Zaragoza

Constructor Summary

Constructors

Constructor and Description
GraphUtils.JUNGUtils()

Method Summary

Methods

Modifier and Type	Method and Description
static edu.uci.ics.jung.graph.Graph<Long,Long>	buildAuxiliaryNodeDisjointGraph(edu.uci.ics.jung.graph.Graph<Long,Long> graph, long originNode, long destinationNode) Builds an auxiliary graph for the application of edge-disjoint shortest-path pair algorithms to node-disjoint problems.
static Pair<edu.uci.ics.jung.graph.Graph<Long,Long>,org.apache.commons.collections15.Transformer<Long,Double>>	buildAuxiliaryNodeDisjointGraph(edu.uci.ics.jung.graph.Graph<Long,Long> graph, org.apache.commons.collections15.Transformer<Long,Double> nev, long originNode, long destinationNode) Builds an auxiliary graph for the application of edge-disjoint shortest-path pair algorithms to node-disjoint problems.
static <V,E> java.awt.image.BufferedImage	createImage(edu.uci.ics.jung.graph.Graph<V,E> graph, org.apache.commons.collections15.Transformer<V,Point2D> vertexPositionTransformer, int width, int height, int fontSize, float nodeSize, float linkThickness) Creates an image of the network topology.
static <V,E> edu.uci.ics.jung.graph.Graph<V,E>	filterGraph(edu.uci.ics.jung.graph.Graph<V,E> graph, Collection<V> acceptedVertices, Collection<V> blockedVertices, Collection<E> acceptedEdges, Collection<E> blockedEdges) Filters a graph maintaining/removing some vertices/edges.
static <V,E> edu.uci.ics.jung.graph.Graph<V,E>	filterGraph(edu.uci.ics.jung.graph.Graph<V,E> graph, org.apache.commons.collections15.Transformer<E,Double> nev) Filters a graph removing those edges whose weight is equal to Double.MAX_VALUE.
static <V,E> edu.uci.ics.jung.graph.Graph<V,E>	filterGraph(edu.uci.ics.jung.graph.Graph<V,E> graph, org.apache.commons.collections15.Transformer<E,Double> nev, org.apache.commons.collections15.Transformer<E,Double> edgeSpareCapacityTransformer, double requiredCapacity) Filters a graph removing those edges whose weight is equal to Double.MAX_VALUE, or whose capacity is below a certain threshold.
static <V,E> List<E>	getCapacitatedShortestPath(edu.uci.ics.jung.graph.Graph<V,E> graph, org.apache.commons.collections15.Transformer<E,Double> nev, V originNodeId, V destinationNodeId, org.apache.commons.collections15.Transformer<E,Double> edgeSpareCapacityTransformer, double requiredCapacity) Returns the shortest path that fulfills a given minimum capacity requirement along its traversed edges.
static <E> org.apache.commons.collections15.Transformer<E,Double>	getEdgeWeightTransformer(Map<E,Double> edgeWeightMap) Obtains a transformer for returning link weight from link identifier.
static <V,E> edu.uci.ics.jung.graph.Graph<V,E>	getGraphFromLinkMap(Map<E,Pair<V,V>> linkMap) Obtains a JUNG graph from a given link map.
static <V,E> edu.uci.ics.jung.graph.Graph<V,E>	getGraphFromLinkMap(Set<V> nodeIds, Map<E,Pair<V,V>> linkMap) Obtains a JUNG graph from a given link map.
static <V,E> List<List<E>>	getKLooplessShortestPaths(edu.uci.ics.jung.graph.Graph<V,E> graph, org.apache.commons.collections15.Transformer<E,Double> nev, V originNodeId, V destinationNodeId, int K) Returns the K-loopless shortest paths between two nodes.
static <E> double	getPathWeight(List<E> path, org.apache.commons.collections15.Transformer<E,Double> nev) Returns the weight of a path given the sequence of edges.
static <V,E> List<E>	getShortestPath(edu.uci.ics.jung.graph.Graph<V,E> graph, org.apache.commons.collections15.Transformer<E,Double> nev, V originNodeId, V destinationNodeId) Returns the shortest path between two nodes using Dijkstra's algorithm.
static <V,E> List<List<E>>	getTwoLinkDisjointPaths(edu.uci.ics.jung.graph.Graph<V,E> graph, org.apache.commons.collections15.Transformer<E,Double> nev, V originNodeId, V destinationNodeId) Returns the shortest pair of link-disjoint paths, where each item represents a path.
static List<List<Long>>	getTwoNodeDisjointPaths(edu.uci.ics.jung.graph.Graph<Long,Long> graph, org.apache.commons.collections15.Transformer<Long,Double> nev, long originNode, long destinationNode) Returns the shortest pair of node-disjoint paths, where each item represents a path.
static boolean	isBidirectional(edu.uci.ics.jung.graph.Graph graph) Check whether the topology has the same number of links between each node pair in both directions (assuming multi-digraphs).
static boolean	isSimple(edu.uci.ics.jung.graph.Graph graph) Check whether the graph is simple, that is, if it has at most one link between each node pair (one per direction under directed graphs, one under undirected graphs).
static <V,E> boolean	isWeightedBidirectional(edu.uci.ics.jung.graph.Graph<V,E> graph, org.apache.commons.collections15.Transformer<E,Double> nev) Checks whether the graph has the same number of links between each node pair in both directions (assuming multi-digraphs) and same individual weights per direction.
static <V,E> edu.uci.ics.jung.graph.Graph<V,E>	simplifyGraph(edu.uci.ics.jung.graph.Graph<V,E> graph, org.apache.commons.collections15.Transformer<E,Double> nev) Given an input graph that may contain multiple edges between some vertex pairs, returns a new graph where only appears, for each vertex pair, the edge having the lowest weight (edges whose weight is equal to Double.MAX_VALUE are excluded).

Methods inherited from class Object

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

Constructor Detail

GraphUtils.JUNGUtils

public GraphUtils.JUNGUtils()

Method Detail

buildAuxiliaryNodeDisjointGraph

public static edu.uci.ics.jung.graph.Graph<Long,Long> buildAuxiliaryNodeDisjointGraph(edu.uci.ics.jung.graph.Graph<Long,Long> graph,
                                                                      long originNode,
                                                                      long destinationNode)

Builds an auxiliary graph for the application of edge-disjoint shortest-path pair algorithms to node-disjoint problems.

Parameters:

graph - Graph representing the network

originNode - Origin node

destinationNode - Destination node

Returns:

Auxiliary graph

Since:

0.3.0

buildAuxiliaryNodeDisjointGraph

public static Pair<edu.uci.ics.jung.graph.Graph<Long,Long>,org.apache.commons.collections15.Transformer<Long,Double>> buildAuxiliaryNodeDisjointGraph(edu.uci.ics.jung.graph.Graph<Long,Long> graph,
                                                                                                                                      org.apache.commons.collections15.Transformer<Long,Double> nev,
                                                                                                                                      long originNode,
                                                                                                                                      long destinationNode)

Builds an auxiliary graph for the application of edge-disjoint shortest-path pair algorithms to node-disjoint problems.

Parameters:

graph - Graph representing the network

nev - Object responsible for returning weights for edges

originNode - Origin node

destinationNode - Destination node

Returns:

Auxiliary graph, and its corresponding object returning edge weights

Since:

0.3.0

createImage

public static <V,E> java.awt.image.BufferedImage createImage(edu.uci.ics.jung.graph.Graph<V,E> graph,
                                             org.apache.commons.collections15.Transformer<V,Point2D> vertexPositionTransformer,
                                             int width,
                                             int height,
                                             int fontSize,
                                             float nodeSize,
                                             float linkThickness)

Creates an image of the network topology. The returned image will be trimmed to remove white borders.

Type Parameters:

V - Vertex type

E - Edge type

Parameters:

graph - Graph representing the network

vertexPositionTransformer - Object responsible for returning position for vertices

width - Expected maximum width (it may be lower due to white borders removal)

height - Expected maximum height (it may be lower due to white borders removal)

fontSize - Font size for vertex label (in points)

nodeSize - Node size

linkThickness - Link thickness

Returns:

Image

Since:

0.3.1

filterGraph

public static <V,E> edu.uci.ics.jung.graph.Graph<V,E> filterGraph(edu.uci.ics.jung.graph.Graph<V,E> graph,
                                                  Collection<V> acceptedVertices,
                                                  Collection<V> blockedVertices,
                                                  Collection<E> acceptedEdges,
                                                  Collection<E> blockedEdges)

Filters a graph maintaining/removing some vertices/edges. In the same invocation, user must choose between 'accept' or 'block' some elements (vertices and/or edges).

Important: Returned graph is not backed in the input one, so changes will not be reflected on it.

Type Parameters:

V - Class type for vertices

E - Class type for edges

Parameters:

graph - Graph representing the network

acceptedVertices - Collection of accepted vertices (null means empty)

blockedVertices - Collection of blocked vertices (null means empty)

acceptedEdges - Collection of accepted edges (null means empty)

blockedEdges - Collection of blocked edges (null means empty)

Returns:

Filtered graph

Since:

0.3.0

filterGraph

public static <V,E> edu.uci.ics.jung.graph.Graph<V,E> filterGraph(edu.uci.ics.jung.graph.Graph<V,E> graph,
                                                  org.apache.commons.collections15.Transformer<E,Double> nev)

Filters a graph removing those edges whose weight is equal to Double.MAX_VALUE.

Important: Returned graph is not backed in the input one, so changes will not be reflected on it.

Type Parameters:

V - Class type for vertices

E - Class type for edges

Parameters:

graph - Graph representing the network

nev - Object responsible for returning weights for edges

Returns:

Filtered graph

Since:

0.3.0

filterGraph

public static <V,E> edu.uci.ics.jung.graph.Graph<V,E> filterGraph(edu.uci.ics.jung.graph.Graph<V,E> graph,
                                                  org.apache.commons.collections15.Transformer<E,Double> nev,
                                                  org.apache.commons.collections15.Transformer<E,Double> edgeSpareCapacityTransformer,
                                                  double requiredCapacity)

Filters a graph removing those edges whose weight is equal to Double.MAX_VALUE, or whose capacity is below a certain threshold.

Important: Returned graph is not backed in the input one, so changes will not be reflected on it.

Type Parameters:

V - Class type for vertices

E - Class type for edges

Parameters:

graph - Graph representing the network

nev - Object responsible for returning weights for edges

edgeSpareCapacityTransformer - Object responsible for returning capacity for edges (if null, it will not applied)

requiredCapacity - Capacity threshold. Edges whose capacity is below that value it will be removed

Returns:

Filtered graph

Since:

0.3.0

getCapacitatedShortestPath

public static <V,E> List<E> getCapacitatedShortestPath(edu.uci.ics.jung.graph.Graph<V,E> graph,
                                       org.apache.commons.collections15.Transformer<E,Double> nev,
                                       V originNodeId,
                                       V destinationNodeId,
                                       org.apache.commons.collections15.Transformer<E,Double> edgeSpareCapacityTransformer,
                                       double requiredCapacity)

Returns the shortest path that fulfills a given minimum capacity requirement along its traversed edges. In case no path can be found, an empty list will be returned.

Type Parameters:

V - Class type for vertices

E - Class type for edges

Parameters:

graph - Graph representing the network

nev - Object responsible for returning weights for edges

originNodeId - Origin node

destinationNodeId - Destination node

edgeSpareCapacityTransformer - Object responsible for returning capacity for edges (if null, it will not applied)

requiredCapacity - Capacity threshold. Edges whose capacity is below that value it will be removed

Returns:

Shortest path fulfilling a minimum capacity requirement

Since:

0.3.0

getEdgeWeightTransformer

public static <E> org.apache.commons.collections15.Transformer<E,Double> getEdgeWeightTransformer(Map<E,Double> edgeWeightMap)

Obtains a transformer for returning link weight from link identifier.

Type Parameters:

E - Edge type

Parameters:

edgeWeightMap - A mapping of edges to weights (null means 'all-one' map)

Returns:

A transformer for returning weights for edges

Since:

0.3.0

getGraphFromLinkMap

public static <V,E> edu.uci.ics.jung.graph.Graph<V,E> getGraphFromLinkMap(Map<E,Pair<V,V>> linkMap)

Obtains a JUNG graph from a given link map.

Type Parameters:

V - Vertex type

E - Edge type

Parameters:

linkMap - Map of links, where the key is the unique link identifier and the value is a Pair representing the origin node and the destination node of the link, respectively. Origin/destination nodes will be added as needed

Returns:

JUNG graph

Since:

0.3.1

getGraphFromLinkMap

public static <V,E> edu.uci.ics.jung.graph.Graph<V,E> getGraphFromLinkMap(Set<V> nodeIds,
                                                          Map<E,Pair<V,V>> linkMap)

Obtains a JUNG graph from a given link map.

Type Parameters:

V - Vertex type

E - Edge type

Parameters:

nodeIds - Set of node identifiers

linkMap - Map of links, where the key is the unique link identifier and the value is a Pair representing the origin node and the destination node of the link, respectively. Only links whose end-nodes are in nodeIds will be added to the graph

Returns:

JUNG graph

Since:

0.3.1

getKLooplessShortestPaths

public static <V,E> List<List<E>> getKLooplessShortestPaths(edu.uci.ics.jung.graph.Graph<V,E> graph,
                                            org.apache.commons.collections15.Transformer<E,Double> nev,
                                            V originNodeId,
                                            V destinationNodeId,
                                            int K)

Returns the K-loopless shortest paths between two nodes. If only n could be found, only these ones will be returned.

Type Parameters:

V - Class type for vertices

E - Class type for edges

Parameters:

graph - Graph representing the network

nev - Object responsible for returning weights for edges

originNodeId - Origin node

destinationNodeId - Destination node

K - Number of different paths

Returns:

K-shortest paths

Since:

0.3.0

getPathWeight

public static <E> double getPathWeight(List<E> path,
                       org.apache.commons.collections15.Transformer<E,Double> nev)

Returns the weight of a path given the sequence of edges.

Type Parameters:

E - Class type for edges

Parameters:

path - Sequence of edges

nev - Object responsible for returning weights for edges

Returns:

Path weight

Since:

0.2.0

getShortestPath

public static <V,E> List<E> getShortestPath(edu.uci.ics.jung.graph.Graph<V,E> graph,
                            org.apache.commons.collections15.Transformer<E,Double> nev,
                            V originNodeId,
                            V destinationNodeId)

Returns the shortest path between two nodes using Dijkstra's algorithm.

Type Parameters:

V - Vertex type

E - Edge type

Parameters:

graph - Graph representing the network

nev - Object responsible for returning weights for edges

originNodeId - Origin node

destinationNodeId - Destination node

Returns:

Shortest path

Since:

0.3.0

getTwoLinkDisjointPaths

public static <V,E> List<List<E>> getTwoLinkDisjointPaths(edu.uci.ics.jung.graph.Graph<V,E> graph,
                                          org.apache.commons.collections15.Transformer<E,Double> nev,
                                          V originNodeId,
                                          V destinationNodeId)

Returns the shortest pair of link-disjoint paths, where each item represents a path. 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.

Type Parameters:

V - Vertex type

E - Edge type

Parameters:

graph - Graph representing the network

nev - Object responsible for returning weights for edges

originNodeId - Origin node

destinationNodeId - Destination node

Returns:

Shortest pair of link-disjoint paths

Since:

0.3.0

getTwoNodeDisjointPaths

public static List<List<Long>> getTwoNodeDisjointPaths(edu.uci.ics.jung.graph.Graph<Long,Long> graph,
                                       org.apache.commons.collections15.Transformer<Long,Double> nev,
                                       long originNode,
                                       long destinationNode)

Returns the shortest pair of node-disjoint paths, where each item represents a path. 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:

graph - Graph representing the network

nev - Object responsible for returning weights for edges

originNode - Origin node

destinationNode - Origin node

Returns:

Shortest pair of node-disjoint paths

Since:

0.3.0

isBidirectional

public static boolean isBidirectional(edu.uci.ics.jung.graph.Graph graph)

Check whether the topology has the same number of links between each node pair in both directions (assuming multi-digraphs).

Parameters:

graph - The graph to analyze

Returns:

true if the graph is bidirectional, and false otherwise

Since:

0.2.0

isSimple

public static boolean isSimple(edu.uci.ics.jung.graph.Graph graph)

Check whether the graph is simple, that is, if it has at most one link between each node pair (one per direction under directed graphs, one under undirected graphs).

Parameters:

graph - The graph to analyze

Returns:

true if the graph is simple, and false otherwise

Since:

0.2.0

isWeightedBidirectional

public static <V,E> boolean isWeightedBidirectional(edu.uci.ics.jung.graph.Graph<V,E> graph,
                                    org.apache.commons.collections15.Transformer<E,Double> nev)

Checks whether the graph has the same number of links between each node pair in both directions (assuming multi-digraphs) and same individual weights per direction.

Type Parameters:

V - Vertex type

E - Edge type

Parameters:

graph - The graph to analyze

nev - Object responsible for returning weights for edges

Returns:

true if the graph is weighted-bidirectional, and false otherwise. By convention returns false if network is empty

Since:

0.2.0

simplifyGraph

public static <V,E> edu.uci.ics.jung.graph.Graph<V,E> simplifyGraph(edu.uci.ics.jung.graph.Graph<V,E> graph,
                                                    org.apache.commons.collections15.Transformer<E,Double> nev)

Given an input graph that may contain multiple edges between some vertex pairs, returns a new graph where only appears, for each vertex pair, the edge having the lowest weight (edges whose weight is equal to Double.MAX_VALUE are excluded). Ties are broken arbitrarely.

Important: Returned graph is not backed in the input one, so changes will not be reflected on it.

Type Parameters:

V - Vertex type

E - Edge type

Parameters:

graph - Graph representing the network

nev - Object responsible for returning weights for edges

Returns:

Copy of the input graph with at most an edge between each vertex pair

Since:

0.3.0