/**
 * A {@link MapIteratorCache} that adds additional caching. In addition to the caching provided by
 * {@link MapIteratorCache}, this structure caches values for the two most recently retrieved keys.
 *
 * @author James Sexton
 */
@ElementTypesAreNonnullByDefault
final class MapRetrievalCache<K, V> extends MapIteratorCache<K, V> {
  // See the note about volatile in the superclass.

import java.util.Set;
import javax.annotation.CheckForNull;

/**
 * An interface for representing and manipulating an origin node's adjacent nodes and incident edges
 * in a {@link Network}.
 *
 * @author James Sexton
 * @param <N> Node parameter type
 * @param <E> Edge parameter type
 */
@ElementTypesAreNonnullByDefault
interface NetworkConnections<N, E> {

  Set<N> adjacentNodes();

  Set<N> predecessors();

import java.util.LinkedHashMap;
import java.util.Map;
import java.util.Set;
import javax.annotation.CheckForNull;

/**
 * An implementation of {@link GraphConnections} for undirected graphs.
 *
 * @author James Sexton
 * @param <N> Node parameter type
 * @param <V> Value parameter type
 */
@ElementTypesAreNonnullByDefault
final class UndirectedGraphConnections<N, V> implements GraphConnections<N, V> {

 *         .putEdgeValue("San Jose", "San Jose", 0.0)
 *         .putEdgeValue("San Francisco", "San Jose", 48.4)
 *         .build();
 * }</pre>
 *
 * @author James Sexton
 * @author Joshua O'Madadhain
 * @param <N> The most general node type this builder will support. This is normally {@code Object}
 *     unless it is constrained by using a method like {@link #nodeOrder}, or the builder is

 * {@link EndpointPair} of an undirected edge is an unordered pair of nodes ({@link #nodeU()} and
 * {@link #nodeV()}).
 *
 * <p>The edge is a self-loop if, and only if, the two endpoints are equal.
 *
 * @author James Sexton
 * @since 20.0
 */
@Beta
@Immutable(containerOf = {"N"})
@ElementTypesAreNonnullByDefault
public abstract class EndpointPair<N> implements Iterable<N> {
  private final N nodeU;
  private final N nodeV;

 * this class rather than implement {@link ValueGraph} directly.
 *
 * <p>The methods implemented in this class should not be overridden unless the subclass admits a
 * more efficient implementation.
 *
 * @author James Sexton
 * @param <N> Node parameter type
 * @param <V> Value parameter type
 * @since 20.0
 */
@Beta
@ElementTypesAreNonnullByDefault
public abstract class AbstractValueGraph<N, V> extends AbstractBaseGraph<N>

/**
 * A subinterface of {@link Network} which adds mutation methods. When mutation is not required,
 * users should prefer the {@link Network} interface.
 *
 * @author James Sexton
 * @author Joshua O'Madadhain
 * @param <N> Node parameter type
 * @param <E> Edge parameter type
 * @since 20.0
 */
@Beta
@ElementTypesAreNonnullByDefault

 * changes to the graph (if the graph is mutable) but may not be modified by the user.
 *
 * <p>The time complexity of all collection-returning accessors is O(1), since views are returned.
 *
 * @author James Sexton
 * @author Joshua O'Madadhain
 * @author Omar Darwish
 * @param <N> Node parameter type
 * @param <V> Value parameter type
 */
@ElementTypesAreNonnullByDefault

import java.util.Collections;
import java.util.Map;
import java.util.Set;
import javax.annotation.CheckForNull;

/**
 * A base implementation of {@link NetworkConnections} for directed networks.
 *
 * @author James Sexton
 * @param <N> Node parameter type
 * @param <E> Edge parameter type
 */
@ElementTypesAreNonnullByDefault
abstract class AbstractDirectedNetworkConnections<N, E> implements NetworkConnections<N, E> {

 * map is immutable).
 *
 * <p>This class is tailored toward use cases in common.graph. It is *NOT* a general purpose map.
 *
 * @author James Sexton
 */
@ElementTypesAreNonnullByDefault
class MapIteratorCache<K, V> {
  private final Map<K, V> backingMap;

  /*
   * Per JDK: "the behavior of a map entry is undefined if the backing map has been modified after