com.net2plan.libraries

Class GraphUtils.JUNGUtils

java.lang.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
JUNGUtils()

Method Summary

Modifier and Type	Method and Description
static edu.uci.ics.jung.graph.Graph<Node,Link>	buildAuxiliaryNodeDisjointGraph(edu.uci.ics.jung.graph.Graph<Node,Link> graph, Node originNode, Node 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<Node,Link>,org.apache.commons.collections15.Transformer<Link,Double>>	buildAuxiliaryNodeDisjointGraph(edu.uci.ics.jung.graph.Graph<Node,Link> graph, org.apache.commons.collections15.Transformer<Link,Double> nev, Node originNode, Node destinationNode) Builds an auxiliary graph for the application of edge-disjoint shortest-path pair algorithms to node-disjoint problems.
static <V,E> 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, 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 <E> org.apache.commons.collections15.Transformer<E,Double>	getEdgeWeightTransformer(Map<E,Double> linkCosts) Obtains a transformer for returning link weight from link identifier.
static edu.uci.ics.jung.graph.Graph<Node,Link>	getGraphFromLinkMap(Collection<Node> nodes, Collection<Link> links) Obtains a JUNG graph from a given set of links.
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<Link>>	getTwoNodeDisjointPaths(edu.uci.ics.jung.graph.Graph<Node,Link> graph, org.apache.commons.collections15.Transformer<Link,Double> nev, Node originNode, Node 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 java.lang.Object

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

Constructor Detail

JUNGUtils

public JUNGUtils()

Method Detail

buildAuxiliaryNodeDisjointGraph

public static edu.uci.ics.jung.graph.Graph<Node,Link> buildAuxiliaryNodeDisjointGraph(edu.uci.ics.jung.graph.Graph<Node,Link> graph,
                                                                                      Node originNode,
                                                                                      Node 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

buildAuxiliaryNodeDisjointGraph

public static Pair<edu.uci.ics.jung.graph.Graph<Node,Link>,org.apache.commons.collections15.Transformer<Link,Double>> buildAuxiliaryNodeDisjointGraph(edu.uci.ics.jung.graph.Graph<Node,Link> graph,
                                                                                                                                                      org.apache.commons.collections15.Transformer<Link,Double> nev,
                                                                                                                                                      Node originNode,
                                                                                                                                                      Node 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

createImage

public static <V,E> 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

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

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

getEdgeWeightTransformer

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

Obtains a transformer for returning link weight from link identifier.

Type Parameters:

E - Edge type

Parameters:

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

Returns:

A transformer for returning weights for edges

getGraphFromLinkMap

public static edu.uci.ics.jung.graph.Graph<Node,Link> getGraphFromLinkMap(Collection<Node> nodes,
                                                                          Collection<Link> links)

Obtains a JUNG graph from a given set of links.

Parameters:

nodes - Collection of nodes

links - Collection of links

Returns:

JUNG graph

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

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

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

getTwoNodeDisjointPaths

public static List<List<Link>> getTwoNodeDisjointPaths(edu.uci.ics.jung.graph.Graph<Node,Link> graph,
                                                       org.apache.commons.collections15.Transformer<Link,Double> nev,
                                                       Node originNode,
                                                       Node 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

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

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

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

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