Graphs/Guava

Main article: Guava

Overview

Guava implements high performance data containers for Java. There are a number of things to be aware of when dealing with Guava Graphs. Most of these notes are taken from the Guava wiki on Github: https://github.com/google/guava/wiki/GraphsExplained#building-graph-instances

First, Guava Graphs should be thought of as extensions of the Java Collections types; they are not intended to scale to massive graphs, nor do they provide any specialized functionality (e.g., visualization). That is separate functionality to be implemented in separate libraries.

Next, there are two major classes of graphs in Guava: mutable and immutable.

There are three types of graphs available: Graph, ValueGraph, and Network. These are summarized as follows:

• Graph is your classic graph, it just deals with node-to-node relationships with "anonymous" edges defined only by endpoints.
• ValueGraph is a graph where edges store a value (the value does not need to be unique); the value associated with the edge is (maybe??) of arbitrary type. The edges are stored as a map from a pair of vertices to a value.
• Network is a type of graph that treats all edges as formal first-clsas types, just like nodes; this enables parallel edges with arbitrary objects.

Immutability

The Guava FAQ recommends enforcing that any objects stored in the nodes or edges of an immutable graph are themselves immutable - otherwise you have a nominally "immutable" graph but in reality the elements being wrapped by the graph can be modified at will. This is not a deeply immutable graph.

Building Graphs

Unfortunately, the first step in dealing with Guava Graphs is one of the most confusing: how the heck are you supposed to build a graph that's immutable?

Here's how you do it: you start by creating an empty graph that is MUTABLE, and add nodes and edges to the graph as you go. When you're finished modifying the mutable graph, you can then turn it into an immutable graph.

To build a graph, valuegraph, or network, start with the appropriate Builder class:

• GraphBuilder: http://google.github.io/guava/releases/snapshot/api/docs/com/google/common/graph/GraphBuilder.html
• ValueGraphBuilder: http://google.github.io/guava/releases/snapshot/api/docs/com/google/common/graph/ValueGraphBuilder.html
• NetworkBuilder: google.github.io/guava/releases/snapshot/api/docs/com/google/common/graph/NetworkBuilder.html

Now suppose we build a (mutable) Graph called (creatively enough) graph, and we wish to create an ImmutableGraph from that. To do so, we can use the static copyOf method:

ImmutableGraph<Integer> immutableGraph = ImmutableGraph.copyOf(graph);

Flags

See also:

• Template:DataStructuresFlag
• Template:AlgorithmsFlag