How to Create and Traverse Graphs Using Guava's Graph Library

Use GraphBuilder to construct MutableGraph or ImmutableGraph instances, then apply Traverser.forGraph() or Traverser.forTree() to perform BFS or DFS traversals over your data structures.

The Google Guava library provides a lightweight, type-safe graph API in the com.google.common.graph package that enables you to model directed and undirected graphs without external dependencies. This API supports both mutable and immutable graph implementations, offering fluent builders for construction and specialized traversers for efficient path exploration. Whether you are modeling social networks, dependency trees, or state machines, Guava's graph utilities provide the necessary tools to create and traverse complex relationships in Java.

Understanding Guava's Graph API Architecture

Guava's graph implementation separates graph construction from traversal through distinct interfaces and builders. The architecture centers on immutable views for read operations and specialized builders for type-safe construction.

GraphBuilder for Graph Construction

The GraphBuilder class, located in guava/src/com/google/common/graph/GraphBuilder.java, provides a fluent API for configuring graph properties before instantiation. You initiate construction by selecting directionality—GraphBuilder.directed() or GraphBuilder.undirected()—then chain configuration methods such as allowsSelfLoops(true), nodeOrder(ElementOrder.insertion()), or expectedNodeCount(int) to optimize internal data structures.

MutableGraph vs ImmutableGraph

Guava distinguishes between modifiable and unmodifiable graph instances through two core interfaces:

• MutableGraph (guava/src/com/google/common/graph/MutableGraph.java): Extends the base Graph interface with mutating operations including addNode(N node) and putEdge(N nodeU, N nodeV). Use this when your graph structure changes at runtime.
• ImmutableGraph (guava/src/com/google/common/graph/ImmutableGraph.java): An unmodifiable snapshot created via GraphBuilder.immutable() followed by build(). Once constructed, attempts to modify the graph throw UnsupportedOperationException.

The Graph Interface

The base Graph interface (guava/src/com/google/common/graph/Graph.java) exposes read-only views through methods like nodes(), edges(), adjacentNodes(node), predecessors(node), and successors(node). All returned collections are live, unmodifiable views backed by the underlying graph structure, ensuring consistency while preventing external modification.

Creating Graphs with GraphBuilder

To create a graph in Guava, instantiate the appropriate builder type, configure optional constraints, and populate the structure with nodes and edges.

Building a Mutable Undirected Graph

For graphs requiring runtime modifications, use GraphBuilder with build() to obtain a MutableGraph instance:

import com.google.common.graph.*;

public class MutableGraphExample {
  public static void main(String[] args) {
    // Configure an undirected graph that allows self-loops
    MutableGraph<String> graph = GraphBuilder.undirected()
        .allowsSelfLoops(true)
        .nodeOrder(ElementOrder.insertion())
        .expectedNodeCount(10)
        .build();

    // Populate the graph
    graph.putEdge("bread", "bread");          // self-loop
    graph.putEdge("bread", "chocolate");
    graph.putEdge("chocolate", "peanut butter");
    graph.putEdge("peanut butter", "jelly");

    // Query the graph structure
    System.out.println("Nodes: " + graph.nodes());
    System.out.println("Successors of 'bread': " + graph.successors("bread"));
  }
}

Building an Immutable Directed Graph

For static graph structures, use the immutable builder pattern to create a thread-safe, memory-efficient snapshot:

import com.google.common.graph.*;

public class ImmutableGraphExample {
  public static void main(String[] args) {
    // Start with a directed immutable builder
    ImmutableGraph.Builder<String> builder = GraphBuilder.<String>directed()
        .allowsSelfLoops(false)
        .immutable();

    // Add edges (returns builder for chaining)
    builder.putEdge("a", "b")
           .putEdge("a", "c")
           .putEdge("b", "d")
           .putEdge("c", "d")
           .putEdge("d", "e");

    // Build the immutable graph
    ImmutableGraph<String> dag = builder.build();

    // Access read-only views
    System.out.println("Predecessors of 'd': " + dag.predecessors("d"));
  }
}

Traversing Graphs with Traverser

The Traverser class (guava/src/com/google/common/graph/Traverser.java) provides generic graph traversal algorithms without requiring manual stack or queue management. You obtain a Traverser instance through static factory methods that accept a successor function.

BFS and DFS Traversal Methods

Traverser exposes three primary traversal orders, each returning an Iterable that lazily evaluates nodes as you iterate:

• breadthFirst(startNode): Explores nodes in breadth-first search (BFS) order, visiting all neighbors at the present depth before moving deeper.
• depthFirstPreOrder(startNode): Performs depth-first search (DFS), yielding nodes immediately upon first encounter.
• depthFirstPostOrder(startNode): Performs DFS but yields nodes only after visiting all descendants, useful for dependency resolution.

General Graphs vs Tree Structures

Guava provides two factory methods depending on your graph's structural guarantees:

• Traverser.forGraph(successorsFunction): Use for general graphs where cycles may exist. The traverser tracks visited nodes to ensure each reachable node is visited at most once, preventing infinite loops in cyclic structures.
• Traverser.forTree(successorsFunction): Use for tree or forest structures (DAGs where each node has exactly one path from the root). This implementation assumes no cycles and visits each node exactly once, offering slightly better performance by eliminating visited-set overhead.

Both traversal methods run in O(n) time and O(n) space, where n is the number of reachable nodes, using the node's equals() and hashCode() methods for identity checks.

Traversal Code Examples

The following example demonstrates BFS and DFS traversals on a general undirected graph:

import com.google.common.graph.*;

public class GraphTraversalExample {
  public static void main(String[] args) {
    MutableGraph<String> graph = GraphBuilder.undirected()
        .allowsSelfLoops(true)
        .build();

    graph.putEdge("bread", "bread");
    graph.putEdge("bread", "chocolate");
    graph.putEdge("chocolate", "peanut butter");
    graph.putEdge("peanut butter", "jelly");

    // Create traverser for general graphs (handles cycles)
    Traverser<String> traverser = Traverser.forGraph(graph::successors);

    System.out.println("BFS from 'bread':");
    for (String node : traverser.breadthFirst("bread")) {
      System.out.println(node);
    }

    System.out.println("\nDFS pre-order from 'bread':");
    for (String node : traverser.depthFirstPreOrder("bread")) {
      System.out.println(node);
    }
  }
}

For tree-like directed acyclic graphs (DAGs), use the tree-specific traverser:

import com.google.common.graph.*;

public class TreeTraversalExample {
  public static void main(String[] args) {
    ImmutableGraph<String> dag = GraphBuilder.<String>directed()
        .immutable()
        .putEdge("a", "b")
        .putEdge("a", "c")
        .putEdge("b", "d")
        .putEdge("c", "d")
        .putEdge("d", "e")
        .build();

    // Optimized for tree structures (no cycle checking overhead)
    Traverser<String> treeTraverser = Traverser.forTree(dag::successors);

    System.out.println("DFS post-order (tree) from 'a':");
    for (String node : treeTraverser.depthFirstPostOrder("a")) {
      System.out.println(node);
    }
  }
}

Working with Graph Utilities

The Graphs utility class (guava/src/com/google/common/graph/Graphs.java) provides static helper methods for common graph operations. Use Graphs.hasEdgeConnecting(graph, nodeU, nodeV) to check edge existence, Graphs.degree(graph, node) to calculate total degree, or Graphs.transitiveClosure(graph) to compute the transitive closure of a directed graph. These utilities operate on any Graph implementation, allowing you to analyze both mutable and immutable instances without manual iteration logic.

Summary

• Use GraphBuilder to configure directionality, self-loop policies, and node ordering before instantiating graphs.
• Choose MutableGraph for dynamic structures that change at runtime, or ImmutableGraph for static, thread-safe snapshots created through GraphBuilder.immutable().
• Access graph topology through the Graph interface methods nodes(), successors(), predecessors(), and adjacentNodes().
• Employ Traverser.forGraph() for cyclic graphs or Traverser.forTree() for DAGs to perform BFS, DFS pre-order, or DFS post-order traversals.
• Leverage the Graphs utility class for common operations like edge checking and transitive closure calculations.
• All traversal operations guarantee O(n) time complexity and visit each node at most once (for general graphs) or exactly once (for trees).

Frequently Asked Questions

What's the difference between MutableGraph and ImmutableGraph?

MutableGraph allows runtime modifications through methods like addNode() and putEdge(), while ImmutableGraph creates an unmodifiable snapshot via GraphBuilder.immutable().build(). Once built, immutable graphs throw UnsupportedOperationException on modification attempts, providing thread safety and memory efficiency for static graph structures.

How do I handle cycles when traversing a Guava graph?

Use Traverser.forGraph() instead of Traverser.forTree() when your graph may contain cycles. The forGraph() implementation maintains an internal set of visited nodes to ensure each node is processed at most once, preventing infinite loops during traversal. According to the source code in Traverser.java, this approach guarantees O(n) time complexity even with cyclic structures.

Can I use custom objects as nodes in Guava graphs?

Yes, Guava graphs accept any object type as nodes, provided they implement proper equals() and hashCode() contracts. The graph implementation uses these methods for identity checks during edge insertion and traversal. For best performance with large graphs, ensure your node objects are immutable and have efficient hash code implementations.

What performance characteristics does Guava's Traverser provide?

Both Traverser.forGraph() and Traverser.forTree() provide O(n) time and O(n) space complexity, where n represents the number of reachable nodes from the starting node. The traverser lazily evaluates nodes as you iterate the returned Iterable, minimizing memory overhead. Tree traversals offer slightly better constant factors since they skip the visited-set checks required for general graphs.

{
  "mcpServers": {
    "instagit": {
      "command": "npx",
      "args": ["-y", "instagit@latest"]
    }
  }
}