Package org.graph4j

Class GraphTests

java.lang.Object
org.graph4j.GraphTests
public class GraphTests extends Object
Author:
Cristian Frăsinaru

  • Constructor Summary

    Constructors
    Constructor
    Description
    GraphTests()
     

  • Method Summary

    Modifier and Type
    Method
    Description
    static boolean
    hasOreProperty(Graph graph)
    Checks if an undirected graph has Ore's property: deg(v) + deg(u) >= |V|, for every pair of distinct non-adjacent vertices v and u.
    static boolean
    isAcyclic(Graph graph)
    Determines if the graph is acyclic, meaning it does not contain any cycle.
    static boolean
    isArborescence(Digraph digraph)
    Determines if a directed graph is an arborescence (also called poly-tree), that is a directed rooted tree in which all edges point away from the root.
    static boolean
    isBiconnected(Graph graph)
    Determines if the graph is biconnected (2-connected). that is it does not contain a cut-vertex.
    static boolean
    isBipartite(Graph graph)
    Determines if a graph is bipartite, meaning that its vertices can be partitioned in two disjoint stable sets.
    static boolean
    isBranching(Digraph digraph)
    Determines if a directed graph is a branching (also called poly-forest), that is a collection of disjoint arborescences.
    static boolean
    isBridgeless(Graph graph)
    Determines if the graph is bridgeless, that is it does not contain any bridge.
    static boolean
    isChordal(Graph graph)
    Determines if a graph is chordal, meaning it does not contain an induced cycle of four or more vertices.
    static boolean
    isClique(Graph graph, int[] vertices)
    Checks if the specified vertices represent a clique, meaning that the subgraph induced by them is complete.
    static boolean
    isConnected(Graph graph)
    Determines if a graph is connected, meaning that there exists a path between every pair of vertices.
    static boolean
    isCubic(Graph graph)
    Determines if a graph is cubic, meaning that all of its vertices have degree 3.
    static boolean
    isEulerian(Graph graph)
    Determines if a graph is Eulerian, that is it contains a circuit passing through all of its edges.
    static boolean
    isForest(Graph graph)
    Determines if a graph is a forest, an undirected and acyclic graph.
    static boolean
    isOverfull(Graph graph)
    Checks if a graph is overfull, meaning its size is greater than the product of its maximum degree and half of its order floored: |E| > Δ(G) |V|/2, where Δ(G) is the maximum degree of the graph.
    static boolean
    isRegular(Graph graph)
    Determines if the graph is regular, that is a graph where each vertex has the same number of neighbors (degree).
    static boolean
    isRegular(Graph graph, int k)
    Determines if the graph is k-regular, that is a graph where each vertex has exactly k neighbors.
    static boolean
    isStableSet(Graph graph, int[] vertices)
    Checks if the specified vertices represent a stable set, meaning that the subgraph induced by them is edgeless.
    static boolean
    isStronglyConnected(Digraph digraph)
    Determines if a directed graph is strongly connected, that is for every pair of vertices u and v, there exists both directed paths from u to v and from v to u.
    static boolean
    isTree(Graph graph)
    Determines if a graph is a tree, that is an undirected, connected and acyclic graph.
    static boolean
    isTriangleFree(Graph graph)
    Determines if a graph is triangle-free, that is no three distinct vertices form a triangle.
    static boolean
    isUnilateralConnected(Digraph digraph)
    Determines if a directed graph is unilateral connected, that is for every pair of vertices u and v, there exists either a directed path from u to v or one from v to u.
    static boolean
    isWeaklyConnected(Digraph digraph)
    Determines if a directed graph is weakly connected, that is its support graph is connected.

    Methods inherited from class java.lang.Object

    clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

  • Constructor Details

    • GraphTests

      public GraphTests()

  • Method Details

    • isBipartite

      public static boolean isBipartite(Graph graph)
      Determines if a graph is bipartite, meaning that its vertices can be partitioned in two disjoint stable sets.
      Parameters:
      graph - the input graph.
      Returns:
      true if the graph is bipartite, false otherwise.
      See Also:

    • isConnected

      public static boolean isConnected(Graph graph)
      Determines if a graph is connected, meaning that there exists a path between every pair of vertices. If the input graph is directed, the algorithm is performed on its support graph (it tests weak connectivity).
      Parameters:
      graph - the input graph.
      Returns:
      true if the graph is connected, false otherwise.
      See Also:

    • isTree

      public static boolean isTree(Graph graph)
      Determines if a graph is a tree, that is an undirected, connected and acyclic graph. It uses the property that a tree has n - 1 edges, where n is the number of vertices in the graph.
      Parameters:
      graph - the input graph.
      Returns:
      true if the graph is a tree, false otherwise.
      Throws:
      IllegalArgumentException - if the graph is directed.

    • isForest

      public static boolean isForest(Graph graph)
      Determines if a graph is a forest, an undirected and acyclic graph. A forest can also be defined as a disjoint reunion of trees.
      Parameters:
      graph - the input graph.
      Returns:
      true if the graph is a forest, false otherwise.
      Throws:
      IllegalArgumentException - if the graph is directed.

    • isArborescence

      public static boolean isArborescence(Digraph digraph)
      Determines if a directed graph is an arborescence (also called poly-tree), that is a directed rooted tree in which all edges point away from the root. Technically, an arborescence is a directed tree with maximum indegree equal to 1.
      Parameters:
      digraph - the input directed graph.
      Returns:
      true if the digraph is an arborescence, false otherwise.

    • isBranching

      public static boolean isBranching(Digraph digraph)
      Determines if a directed graph is a branching (also called poly-forest), that is a collection of disjoint arborescences. Technically, a branching is a directed forest with maximum indegree equal to 1.
      Parameters:
      digraph - the input directed graph.
      Returns:
      true if the digraph is a branching, false otherwise.

    • isBiconnected

      public static boolean isBiconnected(Graph graph)
      Determines if the graph is biconnected (2-connected). that is it does not contain a cut-vertex.
      Parameters:
      graph - the input graph
      Returns:
      true if the graph is biconnected (2-connected), false otherwise.
      See Also:

    • isStronglyConnected

      public static boolean isStronglyConnected(Digraph digraph)
      Determines if a directed graph is strongly connected, that is for every pair of vertices u and v, there exists both directed paths from u to v and from v to u.
      Parameters:
      digraph - the input directed graph.
      Returns:
      true if the digraph is strongly connected, false otherwise.
      See Also:

    • isUnilateralConnected

      public static boolean isUnilateralConnected(Digraph digraph)
      Determines if a directed graph is unilateral connected, that is for every pair of vertices u and v, there exists either a directed path from u to v or one from v to u.
      Parameters:
      digraph - the input directed graph.
      Returns:
      true if the digraph is unilateral connected, false otherwise.
      See Also:

    • isWeaklyConnected

      public static boolean isWeaklyConnected(Digraph digraph)
      Determines if a directed graph is weakly connected, that is its support graph is connected.
      Parameters:
      digraph - the input directed graph.
      Returns:
      true if the digraph is weakly connected, false otherwise.
      See Also:

    • isBridgeless

      public static boolean isBridgeless(Graph graph)
      Determines if the graph is bridgeless, that is it does not contain any bridge.
      Parameters:
      graph - the input graph
      Returns:
      true if the graph does not contain any bridge.
      See Also:

    • isAcyclic

      public static boolean isAcyclic(Graph graph)
      Determines if the graph is acyclic, meaning it does not contain any cycle.
      Parameters:
      graph - the input graph.
      Returns:
      true if the graph is acyclic, false otherwise.
      See Also:

    • isRegular

      public static boolean isRegular(Graph graph)
      Determines if the graph is regular, that is a graph where each vertex has the same number of neighbors (degree). For a regular directed graph, the indegree and outdegree of each vertex must also be equal.
      Parameters:
      graph - an input graph.
      Returns:
      true if all vertices have the same degree, false otherwise.

    • isRegular

      public static boolean isRegular(Graph graph, int k)
      Determines if the graph is k-regular, that is a graph where each vertex has exactly k neighbors. For a k-regular directed graph, the indegree and outdegree of each vertex must both be equal to k.
      Parameters:
      graph - the input graph.
      k - a degree.
      Returns:
      true if the graph is k-regular.

    • isCubic

      public static boolean isCubic(Graph graph)
      Determines if a graph is cubic, meaning that all of its vertices have degree 3. In case of directed graphs, the indegree and outdegree of each vertex must both be equal to 3.
      Parameters:
      graph - the input graph.
      Returns:
      true if the graph is cubic, false otherwise.
      See Also:

    • isEulerian

      public static boolean isEulerian(Graph graph)
      Determines if a graph is Eulerian, that is it contains a circuit passing through all of its edges.
      Parameters:
      graph - the input graph.
      Returns:
      true if the graph is Eulerian.
      See Also:

    • isTriangleFree

      public static boolean isTriangleFree(Graph graph)
      Determines if a graph is triangle-free, that is no three distinct vertices form a triangle.
      Parameters:
      graph - the input graph.
      Returns:
      true if the graph is triangle-free.
      See Also:

    • isChordal

      public static boolean isChordal(Graph graph)
      Determines if a graph is chordal, meaning it does not contain an induced cycle of four or more vertices.
      Parameters:
      graph - the input graph.
      Returns:
      true if the graph is chordal, false otherwise.
      See Also:

    • hasOreProperty

      public static boolean hasOreProperty(Graph graph)
      Checks if an undirected graph has Ore's property: deg(v) + deg(u) >= |V|, for every pair of distinct non-adjacent vertices v and u. If a graph has Ore's property, then it is Hamiltonian.
      Parameters:
      graph - the input graph.
      Returns:
      true if the graph has Ore's property, false otherwise.
      Throws:
      IllegalArgumentException - if the graph is directed.
      See Also:

    • isClique

      public static boolean isClique(Graph graph, int[] vertices)
      Checks if the specified vertices represent a clique, meaning that the subgraph induced by them is complete.
      Parameters:
      graph - the input graph.
      vertices - an array of vertices.
      Returns:
      true if the vertices form a clique, false otherwise.
      Throws:
      IllegalArgumentException - if the graph is directed.
      InvalidVertexException - if any of the vertices is not in the graph.

    • isStableSet

      public static boolean isStableSet(Graph graph, int[] vertices)
      Checks if the specified vertices represent a stable set, meaning that the subgraph induced by them is edgeless.
      Parameters:
      graph - the input graph.
      vertices - an array of vertices.
      Returns:
      true if the vertices form a stable set, false otherwise.
      Throws:
      IllegalArgumentException - if the graph is directed.
      InvalidVertexException - if any of the vertices is not in the graph.

    • isOverfull

      public static boolean isOverfull(Graph graph)
      Checks if a graph is overfull, meaning its size is greater than the product of its maximum degree and half of its order floored: |E| > Δ(G) |V|/2, where Δ(G) is the maximum degree of the graph. Overfull property play a role in results concerning edge coloring.
      Parameters:
      graph - the input graph.
      Returns:
      true if the graph is overfull, false otherwise.