Guava Graph package: Method for testing if a undirected graph is a tree

Question

I want to write a function that tests if a undirected Graph is a tree.
So far, I'm using this:

Function<Graph<Integer>, Double> targetFunction = g -> {
    boolean isConnected = Graphs.reachableNodes(g, g.nodes().iterator().next()).equals(g.nodes());
    return isConnected && Graphs.hasCycle(g);
};

Is there already an implementation for this method in Guava (didn't find one) and if no, can this be improved?

Answer 1

Your implementation has two problems.

• g.nodes().iterator().next() returns the first node - n1 in the graph. Assume the graph is a tree, n1 might not be the root of the tree. So its reachable nodes is a subset of all nodes.
• hasCycle only detect back edges, but not forward edges or cross edges. Check the answer to find out the difference.

I cannot find a direct solution from guava graph api. It only provides basic support for graph data structure, bfs, and dfs.

This question, Determining whether or not a directed or undirected graph is a tree, shows how to implement what the algorithm you want.