```
public abstract class GraphTests
extends Object
```
A collection of utilities to test for various graph properties.

Author:

Barak Naveh, Dimitrios Michail, Joris Kinable, Alexandru Valeanu

Constructor Summary

Constructors
Constructor Description

GraphTests()

Method Summary

All Methods Static Methods Concrete Methods
Modifier and Type	Method	Description
`static <V,E> boolean`	`hasMultipleEdges(Graph<V,E> graph)`	Check if a graph has multiple edges (parallel edges), that is, whether the graph contains two or more edges connecting the same pair of vertices.
`static <V,E> boolean`	`hasOreProperty(Graph<V,E> graph)`	Tests whether an undirected graph meets Ore's condition to be Hamiltonian.
`static <V,E> boolean`	`hasSelfLoops(Graph<V,E> graph)`	Check if a graph has self-loops.
`static <V,E> boolean`	`isBiconnected(Graph<V,E> graph)`	Tests if the inspected graph is biconnected.
`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`	`isChordal(Graph<V,E> graph)`	Checks whether a graph is chordal.
`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 if the inspected 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`	`isK33Subdivision(Graph<V,E> graph)`	Checks whether the `graph` is a $K_{3,3}$ subdivision.
`static <V,E> boolean`	`isK5Subdivision(Graph<V,E> graph)`	Checks whether the `graph` is a $K_5$ subdivision.
`static <V,E> boolean`	`isKuratowskiSubdivision(Graph<V,E> graph)`	Checks whether the `graph` is a Kuratowski subdivision.
`static <V,E> boolean`	`isOverfull(Graph<V,E> graph)`	Test whether a graph is overfull.
`static <V,E> boolean`	`isPerfect(Graph<V,E> graph)`	Checks that the specified graph is perfect.
`static <V,E> boolean`	`isPlanar(Graph<V,E> graph)`	Checks that the specified graph is planar.
`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 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`	`isTriangleFree(Graph<V,E> graph)`	Tests whether an undirected graph is triangle-free (i.e.
`static <V,E> boolean`	`isWeaklyChordal(Graph<V,E> graph)`	Checks whether a graph is weakly chordal.
`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.
`static <V,E> Graph<V,E>`	`requireWeighted(Graph<V,E> graph)`	Checks that the specified graph is weighted 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 (parallel) 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
  - hasSelfLoops
```
public static <V,E> boolean hasSelfLoops(Graph<V,E> graph)
```
    Check if a graph has self-loops. A self-loop is an edge with the same source and target vertices.
    
    Type Parameters:
    
    V - the graph vertex type
    
    E - the graph edge type
    
    Parameters:
    
    graph - a graph
    
    Returns:
    
    true if a graph has self-loops, false otherwise
  - hasMultipleEdges
```
public static <V,E> boolean hasMultipleEdges(Graph<V,E> graph)
```
    Check if a graph has multiple edges (parallel edges), that is, whether the graph contains two or more edges connecting the same pair of vertices.
    
    Type Parameters:
    
    V - the graph vertex type
    
    E - the graph edge type
    
    Parameters:
    
    graph - a graph
    
    Returns:
    
    true if a graph has multiple edges, 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 if the inspected graph is connected. A graph is connected when, while ignoring edge directionality, there exists a path between every pair of vertices. In a connected graph, there are no unreachable vertices. When the inspected graph is a directed graph, this method returns true if and only if the inspected graph is weakly connected. An empty graph is not considered 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
  - isBiconnected
```
public static <V,E> boolean isBiconnected(Graph<V,E> graph)
```
    Tests if the inspected graph is biconnected. A biconnected graph is a connected graph on two or more vertices having no cutpoints.
    This method does not performing any caching, instead recomputes everything from scratch. In case more control is required use BiconnectivityInspector directly.
    
    Type Parameters:
    
    V - the graph vertex type
    
    E - the graph edge type
    
    Parameters:
    
    graph - the input graph
    
    Returns:
    
    true if the graph is biconnected, false otherwise
    
    See Also:
    
    BiconnectivityInspector
  - 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 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.
    In case of undirected graphs this method delegated to isConnected(Graph).
    
    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
    
    See Also:
    
    BipartitePartitioning.isBipartite()
  - 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
    
    See Also:
    
    BipartitePartitioning.isValidPartitioning(PartitioningAlgorithm.Partitioning)
  - 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)
  - isChordal
```
public static <V,E> boolean isChordal(Graph<V,E> graph)
```
    Checks whether a graph is chordal. A chordal graph is one in which all cycles of four or more vertices have a chord, which is an edge that is not part of the cycle but connects two vertices of the cycle.
    
    Type Parameters:
    
    V - the graph vertex type
    
    E - the graph edge type
    
    Parameters:
    
    graph - the input graph
    
    Returns:
    
    true if the graph is chordal, false otherwise
    
    See Also:
    
    ChordalityInspector.isChordal()
  - isWeaklyChordal
```
public static <V,E> boolean isWeaklyChordal(Graph<V,E> graph)
```
    Checks whether a graph is weakly chordal.
    The following definitions are equivalent:
    
    A graph is weakly chordal (weakly triangulated) if neither it nor its complement contains a chordless cycles with five or more vertices.
    
    A 2-pair in a graph is a pair of non-adjacent vertices $x$, $y$ such that every chordless path has exactly two edges. A graph is weakly chordal if every connected induced subgraph $H$ that is not a complete graph, contains a 2-pair.
    Type Parameters:
    
    V - the graph vertex type
    
    E - the graph edge type
    
    Parameters:
    
    graph - the input graph
    
    Returns:
    
    true if the graph is weakly chordal, false otherwise
    
    See Also:
    
    WeakChordalityInspector.isWeaklyChordal()
  - hasOreProperty
```
public static <V,E> boolean hasOreProperty(Graph<V,E> graph)
```
    Tests whether an undirected graph meets Ore's condition to be Hamiltonian. Let $G$ be a (finite and simple) graph with $n \geq 3$ vertices. We denote by $deg(v)$ the degree of a vertex $v$ in $G$, i.e. the number of incident edges in $G$ to $v$. Then, Ore's theorem states that if $deg(v) + deg(w) \geq n$ for every pair of distinct non-adjacent vertices $v$ and $w$ of $G$, then $G$ is Hamiltonian.
    
    Type Parameters:
    
    V - the graph vertex type
    
    E - the graph edge type
    
    Parameters:
    
    graph - the input graph
    
    Returns:
    
    true if the graph meets Ore's condition, false otherwise
    
    See Also:
    
    PalmerHamiltonianCycle
  - isTriangleFree
```
public static <V,E> boolean isTriangleFree(Graph<V,E> graph)
```
    Tests whether an undirected graph is triangle-free (i.e. no three distinct vertices form a triangle of edges). The implementation of this method uses GraphMetrics.getNumberOfTriangles(Graph).
    
    Type Parameters:
    
    V - the graph vertex type
    
    E - the graph edge type
    
    Parameters:
    
    graph - the input graph
    
    Returns:
    
    true if the graph is triangle-free, false otherwise
  - isPerfect
```
public static <V,E> boolean isPerfect(Graph<V,E> graph)
```
    Checks that the specified graph is perfect. Due to the Strong Perfect Graph Theorem Berge Graphs are the same as perfect Graphs. The implementation of this method is delegated to BergeGraphInspector
    
    Type Parameters:
    
    V - the graph vertex type
    
    E - the graph edge type
    
    Parameters:
    
    graph - the graph reference to check for being perfect or not
    
    Returns:
    
    true if the graph is perfect, false otherwise
  - isPlanar
```
public static <V,E> boolean isPlanar(Graph<V,E> graph)
```
    Checks that the specified graph is planar. A graph is planar if it can be drawn on a two-dimensional plane without any of its edges crossing. The implementation of the method is delegated to the BoyerMyrvoldPlanarityInspector. Also, use this class to get a planar embedding of the graph in case it is planar, or a Kuratowski subgraph as a certificate of nonplanarity.
    
    Type Parameters:
    
    V - the graph vertex type
    
    E - the graph edge type
    
    Parameters:
    
    graph - the graph to test planarity of
    
    Returns:
    
    true if the graph is planar, false otherwise
    
    See Also:
    
    PlanarityTestingAlgorithm, BoyerMyrvoldPlanarityInspector
  - isKuratowskiSubdivision
```
public static <V,E> boolean isKuratowskiSubdivision(Graph<V,E> graph)
```
    Checks whether the graph is a Kuratowski subdivision. Effectively checks whether the graph is a $K_{3,3}$ subdivision or $K_{5}$ subdivision
    
    Type Parameters:
    
    V - the graph vertex type
    
    E - the graph edge type
    
    Parameters:
    
    graph - the graph to test
    
    Returns:
    
    true if the graph is a Kuratowski subdivision, false otherwise
  - isK33Subdivision
```
public static <V,E> boolean isK33Subdivision(Graph<V,E> graph)
```
    Checks whether the graph is a $K_{3,3}$ subdivision.
    
    Type Parameters:
    
    V - the graph vertex type
    
    E - the graph edge type
    
    Parameters:
    
    graph - the graph to test
    
    Returns:
    
    true if the graph is a $K_{3,3}$ subdivision, false otherwise
  - isK5Subdivision
```
public static <V,E> boolean isK5Subdivision(Graph<V,E> graph)
```
    Checks whether the graph is a $K_5$ subdivision.
    
    Type Parameters:
    
    V - the graph vertex type
    
    E - the graph edge type
    
    Parameters:
    
    graph - the graph to test
    
    Returns:
    
    true if the graph is a $K_5$ subdivision, false otherwise
  - 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
  - requireWeighted
```
public static <V,E> Graph<V,E> requireWeighted(Graph<V,E> graph)
```
    Checks that the specified graph is weighted 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 weighted and not null
    
    Returns:
    
    graph if directed and not null
    
    Throws:
    
    NullPointerException - if graph is null
    
    IllegalArgumentException - if graph is not weighted

Class GraphTests

Constructor Summary

Method Summary

Methods inherited from class java.lang.Object

Constructor Detail

GraphTests

Method Detail

isEmpty

isSimple

hasSelfLoops

hasMultipleEdges

isComplete

isConnected

isBiconnected

isWeaklyConnected

isStronglyConnected

isTree

isForest

isOverfull

isSplit

isBipartite

isBipartitePartition

isCubic

isEulerian

isChordal

isWeaklyChordal

hasOreProperty

isTriangleFree

isPerfect

isPlanar

isKuratowskiSubdivision

isK33Subdivision

isK5Subdivision

requireDirected

requireDirected

requireUndirected

requireUndirected

requireDirectedOrUndirected

requireDirectedOrUndirected

requireWeighted