Package org.jgrapht
Class GraphTests
- java.lang.Object
-
- org.jgrapht.GraphTests
-
public abstract class GraphTests extends java.lang.Object
A collection of utilities to test for various graph properties.
-
-
Constructor Summary
Constructors Constructor Description GraphTests()
-
Method Summary
All Methods Static Methods Concrete Methods Modifier and Type Method Description static <V,E>
booleanisBipartite(Graph<V,E> graph)
Test whether a graph is bipartite.static <V,E>
booleanisBipartitePartition(Graph<V,E> graph, java.util.Set<? extends V> firstPartition, java.util.Set<? extends V> secondPartition)
Test whether a partition of the vertices into two sets is a bipartite partition.static <V,E>
booleanisComplete(Graph<V,E> graph)
Test whether a graph is complete.static <V,E>
booleanisConnected(UndirectedGraph<V,E> graph)
Test whether an undirected graph is connected.static <V,E>
booleanisEmpty(Graph<V,E> graph)
Test whether a graph is empty.static <V,E>
booleanisEulerian(Graph<V,E> graph)
Test whether a graph is Eulerian.static <V,E>
booleanisSimple(Graph<V,E> graph)
Check if a graph is simple.static <V,E>
booleanisStronglyConnected(DirectedGraph<V,E> graph)
Test whether a directed graph is strongly connected.static <V,E>
booleanisTree(UndirectedGraph<V,E> graph)
Test whether an undirected graph is a tree.static <V,E>
booleanisWeaklyConnected(DirectedGraph<V,E> graph)
Test whether a directed graph is weakly connected.
-
-
-
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 typeE
- 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 typeE
- 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 typeE
- 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(UndirectedGraph<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 typeE
- 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(DirectedGraph<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 typeE
- 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(DirectedGraph<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 typeE
- 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(UndirectedGraph<V,E> graph)
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
-
isBipartite
public static <V,E> boolean isBipartite(Graph<V,E> graph)
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
-
isBipartitePartition
public static <V,E> boolean isBipartitePartition(Graph<V,E> graph, java.util.Set<? extends V> firstPartition, java.util.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
-
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 typeE
- the graph edge type- Parameters:
graph
- the input graph- Returns:
- true if the graph is Eulerian, false otherwise
- See Also:
HierholzerEulerianCycle.isEulerian(Graph)
-
-