com.google.common.graph

Interface ValueGraph<N,V>

Type Parameters:

N - Node parameter type

V - Value parameter type

All Superinterfaces:

Graph<N>

All Known Subinterfaces:

MutableValueGraph<N,V>

All Known Implementing Classes:

AbstractValueGraph, ImmutableValueGraph

@Beta
public interface ValueGraph<N,V>
extends Graph<N>

An interface for graph data structures. A graph is composed of a set of nodes (sometimes called vertices) and a set of edges connecting pairs of nodes. Graphs are useful for modeling many kinds of relations. If the relation to be modeled is symmetric (such as "distance between cities"), that can be represented with an undirected graph, where an edge that connects node U to node V also connects node V to node U. If the relation to be modeled is asymmetric (such as "employees managed"), that can be represented with a directed graph, where edges are strictly one-way.

There are three main interfaces provided to represent graphs. In order of increasing complexity they are: Graph, ValueGraph, and Network. You should generally prefer the simplest interface that satisfies your use case.

To choose the right interface, answer these questions:

1. Do you have data (objects) that you wish to associate with edges?

   Yes: Go to question 2. No: Use Graph.

2. Are the objects you wish to associate with edges unique within the scope of a graph? That is, no two objects would be equal to each other. A common example where this would not be the case is with weighted graphs.

   Yes: Go to question 3. No: Use ValueGraph.

3. Do you need to be able to query the graph for an edge associated with a particular object? For example, do you need to query what nodes an edge associated with a particular object connects, or whether an edge associated with that object exists in the graph?

   Yes: Use Network. No: Go to question 4.

4. Do you need explicit support for parallel edges? For example, do you need to remove one edge connecting a pair of nodes while leaving other edges connecting those same nodes intact?

   Yes: Use Network. No: Use ValueGraph.

Although MutableValueGraph and MutableNetwork both require users to provide objects to associate with edges when adding them, the differentiating factor is that in ValueGraphs, these objects can be any arbitrary data. Like the values in a Map, they do not have to be unique, and can be mutated while in the graph. In a Network, these objects serve as keys into the data structure. Like the keys in a Map, they must be unique, and cannot be mutated in a way that affects their equals/hashcode or the data structure will become corrupted.

In all three interfaces, nodes have all the same requirements as keys in a Map.

The Graph interface does not support parallel Graph.edges(), and forbids implementations or extensions with parallel edges. It is possible to encode a notion of edge multiplicity into the values of a ValueGraph (e.g. with an integer or a list of values), but this will not be reflected in methods such as Graph.degree(Object). For that functionality, see Network.

All mutation methods live on the subinterface MutableValueGraph. If you do not need to mutate a graph (e.g. if you write a method than runs a read-only algorithm on the graph), you should prefer the non-mutating ValueGraph interface.

We provide an efficient implementation of this interface via ValueGraphBuilder. When using the implementation provided, all collection-returning methods provide live, unmodifiable views of the graph. In other words, you cannot add an element to the collection, but if an element is added to the ValueGraph that would affect the collection, the collection will be updated automatically. This also means that you cannot mutate a ValueGraph in a way that would affect a collection while iterating over that collection. For example, you cannot remove either foo or any successors of foo from the graph while iterating over successors(foo) (unless you first make a copy of the successors), just as you could not remove keys from a Map while iterating over its Map.keySet(). Behavior in such a case is undefined, and may result in ConcurrentModificationException.

Example of use:

 MutableValueGraph synonymGraph = ValueGraphBuilder.undirected().build();
 synonymGraph.putEdgeValue("large", "big", 0.9);
 synonymGraph.putEdgeValue("large", "huge", 0.9);
 synonymGraph.putEdgeValue("large", "grand", 0.6);
 synonymGraph.putEdgeValue("large", "cold", 0.0);
 synonymGraph.putEdgeValue("large", "small", -1.0);
 for (String word : synonymGraph.adjacentNodes("large")) {
   if (synonymGraph.edgeValue(word, "large") > 0.5) {
     System.out.println(word + " is a synonym for large");
   }
 }
 

Since:

20.0

Author:

James Sexton

Method Summary

Modifier and Type	Method and Description
V	edgeValue(Object nodeU, Object nodeV) If there is an edge connecting nodeU to nodeV, returns the non-null value associated with that edge.
V	edgeValueOrDefault(Object nodeU, Object nodeV, V defaultValue) If there is an edge connecting nodeU to nodeV, returns the non-null value associated with that edge; otherwise, returns defaultValue.
boolean	equals(Object object) For the default ValueGraph implementations, returns true iff this == object (reference equality).
int	hashCode() For the default ValueGraph implementations, returns System.identityHashCode(this).

Methods inherited from interface com.google.common.graph.Graph

adjacentNodes, allowsSelfLoops, degree, edges, inDegree, isDirected, nodeOrder, nodes, outDegree, predecessors, successors

Method Detail

edgeValue

V edgeValue(Object nodeU,
            Object nodeV)

If there is an edge connecting nodeU to nodeV, returns the non-null value associated with that edge.

In an undirected graph, this is equal to edgeValue(nodeV, nodeU).

Throws:

IllegalArgumentException - if there is no edge connecting nodeU to nodeV.

edgeValueOrDefault

V edgeValueOrDefault(Object nodeU,
                     Object nodeV,
                     @Nullable
                     V defaultValue)

If there is an edge connecting nodeU to nodeV, returns the non-null value associated with that edge; otherwise, returns defaultValue.

In an undirected graph, this is equal to edgeValueOrDefault(nodeV, nodeU, defaultValue).

equals

boolean equals(@Nullable
               Object object)

For the default ValueGraph implementations, returns true iff this == object (reference equality). External implementations are free to define this method as they see fit, as long as they satisfy the Object.equals(Object) contract.

To compare two ValueGraphs based on their contents rather than their references, see Graphs.equivalent(ValueGraph, ValueGraph).

Specified by:

equals in interface Graph<N>

Overrides:

equals in class Object

hashCode

int hashCode()

For the default ValueGraph implementations, returns System.identityHashCode(this). External implementations are free to define this method as they see fit, as long as they satisfy the Object.hashCode() contract.

Specified by:

hashCode in interface Graph<N>

Overrides:

hashCode in class Object