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.

Mutability and 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.

Immutable types can guarantee the following:

shallow immutability
deterministic iteration (consistent iteration order)
thread safety (safe to access graph concurrently from multiple threads)
integrity (it is not possible to subclass the Immutable types in a way that would violate these guarantees)

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);

Example

The Traveling Salesperson Problem repository on http://git.charlesreid1.com provides an example of how to construct a MutableNetwork, and then turn the MutableNetwork into an ImmutableNetwork.

The key line is here: https://git.charlesreid1.com/charlesreid1/hello-data-structures/src/master/java/guava/TSP.java#L101

The method that constructs the graph and returns an ImmutableNetwork object is reproduced below:

	/** This method actually constructs the graph. */
	public ImmutableNetwork<Node,Edge> buildGraph() {
		/** Make a NetworkBuilder object for an undirected network and call build().
         *
         * https://github.com/google/guava/wiki/GraphsExplained#building-graph-instances
		 */

		// MutableNetwork is an interface requiring a type for nodes and a type for edges
		MutableNetwork<Node,Edge> roads = NetworkBuilder.undirected().build();

		// Construct a dictionary of nodes (cities)
		String[] cities = {"A","B","C","D","E"};
		Map<String,Node> all_nodes = new TreeMap<String,Node>();
		for(int i = 0; i<cities.length; i++) {
			Node node = new Node(cities[i]);
			all_nodes.put(cities[i], node);

			// Add the nodes to the network
			roads.addNode(node);
		}
		
		// Construct Edges for roads,
		// and add them to a map
		String[] distances = {"A:B:24","A:C:5","A:D:20","A:E:18","B:C:10","B:D:20","C:D:4","C:E:28","D:E:3"};
		Map<String,Edge> all_edges = new TreeMap<String,Edge>();
		for(int j = 0; j<distances.length; j++) {
			// Parse out (city1):(city2):(distance)
			String[] splitresult = distances[j].split(":");
			String left = splitresult[0];
			String right = splitresult[1];
			String label = left + ":" + right;
			int value = Integer.parseInt(splitresult[2]);

			// Add edges to map
			Edge edge = new Edge(left, right, value);
			all_edges.put(label, edge);
			
			// Add edges to network
			roads.addEdge(all_nodes.get(edge.left), all_nodes.get(edge.right), edge);
		}
		
		// Freeze the network
		ImmutableNetwork<Node,Edge> frozen_roads = ImmutableNetwork.copyOf(roads);
		
		return frozen_roads;
	}

Useful Links

Traveling Salesperson Problem in Guava: https://git.charlesreid1.com/charlesreid1/hello-data-structures/src/master/java/guava/TSP.java

Graphs Explained: Google Guava Github Wiki: https://github.com/google/guava/wiki/GraphsExplained

Graphs Explained FAQ: Google Guava Github Wiki: https://github.com/google/guava/wiki/GraphsExplained#faq

Guava Javadocs:

Graphs/Guava

From charlesreid1

Contents

Overview

Mutability and Immutability

Building Graphs

Example

Useful Links

Flags