Package org.jgrapht

Class 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>
      boolean
      isBipartite​(Graph<V,​E> graph)
      Test whether a graph is bipartite.
      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.
      static <V,​E>
      boolean
      isComplete​(Graph<V,​E> graph)
      Test whether a graph is complete.
      static <V,​E>
      boolean
      isConnected​(UndirectedGraph<V,​E> graph)
      Test whether an undirected graph is connected.
      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
      isSimple​(Graph<V,​E> graph)
      Check if a graph is simple.
      static <V,​E>
      boolean
      isStronglyConnected​(DirectedGraph<V,​E> graph)
      Test whether a directed graph is strongly connected.
      static <V,​E>
      boolean
      isTree​(UndirectedGraph<V,​E> graph)
      Test whether an undirected graph is a tree.
      static <V,​E>
      boolean
      isWeaklyConnected​(DirectedGraph<V,​E> graph)
      Test whether a directed graph is weakly connected.
      • 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​(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 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​(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 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​(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 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​(UndirectedGraph<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
      • 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,
                                                               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 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
      • 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)