Package org.jgrapht
Class Graphs
 java.lang.Object

 org.jgrapht.Graphs

public abstract class Graphs extends Object
A collection of utilities to assist with graph manipulation. Author:
 Barak Naveh


Constructor Summary
Constructors Constructor Description Graphs()

Method Summary
All Methods Static Methods Concrete Methods Modifier and Type Method Description static <V,E>
booleanaddAllEdges(Graph<? super V,? super E> destination, Graph<V,E> source, Collection<? extends E> edges)
Adds a subset of the edges of the specified source graph to the specified destination graph.static <V,E>
booleanaddAllVertices(Graph<? super V,? super E> destination, Collection<? extends V> vertices)
Adds all of the specified vertices to the destination graph.static <V,E>
EaddEdge(Graph<V,E> g, V sourceVertex, V targetVertex, double weight)
Creates a new edge and adds it to the specified graph similarly to theGraph.addEdge(Object, Object)
method.static <V,E>
booleanaddEdgeWithVertices(Graph<V,E> targetGraph, Graph<V,E> sourceGraph, E edge)
Adds the specified edge to the graph, including its vertices if not already included.static <V,E>
EaddEdgeWithVertices(Graph<V,E> g, V sourceVertex, V targetVertex)
Adds the specified source and target vertices to the graph, if not already included, and creates a new edge and adds it to the specified graph similarly to theGraph.addEdge(Object, Object)
method.static <V,E>
EaddEdgeWithVertices(Graph<V,E> g, V sourceVertex, V targetVertex, double weight)
Adds the specified source and target vertices to the graph, if not already included, and creates a new weighted edge and adds it to the specified graph similarly to theGraph.addEdge(Object, Object)
method.static <V,E>
booleanaddGraph(Graph<? super V,? super E> destination, Graph<V,E> source)
Adds all the vertices and all the edges of the specified source graph to the specified destination graph.static <V,E>
voidaddGraphReversed(Graph<? super V,? super E> destination, Graph<V,E> source)
Adds all the vertices and all the edges of the specified source digraph to the specified destination digraph, reversing all of the edges.static <V,E>
voidaddIncomingEdges(Graph<V,E> graph, V target, Iterable<V> sources)
Add edges from multiple source vertices to one target vertex.static <V,E>
voidaddOutgoingEdges(Graph<V,E> graph, V source, Iterable<V> targets)
Add edges from one source vertex to multiple target vertices.static <V,E>
VgetOppositeVertex(Graph<V,E> g, E e, V v)
Gets the vertex opposite another vertex across an edge.static <V,E>
VertexToIntegerMapping<V>getVertexToIntegerMapping(Graph<V,E> graph)
Compute a new mapping from the vertices of a graph to the integer range $[0, n)$ where $n$ is the number of vertices in the graph.static <V,E>
List<V>neighborListOf(Graph<V,E> g, V vertex)
Returns a list of vertices that are the neighbors of a specified vertex.static <V,E>
Set<V>neighborSetOf(Graph<V,E> g, V vertex)
Returns a set of vertices that are neighbors of a specified vertex.static <V,E>
List<V>predecessorListOf(Graph<V,E> g, V vertex)
Returns a list of vertices that are the direct predecessors of a specified vertex.static <V,E>
booleanremoveVertexAndPreserveConnectivity(Graph<V,E> graph, Iterable<V> vertices)
Removes all the given vertices from the given graph.static <V,E>
booleanremoveVertexAndPreserveConnectivity(Graph<V,E> graph, V vertex)
Removes the given vertex from the given graph.static <V,E>
booleanremoveVerticesAndPreserveConnectivity(Graph<V,E> graph, Predicate<V> predicate)
Filters vertices from the given graph and subsequently removes them.static <V,E>
List<V>successorListOf(Graph<V,E> g, V vertex)
Returns a list of vertices that are the direct successors of a specified vertex.static <V,E>
booleantestIncidence(Graph<V,E> g, E e, V v)
Tests whether an edge is incident to a vertex.static <V,E>
Graph<V,E>undirectedGraph(Graph<V,E> g)
Returns an undirected view of the specified graph.static <V,E>
booleanvertexHasPredecessors(Graph<V,E> graph, V vertex)
Check if a vertex has any direct predecessors.static <V,E>
booleanvertexHasSuccessors(Graph<V,E> graph, V vertex)
Check if a vertex has any direct successors.



Method Detail

addEdge
public static <V,E> E addEdge(Graph<V,E> g, V sourceVertex, V targetVertex, double weight)
Creates a new edge and adds it to the specified graph similarly to theGraph.addEdge(Object, Object)
method. Type Parameters:
V
 the graph vertex typeE
 the graph edge type Parameters:
g
 the graph for which the edge to be addedsourceVertex
 source vertex of the edgetargetVertex
 target vertex of the edgeweight
 weight of the edge Returns:
 The newly created edge if added to the graph, otherwise
null
.  Throws:
UnsupportedOperationException
 if the graph has no edge supplier See Also:
Graph.addEdge(Object, Object)

addEdgeWithVertices
public static <V,E> E addEdgeWithVertices(Graph<V,E> g, V sourceVertex, V targetVertex)
Adds the specified source and target vertices to the graph, if not already included, and creates a new edge and adds it to the specified graph similarly to theGraph.addEdge(Object, Object)
method. Type Parameters:
V
 the graph vertex typeE
 the graph edge type Parameters:
g
 the graph for which the specified edge to be addedsourceVertex
 source vertex of the edgetargetVertex
 target vertex of the edge Returns:
 The newly created edge if added to the graph, otherwise
null
.

addEdgeWithVertices
public static <V,E> boolean addEdgeWithVertices(Graph<V,E> targetGraph, Graph<V,E> sourceGraph, E edge)
Adds the specified edge to the graph, including its vertices if not already included. Type Parameters:
V
 the graph vertex typeE
 the graph edge type Parameters:
targetGraph
 the graph for which the specified edge to be addedsourceGraph
 the graph in which the specified edge is already presentedge
 edge to add Returns:
true
if the target graph did not already contain the specified edge.

addEdgeWithVertices
public static <V,E> E addEdgeWithVertices(Graph<V,E> g, V sourceVertex, V targetVertex, double weight)
Adds the specified source and target vertices to the graph, if not already included, and creates a new weighted edge and adds it to the specified graph similarly to theGraph.addEdge(Object, Object)
method. Type Parameters:
V
 the graph vertex typeE
 the graph edge type Parameters:
g
 the graph for which the specified edge to be addedsourceVertex
 source vertex of the edgetargetVertex
 target vertex of the edgeweight
 weight of the edge Returns:
 The newly created edge if added to the graph, otherwise
null
.

addGraph
public static <V,E> boolean addGraph(Graph<? super V,? super E> destination, Graph<V,E> source)
Adds all the vertices and all the edges of the specified source graph to the specified destination graph. First all vertices of the source graph are added to the destination graph. Then every edge of the source graph is added to the destination graph. This method returnstrue
if the destination graph has been modified as a result of this operation, otherwise it returnsfalse
.The behavior of this operation is undefined if any of the specified graphs is modified while operation is in progress.
 Type Parameters:
V
 the graph vertex typeE
 the graph edge type Parameters:
destination
 the graph to which vertices and edges are addedsource
 the graph used as source for vertices and edges to add Returns:
true
if and only if the destination graph has been changed as a result of this operation.

addGraphReversed
public static <V,E> void addGraphReversed(Graph<? super V,? super E> destination, Graph<V,E> source)
Adds all the vertices and all the edges of the specified source digraph to the specified destination digraph, reversing all of the edges. If you want to do this as a linked view of the source graph (rather than by copying to a destination graph), useEdgeReversedGraph
instead.The behavior of this operation is undefined if any of the specified graphs is modified while operation is in progress.
 Type Parameters:
V
 the graph vertex typeE
 the graph edge type Parameters:
destination
 the graph to which vertices and edges are addedsource
 the graph used as source for vertices and edges to add See Also:
EdgeReversedGraph

addAllEdges
public static <V,E> boolean addAllEdges(Graph<? super V,? super E> destination, Graph<V,E> source, Collection<? extends E> edges)
Adds a subset of the edges of the specified source graph to the specified destination graph. The behavior of this operation is undefined if either of the graphs is modified while the operation is in progress.addEdgeWithVertices(org.jgrapht.Graph<V, E>, V, V)
is used for the transfer, so source vertexes will be added automatically to the target graph. Type Parameters:
V
 the graph vertex typeE
 the graph edge type Parameters:
destination
 the graph to which edges are to be addedsource
 the graph used as a source for edges to addedges
 the edges to be added Returns:
true
if this graph changed as a result of the call

addAllVertices
public static <V,E> boolean addAllVertices(Graph<? super V,? super E> destination, Collection<? extends V> vertices)
Adds all of the specified vertices to the destination graph. The behavior of this operation is undefined if the specified vertex collection is modified while the operation is in progress. This method will invoke theGraph.addVertex(Object)
method. Type Parameters:
V
 the graph vertex typeE
 the graph edge type Parameters:
destination
 the graph to which edges are to be addedvertices
 the vertices to be added to the graph Returns:
true
if graph changed as a result of the call Throws:
NullPointerException
 if the specified vertices contains one or more null vertices, or if the specified vertex collection isnull
. See Also:
Graph.addVertex(Object)

neighborListOf
public static <V,E> List<V> neighborListOf(Graph<V,E> g, V vertex)
Returns a list of vertices that are the neighbors of a specified vertex. If the graph is a multigraph vertices may appear more than once in the returned list.The method uses
Graph.edgesOf(Object)
to traverse the graph. Type Parameters:
V
 the graph vertex typeE
 the graph edge type Parameters:
g
 the graph to look for neighbors invertex
 the vertex to get the neighbors of Returns:
 a list of the vertices that are the neighbors of the specified vertex.

neighborSetOf
public static <V,E> Set<V> neighborSetOf(Graph<V,E> g, V vertex)
Returns a set of vertices that are neighbors of a specified vertex. Type Parameters:
V
 the graph vertex typeE
 the graph edge type Parameters:
g
 the graph to look for neighbors invertex
 the vertex to get the neighbors of Returns:
 a set of the vertices that are neighbors of the specified vertex

predecessorListOf
public static <V,E> List<V> predecessorListOf(Graph<V,E> g, V vertex)
Returns a list of vertices that are the direct predecessors of a specified vertex. If the graph is a multigraph, vertices may appear more than once in the returned list.The method uses
Graph.incomingEdgesOf(Object)
to traverse the graph. Type Parameters:
V
 the graph vertex typeE
 the graph edge type Parameters:
g
 the graph to look for predecessors invertex
 the vertex to get the predecessors of Returns:
 a list of the vertices that are the direct predecessors of the specified vertex.

successorListOf
public static <V,E> List<V> successorListOf(Graph<V,E> g, V vertex)
Returns a list of vertices that are the direct successors of a specified vertex. If the graph is a multigraph vertices may appear more than once in the returned list.The method uses
Graph.outgoingEdgesOf(Object)
to traverse the graph. Type Parameters:
V
 the graph vertex typeE
 the graph edge type Parameters:
g
 the graph to look for successors invertex
 the vertex to get the successors of Returns:
 a list of the vertices that are the direct successors of the specified vertex.

undirectedGraph
public static <V,E> Graph<V,E> undirectedGraph(Graph<V,E> g)
Returns an undirected view of the specified graph. If the specified graph is directed, returns an undirected view of it. If the specified graph is already undirected, just returns it. Type Parameters:
V
 the graph vertex typeE
 the graph edge type Parameters:
g
 the graph for which an undirected view is to be returned Returns:
 an undirected view of the specified graph, if it is directed, or or the specified graph itself if it is already undirected.
 Throws:
IllegalArgumentException
 if the graph is neither directed nor undirected See Also:
AsUndirectedGraph

testIncidence
public static <V,E> boolean testIncidence(Graph<V,E> g, E e, V v)
Tests whether an edge is incident to a vertex. Type Parameters:
V
 the graph vertex typeE
 the graph edge type Parameters:
g
 graph containing e and ve
 edge in gv
 vertex in g Returns:
 true iff e is incident on v

getOppositeVertex
public static <V,E> V getOppositeVertex(Graph<V,E> g, E e, V v)
Gets the vertex opposite another vertex across an edge. Type Parameters:
V
 the graph vertex typeE
 the graph edge type Parameters:
g
 graph containing e and ve
 edge in gv
 vertex in g Returns:
 vertex opposite to v across e

removeVertexAndPreserveConnectivity
public static <V,E> boolean removeVertexAndPreserveConnectivity(Graph<V,E> graph, V vertex)
Removes the given vertex from the given graph. If the vertex to be removed has one or more predecessors, the predecessors will be connected directly to the successors of the vertex to be removed. Type Parameters:
V
 the graph vertex typeE
 the graph edge type Parameters:
graph
 graph to be mutatedvertex
 vertex to be removed from this graph, if present Returns:
 true if the graph contained the specified vertex; false otherwise.

removeVerticesAndPreserveConnectivity
public static <V,E> boolean removeVerticesAndPreserveConnectivity(Graph<V,E> graph, Predicate<V> predicate)
Filters vertices from the given graph and subsequently removes them. If the vertex to be removed has one or more predecessors, the predecessors will be connected directly to the successors of the vertex to be removed. Type Parameters:
V
 the graph vertex typeE
 the graph edge type Parameters:
graph
 graph to be mutatedpredicate
 a noninterfering stateless predicate to apply to each vertex to determine if it should be removed from the graph Returns:
 true if at least one vertex has been removed; false otherwise.

removeVertexAndPreserveConnectivity
public static <V,E> boolean removeVertexAndPreserveConnectivity(Graph<V,E> graph, Iterable<V> vertices)
Removes all the given vertices from the given graph. If the vertex to be removed has one or more predecessors, the predecessors will be connected directly to the successors of the vertex to be removed. Type Parameters:
V
 the graph vertex typeE
 the graph edge type Parameters:
graph
 to be mutatedvertices
 vertices to be removed from this graph, if present Returns:
 true if at least one vertex has been removed; false otherwise.

addOutgoingEdges
public static <V,E> void addOutgoingEdges(Graph<V,E> graph, V source, Iterable<V> targets)
Add edges from one source vertex to multiple target vertices. Whether duplicates are created depends on the underlyingGraph
implementation. Type Parameters:
V
 the graph vertex typeE
 the graph edge type Parameters:
graph
 graph to be mutatedsource
 source vertex of the new edgestargets
 target vertices for the new edges

addIncomingEdges
public static <V,E> void addIncomingEdges(Graph<V,E> graph, V target, Iterable<V> sources)
Add edges from multiple source vertices to one target vertex. Whether duplicates are created depends on the underlyingGraph
implementation. Type Parameters:
V
 the graph vertex typeE
 the graph edge type Parameters:
graph
 graph to be mutatedtarget
 target vertex for the new edgessources
 source vertices for the new edges

vertexHasSuccessors
public static <V,E> boolean vertexHasSuccessors(Graph<V,E> graph, V vertex)
Check if a vertex has any direct successors. Type Parameters:
V
 the graph vertex typeE
 the graph edge type Parameters:
graph
 the graph to look for successorsvertex
 the vertex to look for successors Returns:
 true if the vertex has any successors, false otherwise

vertexHasPredecessors
public static <V,E> boolean vertexHasPredecessors(Graph<V,E> graph, V vertex)
Check if a vertex has any direct predecessors. Type Parameters:
V
 the graph vertex typeE
 the graph edge type Parameters:
graph
 the graph to look for predecessorsvertex
 the vertex to look for predecessors Returns:
 true if the vertex has any predecessors, false otherwise

getVertexToIntegerMapping
public static <V,E> VertexToIntegerMapping<V> getVertexToIntegerMapping(Graph<V,E> graph)
Compute a new mapping from the vertices of a graph to the integer range $[0, n)$ where $n$ is the number of vertices in the graph. Type Parameters:
V
 the graph vertex typeE
 the graph edge type Parameters:
graph
 the input graph Returns:
 the mapping as an object containing the
vertexMap
and theindexList
 Throws:
NullPointerException
 ifgraph
isnull
 See Also:
VertexToIntegerMapping

