Package com.jgalgo.alg.tree

Class Trees

java.lang.Object
com.jgalgo.alg.tree.Trees
public class Trees extends Object
Static methods class for tree graphs.
Author:
Barak Ugav

  • Method Details

    • isTree

      public static <V, E> boolean isTree(Graph<V,E> g)
      Check if an undirected graph is a tree.

      An undirected graph is a tree if its connected and contains no cycle, therefore \(n-1\) edges.

      This method runs in linear time.

      Type Parameters:
      V - the vertices type
      E - the edges type
      Parameters:
      g - a graph
      Returns:
      true if the graph is a tree, else false
      Throws:
      IllegalArgumentException - if g is a directed graph

    • isTree

      public static <V, E> boolean isTree(Graph<V,E> g, V root)
      Check if a graph is a tree rooted as some vertex.

      For undirected graphs, a graph which is a tree rooted at some vertex can be rooted at any other vertex and will always be a tree. For directed graphs however this is not true. A directed graph might be a tree rooted at some vertex, but will no be connected if we root it at another vertex.

      This method runs in linear time.

      Type Parameters:
      V - the vertices type
      E - the edges type
      Parameters:
      g - a graph
      root - a root vertex
      Returns:
      true if the graph is a tree rooted at root, else false.

    • isForest

      public static <V, E> boolean isForest(Graph<V,E> g)
      Check if a graph is a forest.

      A forest is a graph which can be divided into trees, which is equivalent to saying a graph with no cycles.

      This method runs in linear time.

      Type Parameters:
      V - the vertices type
      E - the edges type
      Parameters:
      g - a graph
      Returns:
      true if the graph is a forest, else false