org.jgrapht

Class GraphTests

java.lang.Object

org.jgrapht.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

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

See Also:

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

See Also:

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

See Also:

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

See Also:

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