Package com.jgalgo

Class Trees

java.lang.Object

com.jgalgo.Trees

public class Trees
extends Object

Static methods class for tree graphs.

Author:

Barak Ugav

Method Summary

Modifier and Type	Method	Description
static boolean	isForest(Graph g)	Check if a graph is a forest.
static boolean	isTree(Graph g)	Check if an undirected graph is a tree.
static boolean	isTree(Graph g, int root)	Check if a graph is a tree rooted as some vertex.

Methods inherited from class java.lang.Object

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

Method Detail

isTree

public static boolean isTree(Graph 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.

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 boolean isTree(Graph g,
                             int 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.

Parameters:

g - a graph

root - a root vertex

Returns:

true if the graph is a tree rooted at root, else false.

isForest

public static boolean isForest(Graph 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.

Parameters:

g - a graph

Returns:

true if the graph is a forest, else false