org.jgrapht

## Class GraphTests

• public abstract class GraphTests
extends Object
A collection of utilities to test for various graph properties.
Author:
Barak Naveh, Dimitrios Michail, Joris Kinable
• ### Constructor Summary

Constructors
Constructor and Description
GraphTests()
• ### Method Summary

All Methods
Modifier and Type Method and Description
static <V,E> boolean isBipartite(Graph<V,E> graph)
Test whether a graph is bipartite.
static <V,E> boolean isBipartitePartition(Graph<V,E> graph, Set<? extends V> firstPartition, Set<? extends V> secondPartition)
Test whether a partition of the vertices into two sets is a bipartite partition.
static <V,E> boolean isComplete(Graph<V,E> graph)
Test whether a graph is complete.
static <V,E> boolean isConnected(Graph<V,E> graph)
Test whether an undirected graph is connected.
static <V,E> boolean isCubic(Graph<V,E> graph)
Tests whether a graph is cubic.
static <V,E> boolean isEmpty(Graph<V,E> graph)
Test whether a graph is empty.
static <V,E> boolean isEulerian(Graph<V,E> graph)
Test whether a graph is Eulerian.
static <V,E> boolean isForest(Graph<V,E> graph)
Test whether an undirected graph is a forest.
static <V,E> boolean isOverfull(Graph<V,E> graph)
Test whether a graph is overfull.
static <V,E> boolean isSimple(Graph<V,E> graph)
Check if a graph is simple.
static <V,E> boolean isSplit(Graph<V,E> graph)
Test whether an undirected graph is a split graph.
static <V,E> boolean isStronglyConnected(Graph<V,E> graph)
Test whether a directed graph is strongly connected.
static <V,E> boolean isTree(Graph<V,E> graph)
Test whether an undirected graph is a tree.
static <V,E> boolean isWeaklyConnected(Graph<V,E> graph)
Test whether a directed graph is weakly connected.
static <V,E> Graph<V,E> requireDirected(Graph<V,E> graph)
Checks that the specified graph is directed and throws an IllegalArgumentException if it is not.
static <V,E> Graph<V,E> requireDirected(Graph<V,E> graph, String message)
Checks that the specified graph is directed and throws a customized IllegalArgumentException if it is not.
static <V,E> Graph<V,E> requireDirectedOrUndirected(Graph<V,E> graph)
Checks that the specified graph is directed and throws an IllegalArgumentException if it is not.
static <V,E> Graph<V,E> requireDirectedOrUndirected(Graph<V,E> graph, String message)
Checks that the specified graph is directed or undirected and throws a customized IllegalArgumentException if it is not.
static <V,E> Graph<V,E> requireUndirected(Graph<V,E> graph)
Checks that the specified graph is undirected and throws an IllegalArgumentException if it is not.
static <V,E> Graph<V,E> requireUndirected(Graph<V,E> graph, String message)
Checks that the specified graph is undirected and throws a customized IllegalArgumentException if it is not.
• ### Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
• ### Constructor Detail

• #### GraphTests

public GraphTests()
• ### Method Detail

• #### isEmpty

public static <V,E> boolean isEmpty(Graph<V,E> graph)
Test whether a graph is empty. An empty graph on n nodes consists of n isolated vertices with no edges.
Type Parameters:
V - the graph vertex type
E - the graph edge type
Parameters:
graph - the input graph
Returns:
true if the graph is empty, false otherwise
• #### isSimple

public static <V,E> boolean isSimple(Graph<V,E> graph)
Check if a graph is simple. A graph is simple if it has no self-loops and multiple edges.
Type Parameters:
V - the graph vertex type
E - the graph edge type
Parameters:
graph - a graph
Returns:
true if a graph is simple, false otherwise
• #### isComplete

public static <V,E> boolean isComplete(Graph<V,E> graph)
Test whether a graph is complete. A complete undirected graph is a simple graph in which every pair of distinct vertices is connected by a unique edge. A complete directed graph is a directed graph in which every pair of distinct vertices is connected by a pair of unique edges (one in each direction).
Type Parameters:
V - the graph vertex type
E - the graph edge type
Parameters:
graph - the input graph
Returns:
true if the graph is complete, false otherwise
• #### isConnected

public static <V,E> boolean isConnected(Graph<V,E> graph)
Test whether an undirected graph is connected.

This method does not performing any caching, instead recomputes everything from scratch. In case more control is required use ConnectivityInspector directly.

Type Parameters:
V - the graph vertex type
E - the graph edge type
Parameters:
graph - the input graph
Returns:
true if the graph is connected, false otherwise
ConnectivityInspector
• #### isWeaklyConnected

public static <V,E> boolean isWeaklyConnected(Graph<V,E> graph)
Test whether a directed graph is weakly connected.

This method does not performing any caching, instead recomputes everything from scratch. In case more control is required use ConnectivityInspector directly.

Type Parameters:
V - the graph vertex type
E - the graph edge type
Parameters:
graph - the input graph
Returns:
true if the graph is weakly connected, false otherwise
ConnectivityInspector
• #### isStronglyConnected

public static <V,E> boolean isStronglyConnected(Graph<V,E> graph)
Test whether a directed graph is strongly connected.

This method does not performing any caching, instead recomputes everything from scratch. In case more control is required use KosarajuStrongConnectivityInspector directly.

Type Parameters:
V - the graph vertex type
E - the graph edge type
Parameters:
graph - the input graph
Returns:
true if the graph is strongly connected, false otherwise
KosarajuStrongConnectivityInspector
• #### isTree

public static <V,E> boolean isTree(Graph<V,E> graph)
Test whether an undirected graph is a tree.
Type Parameters:
V - the graph vertex type
E - the graph edge type
Parameters:
graph - the input graph
Returns:
true if the graph is tree, false otherwise
• #### isForest

public static <V,E> boolean isForest(Graph<V,E> graph)
Test whether an undirected graph is a forest. A forest is a set of disjoint trees. By definition, any acyclic graph is a forest. This includes the empty graph and the class of tree graphs.
Type Parameters:
V - the graph vertex type
E - the graph edge type
Parameters:
graph - the input graph
Returns:
true if the graph is forest, false otherwise
• #### isOverfull

public static <V,E> boolean isOverfull(Graph<V,E> graph)
Test whether a graph is overfull. A graph is overfull if $|E|>\Delta(G)\lfloor |V|/2 \rfloor$, where $\Delta(G)$ is the maximum degree of the graph.
Type Parameters:
V - the graph vertex type
E - the graph edge type
Parameters:
graph - the input graph
Returns:
true if the graph is overfull, false otherwise
• #### isSplit

public static <V,E> boolean isSplit(Graph<V,E> graph)
Test whether an undirected graph is a split graph. A split graph is a graph in which the vertices can be partitioned into a clique and an independent set. Split graphs are a special class of chordal graphs. Given the degree sequence $d_1 \geq,\dots,\geq d_n$ of $G$, a graph is a split graph if and only if : $\sum_{i=1}^m d_i = m (m - 1) + \sum_{i=m + 1}^nd_i$, where $m = \max_i \{d_i\geq i-1\}$. If the graph is a split graph, then the $m$ vertices with the largest degrees form a maximum clique in $G$, and the remaining vertices constitute an independent set. See Brandstadt, A., Le, V., Spinrad, J. Graph Classes: A Survey. Philadelphia, PA: SIAM, 1999. for details.
Type Parameters:
V - the graph vertex type
E - the graph edge type
Parameters:
graph - the input graph
Returns:
true if the graph is a split graph, false otherwise
• #### isBipartite

public static <V,E> boolean isBipartite(Graph<V,E> graph)
Test whether a graph is bipartite.
Type Parameters:
V - the graph vertex type
E - the graph edge type
Parameters:
graph - the input graph
Returns:
true if the graph is bipartite, false otherwise
• #### isBipartitePartition

public static <V,E> boolean isBipartitePartition(Graph<V,E> graph,
Set<? extends V> firstPartition,
Set<? extends V> secondPartition)
Test whether a partition of the vertices into two sets is a bipartite partition.
Type Parameters:
V - the graph vertex type
E - the graph edge type
Parameters:
graph - the input graph
firstPartition - the first vertices partition
secondPartition - the second vertices partition
Returns:
true if the partition is a bipartite partition, false otherwise
• #### isCubic

public static <V,E> boolean isCubic(Graph<V,E> graph)
Tests whether a graph is cubic. A graph is cubic if all vertices have degree 3.
Type Parameters:
V - the graph vertex type
E - the graph edge type
Parameters:
graph - the input graph
Returns:
true if the graph is cubic, false otherwise
• #### isEulerian

public static <V,E> boolean isEulerian(Graph<V,E> graph)
Test whether a graph is Eulerian. An undirected graph is Eulerian if it is connected and each vertex has an even degree. A directed graph is Eulerian if it is strongly connected and each vertex has the same incoming and outgoing degree. Test whether a graph is Eulerian. An Eulerian graph is a graph containing an Eulerian cycle.
Type Parameters:
V - the graph vertex type
E - the graph edge type
Parameters:
graph - the input graph
Returns:
true if the graph is Eulerian, false otherwise
HierholzerEulerianCycle.isEulerian(Graph)
• #### requireDirected

public static <V,E> Graph<V,E> requireDirected(Graph<V,E> graph,
String message)
Checks that the specified graph is directed and throws a customized IllegalArgumentException if it is not. Also checks that the graph reference is not null and throws a NullPointerException if it is.
Type Parameters:
V - the graph vertex type
E - the graph edge type
Parameters:
graph - the graph reference to check for beeing directed and not null
message - detail message to be used in the event that an exception is thrown
Returns:
graph if directed and not null
Throws:
NullPointerException - if graph is null
IllegalArgumentException - if graph is not directed
• #### requireDirected

public static <V,E> Graph<V,E> requireDirected(Graph<V,E> graph)
Checks that the specified graph is directed and throws an IllegalArgumentException if it is not. Also checks that the graph reference is not null and throws a NullPointerException if it is.
Type Parameters:
V - the graph vertex type
E - the graph edge type
Parameters:
graph - the graph reference to check for beeing directed and not null
Returns:
graph if directed and not null
Throws:
NullPointerException - if graph is null
IllegalArgumentException - if graph is not directed
• #### requireUndirected

public static <V,E> Graph<V,E> requireUndirected(Graph<V,E> graph,
String message)
Checks that the specified graph is undirected and throws a customized IllegalArgumentException if it is not. Also checks that the graph reference is not null and throws a NullPointerException if it is.
Type Parameters:
V - the graph vertex type
E - the graph edge type
Parameters:
graph - the graph reference to check for being undirected and not null
message - detail message to be used in the event that an exception is thrown
Returns:
graph if undirected and not null
Throws:
NullPointerException - if graph is null
IllegalArgumentException - if graph is not undirected
• #### requireUndirected

public static <V,E> Graph<V,E> requireUndirected(Graph<V,E> graph)
Checks that the specified graph is undirected and throws an IllegalArgumentException if it is not. Also checks that the graph reference is not null and throws a NullPointerException if it is.
Type Parameters:
V - the graph vertex type
E - the graph edge type
Parameters:
graph - the graph reference to check for being undirected and not null
Returns:
graph if undirected and not null
Throws:
NullPointerException - if graph is null
IllegalArgumentException - if graph is not undirected
• #### requireDirectedOrUndirected

public static <V,E> Graph<V,E> requireDirectedOrUndirected(Graph<V,E> graph,
String message)
Checks that the specified graph is directed or undirected and throws a customized IllegalArgumentException if it is not. Also checks that the graph reference is not null and throws a NullPointerException if it is.
Type Parameters:
V - the graph vertex type
E - the graph edge type
Parameters:
graph - the graph reference to check for beeing directed or undirected and not null
message - detail message to be used in the event that an exception is thrown
Returns:
graph if directed and not null
Throws:
NullPointerException - if graph is null
IllegalArgumentException - if graph is mixed
• #### requireDirectedOrUndirected

public static <V,E> Graph<V,E> requireDirectedOrUndirected(Graph<V,E> graph)
Checks that the specified graph is directed and throws an IllegalArgumentException if it is not. Also checks that the graph reference is not null and throws a NullPointerException if it is.
Type Parameters:
V - the graph vertex type
E - the graph edge type
Parameters:
graph - the graph reference to check for beeing directed and not null
Returns:
graph if directed and not null
Throws:
NullPointerException - if graph is null
IllegalArgumentException - if graph is mixed