Package com.jgalgo.alg

Class Trees

  • public class Trees
extends Object
    Static methods class for tree graphs.
    Author:
    Barak Ugav

    • Method Detail

      • 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