public static class GraphUtils.JUNGUtils extends Object
Auxiliary class to work with the graph library JUNG.
Constructor and Description 

JUNGUtils() 
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 edgedisjoint shortestpath pair algorithms to nodedisjoint 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 edgedisjoint shortestpath pair algorithms to nodedisjoint 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)
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> 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 <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 Kloopless 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 linkdisjoint 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 nodedisjoint 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 multidigraphs).

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 multidigraphs) 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). 
public static edu.uci.ics.jung.graph.Graph<Node,Link> buildAuxiliaryNodeDisjointGraph(edu.uci.ics.jung.graph.Graph<Node,Link> graph, Node originNode, Node destinationNode)
graph
 Graph representing the networkoriginNode
 Origin nodedestinationNode
 Destination nodepublic 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)
graph
 Graph representing the networknev
 Object responsible for returning weights for edgesoriginNode
 Origin nodedestinationNode
 Destination nodepublic 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)
V
 Vertex typeE
 Edge typegraph
 Graph representing the networkvertexPositionTransformer
 Object responsible for returning position for verticeswidth
 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 sizelinkThickness
 Link thicknesspublic 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.
V
 Class type for verticesE
 Class type for edgesgraph
 Graph representing the networkacceptedVertices
 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)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.
V
 Class type for verticesE
 Class type for edgesgraph
 Graph representing the networknev
 Object responsible for returning weights for edgespublic 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.
V
 Class type for verticesE
 Class type for edgesgraph
 Graph representing the networknev
 Object responsible for returning weights for edgesedgeSpareCapacityTransformer
 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 removedpublic 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)
Double.MAX_VALUE
are not considered.V
 Class type for verticesE
 Class type for edgesgraph
 Graph representing the networknev
 Object responsible for returning weights for edgesoriginNodeId
 Origin nodedestinationNodeId
 Destination nodeedgeSpareCapacityTransformer
 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 removedpublic static <E> org.apache.commons.collections15.Transformer<E,Double> getEdgeWeightTransformer(Map<E,Double> linkCosts)
E
 Edge typelinkCosts
 A mapping of edges to weights (null means 'allone' map)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.
nodes
 Collection of nodeslinks
 Collection of linksJUNG
graphpublic 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)
Double.MAX_VALUE
are not considered.V
 Class type for verticesE
 Class type for edgesgraph
 Graph representing the networknev
 Object responsible for returning weights for edgesoriginNodeId
 Origin nodedestinationNodeId
 Destination nodeK
 Number of different pathspublic static <E> double getPathWeight(List<E> path, org.apache.commons.collections15.Transformer<E,Double> nev)
E
 Class type for edgespath
 Sequence of edgesnev
 Object responsible for returning weights for edgespublic 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)
Double.MAX_VALUE
are not considered.V
 Vertex typeE
 Edge typegraph
 Graph representing the networknev
 Object responsible for returning weights for edgesoriginNodeId
 Origin nodedestinationNodeId
 Destination nodepublic 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)
size()
= 1, only one path was found; and when size()
= 2, the linkdisjoint paths were found. Internally it uses the SuurballeTarjan algorithm.V
 Vertex typeE
 Edge typegraph
 Graph representing the networknev
 Object responsible for returning weights for edgesoriginNodeId
 Origin nodedestinationNodeId
 Destination nodepublic 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)
size()
= 1, only one path was found; and when size()
= 2, the nodedisjoint paths were found. Internally it uses the SuurballeTarjan algorithm.graph
 Graph representing the networknev
 Object responsible for returning weights for edgesoriginNode
 Origin nodedestinationNode
 Origin nodepublic static boolean isBidirectional(edu.uci.ics.jung.graph.Graph graph)
graph
 The graph to analyzetrue
if the graph is bidirectional, and false otherwisepublic static boolean isSimple(edu.uci.ics.jung.graph.Graph graph)
graph
 The graph to analyzetrue
if the graph is simple, and false otherwisepublic static <V,E> boolean isWeightedBidirectional(edu.uci.ics.jung.graph.Graph<V,E> graph, org.apache.commons.collections15.Transformer<E,Double> nev)
V
 Vertex typeE
 Edge typegraph
 The graph to analyzenev
 Object responsible for returning weights for edgestrue
if the graph is weightedbidirectional, and false otherwise. By convention returns false
if network is emptypublic 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)
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.
V
 Vertex typeE
 Edge typegraph
 Graph representing the networknev
 Object responsible for returning weights for edgesCopyright © 2017. All rights reserved.