 Author:
 Barak Naveh, Dimitrios Michail, Joris Kinable, Alexandru Valeanu

Constructor Summary

Method Summary
Modifier and TypeMethodDescriptionstatic <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 selfloops.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 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 Tests whether a graph is cubic.static <V,
E> boolean 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 Test whether an undirected graph is a forest.static <V,
E> boolean isK33Subdivision
(Graph<V, E> graph) Checks whether thegraph
is a $K_{3,3}$ subdivision.static <V,
E> boolean isK5Subdivision
(Graph<V, E> graph) Checks whether thegraph
is a $K_5$ subdivision.static <V,
E> boolean isKuratowskiSubdivision
(Graph<V, E> graph) Checks whether thegraph
is a Kuratowski subdivision.static <V,
E> boolean isOverfull
(Graph<V, E> graph) Test whether a graph is overfull.static <V,
E> boolean Checks that the specified graph is perfect.static <V,
E> boolean Checks that the specified graph is planar.static <V,
E> boolean Check if a graph is simple.static <V,
E> boolean 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 Test whether an undirected graph is a tree.static <V,
E> boolean isTriangleFree
(Graph<V, E> graph) Tests whether an undirected graph is trianglefree (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 anIllegalArgumentException
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 customizedIllegalArgumentException
if it is not.static <V,
E> Graph<V, E> requireDirectedOrUndirected
(Graph<V, E> graph) Checks that the specified graph is directed and throws anIllegalArgumentException
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 customizedIllegalArgumentException
if it is not.static <V,
E> Graph<V, E> requireUndirected
(Graph<V, E> graph) Checks that the specified graph is undirected and throws anIllegalArgumentException
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 customizedIllegalArgumentException
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 customizedIllegalArgumentException
if it is not.

Constructor Details

GraphTests
public GraphTests()


Method Details

isEmpty
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 typeE
 the graph edge type Parameters:
graph
 the input graph Returns:
 true if the graph is empty, false otherwise

isSimple
Check if a graph is simple. A graph is simple if it has no selfloops and multiple (parallel) edges. Type Parameters:
V
 the graph vertex typeE
 the graph edge type Parameters:
graph
 a graph Returns:
 true if a graph is simple, false otherwise

hasSelfLoops
Check if a graph has selfloops. A selfloop is an edge with the same source and target vertices. Type Parameters:
V
 the graph vertex typeE
 the graph edge type Parameters:
graph
 a graph Returns:
 true if a graph has selfloops, false otherwise

hasMultipleEdges
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 typeE
 the graph edge type Parameters:
graph
 a graph Returns:
 true if a graph has multiple edges, false otherwise

isComplete
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 typeE
 the graph edge type Parameters:
graph
 the input graph Returns:
 true if the graph is complete, false otherwise

isConnected
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 typeE
 the graph edge type Parameters:
graph
 the input graph Returns:
 true if the graph is connected, false otherwise
 See Also:

isBiconnected
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 typeE
 the graph edge type Parameters:
graph
 the input graph Returns:
 true if the graph is biconnected, false otherwise
 See Also:

isWeaklyConnected
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 typeE
 the graph edge type Parameters:
graph
 the input graph Returns:
 true if the graph is weakly connected, false otherwise
 See Also:

isStronglyConnected
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 typeE
 the graph edge type Parameters:
graph
 the input graph Returns:
 true if the graph is strongly connected, false otherwise
 See Also:

isTree
Test whether an undirected graph is a tree. Type Parameters:
V
 the graph vertex typeE
 the graph edge type Parameters:
graph
 the input graph Returns:
 true if the graph is tree, false otherwise

isForest
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 typeE
 the graph edge type Parameters:
graph
 the input graph Returns:
 true if the graph is forest, false otherwise

isOverfull
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 typeE
 the graph edge type Parameters:
graph
 the input graph Returns:
 true if the graph is overfull, false otherwise

isSplit
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 i1\}$. 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 typeE
 the graph edge type Parameters:
graph
 the input graph Returns:
 true if the graph is a split graph, false otherwise

isBipartite
Test whether a graph is bipartite. Type Parameters:
V
 the graph vertex typeE
 the graph edge type Parameters:
graph
 the input graph Returns:
 true if the graph is bipartite, false otherwise
 See Also:

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 typeE
 the graph edge type Parameters:
graph
 the input graphfirstPartition
 the first vertices partitionsecondPartition
 the second vertices partition Returns:
 true if the partition is a bipartite partition, false otherwise
 See Also:

isCubic
Tests whether a graph is cubic. A graph is cubic if all vertices have degree 3. Type Parameters:
V
 the graph vertex typeE
 the graph edge type Parameters:
graph
 the input graph Returns:
 true if the graph is cubic, false otherwise

isEulerian
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 typeE
 the graph edge type Parameters:
graph
 the input graph Returns:
 true if the graph is Eulerian, false otherwise
 See Also:

isChordal
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 typeE
 the graph edge type Parameters:
graph
 the input graph Returns:
 true if the graph is chordal, false otherwise
 See Also:

isWeaklyChordal
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 2pair in a graph is a pair of nonadjacent 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 2pair.
 Type Parameters:
V
 the graph vertex typeE
 the graph edge type Parameters:
graph
 the input graph Returns:
 true if the graph is weakly chordal, false otherwise
 See Also:

hasOreProperty
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 nonadjacent vertices $v$ and $w$ of $G$, then $G$ is Hamiltonian. Type Parameters:
V
 the graph vertex typeE
 the graph edge type Parameters:
graph
 the input graph Returns:
 true if the graph meets Ore's condition, false otherwise
 See Also:

isTriangleFree
Tests whether an undirected graph is trianglefree (i.e. no three distinct vertices form a triangle of edges). The implementation of this method usesGraphMetrics.getNumberOfTriangles(Graph)
. Type Parameters:
V
 the graph vertex typeE
 the graph edge type Parameters:
graph
 the input graph Returns:
 true if the graph is trianglefree, false otherwise

isPerfect
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 toBergeGraphInspector
 Type Parameters:
V
 the graph vertex typeE
 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
Checks that the specified graph is planar. A graph is planar if it can be drawn on a twodimensional plane without any of its edges crossing. The implementation of the method is delegated to theBoyerMyrvoldPlanarityInspector
. 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 typeE
 the graph edge type Parameters:
graph
 the graph to test planarity of Returns:
 true if the graph is planar, false otherwise
 See Also:

isKuratowskiSubdivision
Checks whether thegraph
is a Kuratowski subdivision. Effectively checks whether thegraph
is a $K_{3,3}$ subdivision or $K_{5}$ subdivision Type Parameters:
V
 the graph vertex typeE
 the graph edge type Parameters:
graph
 the graph to test Returns:
 true if the
graph
is a Kuratowski subdivision, false otherwise

isK33Subdivision
Checks whether thegraph
is a $K_{3,3}$ subdivision. Type Parameters:
V
 the graph vertex typeE
 the graph edge type Parameters:
graph
 the graph to test Returns:
 true if the
graph
is a $K_{3,3}$ subdivision, false otherwise

isK5Subdivision
Checks whether thegraph
is a $K_5$ subdivision. Type Parameters:
V
 the graph vertex typeE
 the graph edge type Parameters:
graph
 the graph to test Returns:
 true if the
graph
is a $K_5$ subdivision, false otherwise

requireDirected
Checks that the specified graph is directed and throws a customizedIllegalArgumentException
if it is not. Also checks that the graph reference is notnull
and throws aNullPointerException
if it is. Type Parameters:
V
 the graph vertex typeE
 the graph edge type Parameters:
graph
 the graph reference to check for beeing directed and not nullmessage
 detail message to be used in the event that an exception is thrown Returns:
graph
if directed and notnull
 Throws:
NullPointerException
 ifgraph
isnull
IllegalArgumentException
 ifgraph
is not directed

requireDirected
Checks that the specified graph is directed and throws anIllegalArgumentException
if it is not. Also checks that the graph reference is notnull
and throws aNullPointerException
if it is. Type Parameters:
V
 the graph vertex typeE
 the graph edge type Parameters:
graph
 the graph reference to check for beeing directed and not null Returns:
graph
if directed and notnull
 Throws:
NullPointerException
 ifgraph
isnull
IllegalArgumentException
 ifgraph
is not directed

requireUndirected
Checks that the specified graph is undirected and throws a customizedIllegalArgumentException
if it is not. Also checks that the graph reference is notnull
and throws aNullPointerException
if it is. Type Parameters:
V
 the graph vertex typeE
 the graph edge type Parameters:
graph
 the graph reference to check for being undirected and not nullmessage
 detail message to be used in the event that an exception is thrown Returns:
graph
if undirected and notnull
 Throws:
NullPointerException
 ifgraph
isnull
IllegalArgumentException
 ifgraph
is not undirected

requireUndirected
Checks that the specified graph is undirected and throws anIllegalArgumentException
if it is not. Also checks that the graph reference is notnull
and throws aNullPointerException
if it is. Type Parameters:
V
 the graph vertex typeE
 the graph edge type Parameters:
graph
 the graph reference to check for being undirected and not null Returns:
graph
if undirected and notnull
 Throws:
NullPointerException
 ifgraph
isnull
IllegalArgumentException
 ifgraph
is not undirected

requireDirectedOrUndirected
Checks that the specified graph is directed or undirected and throws a customizedIllegalArgumentException
if it is not. Also checks that the graph reference is notnull
and throws aNullPointerException
if it is. Type Parameters:
V
 the graph vertex typeE
 the graph edge type Parameters:
graph
 the graph reference to check for beeing directed or undirected and not nullmessage
 detail message to be used in the event that an exception is thrown Returns:
graph
if directed and notnull
 Throws:
NullPointerException
 ifgraph
isnull
IllegalArgumentException
 ifgraph
is mixed

requireDirectedOrUndirected
Checks that the specified graph is directed and throws anIllegalArgumentException
if it is not. Also checks that the graph reference is notnull
and throws aNullPointerException
if it is. Type Parameters:
V
 the graph vertex typeE
 the graph edge type Parameters:
graph
 the graph reference to check for beeing directed and not null Returns:
graph
if directed and notnull
 Throws:
NullPointerException
 ifgraph
isnull
IllegalArgumentException
 ifgraph
is mixed

requireWeighted
Checks that the specified graph is weighted and throws a customizedIllegalArgumentException
if it is not. Also checks that the graph reference is notnull
and throws aNullPointerException
if it is. Type Parameters:
V
 the graph vertex typeE
 the graph edge type Parameters:
graph
 the graph reference to check for being weighted and not null Returns:
graph
if directed and notnull
 Throws:
NullPointerException
 ifgraph
isnull
IllegalArgumentException
 ifgraph
is not weighted
