android/guava-tests/test/com/google/common/graph/AbstractGraphTest.java - platform/external/guava - Git at Google

 /*
  * Copyright (C) 2014 The Guava Authors
  *
  * Licensed under the Apache License, Version 2.0 (the "License");
  * you may not use this file except in compliance with the License.
  * You may obtain a copy of the License at
  *
  * http://www.apache.org/licenses/LICENSE-2.0
  *
  * Unless required by applicable law or agreed to in writing, software
  * distributed under the License is distributed on an "AS IS" BASIS,
  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  * See the License for the specific language governing permissions and
  * limitations under the License.
  */

 package com.google.common.graph;

 import static com.google.common.graph.TestUtil.ERROR_NODE_NOT_IN_GRAPH;
 import static com.google.common.graph.TestUtil.assertNodeNotInGraphErrorMessage;
 import static com.google.common.graph.TestUtil.assertStronglyEquivalent;
 import static com.google.common.graph.TestUtil.sanityCheckSet;
 import static com.google.common.truth.Truth.assertThat;
 import static org.junit.Assert.fail;

 import com.google.common.collect.ImmutableSet;
 import com.google.errorprone.annotations.CanIgnoreReturnValue;
 import java.util.HashSet;
 import java.util.Set;
 import org.junit.After;
 import org.junit.Before;
 import org.junit.Test;

 /**
  * Abstract base class for testing implementations of {@link Graph} interface. Graph instances
  * created for testing should have Integer node and String edge objects.
  *
  * <p>Test cases that should be handled similarly in any graph implementation are included in this
  * class. For example, testing that {@code nodes()} method returns the set of the nodes in the
  * graph. The following test cases are left for the subclasses to handle:
  *
  * <ul>
  *   <li>Test cases related to whether the graph is directed, undirected, mutable, or immutable.
  *   <li>Test cases related to the specific implementation of the {@link Graph} interface.
  * </ul>
  *
  * TODO(user): Make this class generic (using <N, E>) for all node and edge types.
  * TODO(user): Differentiate between directed and undirected edge strings.
  */
 public abstract class AbstractGraphTest {
   MutableGraph<Integer> graph;
   static final Integer N1 = 1;
   static final Integer N2 = 2;
   static final Integer N3 = 3;
   static final Integer N4 = 4;
   static final Integer N5 = 5;
   static final Integer NODE_NOT_IN_GRAPH = 1000;

   // TODO(user): Consider separating Strings that we've defined here to capture
   // identifiable substrings of expected error messages, from Strings that we've defined
   // here to provide error messages.
   // TODO(user): Some Strings used in the subclasses can be added as static Strings
   // here too.
   static final String ERROR_MODIFIABLE_SET = "Set returned is unexpectedly modifiable";
   static final String ERROR_SELF_LOOP = "self-loops are not allowed";
   static final String ERROR_ADDED_SELF_LOOP = "Should not be allowed to add a self-loop edge.";

   /** Creates and returns an instance of the graph to be tested. */
   public abstract MutableGraph<Integer> createGraph();

   /**
    * A proxy method that adds the node {@code n} to the graph being tested. In case of Immutable
    * graph implementations, this method should add {@code n} to the graph builder and build a new
    * graph with the current builder state.
    *
    * @return {@code true} iff the graph was modified as a result of this call
    */
   @CanIgnoreReturnValue
   protected boolean addNode(Integer n) {
     return graph.addNode(n);
   }

   /**
    * A proxy method that adds the edge {@code e} to the graph being tested. In case of Immutable
    * graph implementations, this method should add {@code e} to the graph builder and build a new
    * graph with the current builder state.
    *
    * <p>This method should be used in tests of specific implementations if you want to ensure
    * uniform behavior (including side effects) with how edges are added elsewhere in the tests. For
    * example, the existing implementations of this method explicitly add the supplied nodes to the
    * graph, and then call {@code graph.addEdge()} to connect the edge to the nodes; this is not part
    * of the contract of {@code graph.addEdge()} and is done for convenience. In cases where you want
    * to avoid such side effects (e.g., if you're testing what happens in your implementation if you
    * add an edge whose end-points don't already exist in the graph), you should <b>not</b> use this
    * method.
    *
    * @return {@code true} iff the graph was modified as a result of this call
    */
   @CanIgnoreReturnValue
   protected boolean putEdge(Integer n1, Integer n2) {
     graph.addNode(n1);
     graph.addNode(n2);
     return graph.putEdge(n1, n2);
   }

   @CanIgnoreReturnValue
   protected boolean putEdge(EndpointPair<Integer> endpoints) {
     graph.addNode(endpoints.nodeU());
     graph.addNode(endpoints.nodeV());
     return graph.putEdge(endpoints);
   }

   @Before
   public void init() {
     graph = createGraph();
   }

   @After
   public void validateGraphState() {
     validateGraph(graph);
   }

   static <N> void validateGraph(Graph<N> graph) {
     assertStronglyEquivalent(graph, Graphs.copyOf(graph));
     assertStronglyEquivalent(graph, ImmutableGraph.copyOf(graph));

     String graphString = graph.toString();
     assertThat(graphString).contains("isDirected: " + graph.isDirected());
     assertThat(graphString).contains("allowsSelfLoops: " + graph.allowsSelfLoops());

     int nodeStart = graphString.indexOf("nodes:");
     int edgeStart = graphString.indexOf("edges:");
     String nodeString = graphString.substring(nodeStart, edgeStart);

     Set<EndpointPair<N>> allEndpointPairs = new HashSet<>();

     for (N node : sanityCheckSet(graph.nodes())) {
       assertThat(nodeString).contains(node.toString());

       if (graph.isDirected()) {
         assertThat(graph.degree(node)).isEqualTo(graph.inDegree(node) + graph.outDegree(node));
         assertThat(graph.predecessors(node)).hasSize(graph.inDegree(node));
         assertThat(graph.successors(node)).hasSize(graph.outDegree(node));
       } else {
         int selfLoopCount = graph.adjacentNodes(node).contains(node) ? 1 : 0;
         assertThat(graph.degree(node)).isEqualTo(graph.adjacentNodes(node).size() + selfLoopCount);
         assertThat(graph.predecessors(node)).isEqualTo(graph.adjacentNodes(node));
         assertThat(graph.successors(node)).isEqualTo(graph.adjacentNodes(node));
         assertThat(graph.inDegree(node)).isEqualTo(graph.degree(node));
         assertThat(graph.outDegree(node)).isEqualTo(graph.degree(node));
       }

       for (N adjacentNode : sanityCheckSet(graph.adjacentNodes(node))) {
         if (!graph.allowsSelfLoops()) {
           assertThat(node).isNotEqualTo(adjacentNode);
         }
         assertThat(
                 graph.predecessors(node).contains(adjacentNode)
                     || graph.successors(node).contains(adjacentNode))
             .isTrue();
       }

       for (N predecessor : sanityCheckSet(graph.predecessors(node))) {
         assertThat(graph.successors(predecessor)).contains(node);
         assertThat(graph.hasEdgeConnecting(predecessor, node)).isTrue();
         assertThat(graph.incidentEdges(node)).contains(EndpointPair.of(graph, predecessor, node));
       }

       for (N successor : sanityCheckSet(graph.successors(node))) {
         allEndpointPairs.add(EndpointPair.of(graph, node, successor));
         assertThat(graph.predecessors(successor)).contains(node);
         assertThat(graph.hasEdgeConnecting(node, successor)).isTrue();
         assertThat(graph.incidentEdges(node)).contains(EndpointPair.of(graph, node, successor));
       }

       for (EndpointPair<N> endpoints : sanityCheckSet(graph.incidentEdges(node))) {
         if (graph.isDirected()) {
           assertThat(graph.hasEdgeConnecting(endpoints.source(), endpoints.target())).isTrue();
         } else {
           assertThat(graph.hasEdgeConnecting(endpoints.nodeU(), endpoints.nodeV())).isTrue();
         }
       }
     }

     sanityCheckSet(graph.edges());
     assertThat(graph.edges()).doesNotContain(EndpointPair.of(graph, new Object(), new Object()));
     assertThat(graph.edges()).isEqualTo(allEndpointPairs);
   }

   /**
    * Verifies that the {@code Set} returned by {@code nodes} has the expected mutability property
    * (see the {@code Graph} documentation for more information).
    */
   @Test
   public abstract void nodes_checkReturnedSetMutability();

   /**
    * Verifies that the {@code Set} returned by {@code adjacentNodes} has the expected mutability
    * property (see the {@code Graph} documentation for more information).
    */
   @Test
   public abstract void adjacentNodes_checkReturnedSetMutability();

   /**
    * Verifies that the {@code Set} returned by {@code predecessors} has the expected mutability
    * property (see the {@code Graph} documentation for more information).
    */
   @Test
   public abstract void predecessors_checkReturnedSetMutability();

   /**
    * Verifies that the {@code Set} returned by {@code successors} has the expected mutability
    * property (see the {@code Graph} documentation for more information).
    */
   @Test
   public abstract void successors_checkReturnedSetMutability();

   /**
    * Verifies that the {@code Set} returned by {@code incidentEdges} has the expected mutability
    * property (see the {@code Graph} documentation for more information).
    */
   @Test
   public abstract void incidentEdges_checkReturnedSetMutability();

   @Test
   public void nodes_oneNode() {
     addNode(N1);
     assertThat(graph.nodes()).containsExactly(N1);
   }

   @Test
   public void nodes_noNodes() {
     assertThat(graph.nodes()).isEmpty();
   }

   @Test
   public void adjacentNodes_oneEdge() {
     putEdge(N1, N2);
     assertThat(graph.adjacentNodes(N1)).containsExactly(N2);
     assertThat(graph.adjacentNodes(N2)).containsExactly(N1);
   }

   @Test
   public void adjacentNodes_noAdjacentNodes() {
     addNode(N1);
     assertThat(graph.adjacentNodes(N1)).isEmpty();
   }

   @Test
   public void adjacentNodes_nodeNotInGraph() {
     try {
       graph.adjacentNodes(NODE_NOT_IN_GRAPH);
       fail(ERROR_NODE_NOT_IN_GRAPH);
     } catch (IllegalArgumentException e) {
       assertNodeNotInGraphErrorMessage(e);
     }
   }

   @Test
   public void predecessors_noPredecessors() {
     addNode(N1);
     assertThat(graph.predecessors(N1)).isEmpty();
   }

   @Test
   public void predecessors_nodeNotInGraph() {
     try {
       graph.predecessors(NODE_NOT_IN_GRAPH);
       fail(ERROR_NODE_NOT_IN_GRAPH);
     } catch (IllegalArgumentException e) {
       assertNodeNotInGraphErrorMessage(e);
     }
   }

   @Test
   public void successors_noSuccessors() {
     addNode(N1);
     assertThat(graph.successors(N1)).isEmpty();
   }

   @Test
   public void successors_nodeNotInGraph() {
     try {
       graph.successors(NODE_NOT_IN_GRAPH);
       fail(ERROR_NODE_NOT_IN_GRAPH);
     } catch (IllegalArgumentException e) {
       assertNodeNotInGraphErrorMessage(e);
     }
   }

   @Test
   public void incidentEdges_noIncidentEdges() {
     addNode(N1);
     assertThat(graph.incidentEdges(N1)).isEmpty();
   }

   @Test
   public void incidentEdges_nodeNotInGraph() {
     try {
       graph.incidentEdges(NODE_NOT_IN_GRAPH);
       fail(ERROR_NODE_NOT_IN_GRAPH);
     } catch (IllegalArgumentException e) {
       assertNodeNotInGraphErrorMessage(e);
     }
   }

   @Test
   public void degree_oneEdge() {
     putEdge(N1, N2);
     assertThat(graph.degree(N1)).isEqualTo(1);
     assertThat(graph.degree(N2)).isEqualTo(1);
   }

   @Test
   public void degree_isolatedNode() {
     addNode(N1);
     assertThat(graph.degree(N1)).isEqualTo(0);
   }

   @Test
   public void degree_nodeNotInGraph() {
     try {
       graph.degree(NODE_NOT_IN_GRAPH);
       fail(ERROR_NODE_NOT_IN_GRAPH);
     } catch (IllegalArgumentException e) {
       assertNodeNotInGraphErrorMessage(e);
     }
   }

   @Test
   public void inDegree_isolatedNode() {
     addNode(N1);
     assertThat(graph.inDegree(N1)).isEqualTo(0);
   }

   @Test
   public void inDegree_nodeNotInGraph() {
     try {
       graph.inDegree(NODE_NOT_IN_GRAPH);
       fail(ERROR_NODE_NOT_IN_GRAPH);
     } catch (IllegalArgumentException e) {
       assertNodeNotInGraphErrorMessage(e);
     }
   }

   @Test
   public void outDegree_isolatedNode() {
     addNode(N1);
     assertThat(graph.outDegree(N1)).isEqualTo(0);
   }

   @Test
   public void outDegree_nodeNotInGraph() {
     try {
       graph.outDegree(NODE_NOT_IN_GRAPH);
       fail(ERROR_NODE_NOT_IN_GRAPH);
     } catch (IllegalArgumentException e) {
       assertNodeNotInGraphErrorMessage(e);
     }
   }

   @Test
   public void addNode_newNode() {
     assertThat(addNode(N1)).isTrue();
     assertThat(graph.nodes()).contains(N1);
   }

   @Test
   public void addNode_existingNode() {
     addNode(N1);
     ImmutableSet<Integer> nodes = ImmutableSet.copyOf(graph.nodes());
     assertThat(addNode(N1)).isFalse();
     assertThat(graph.nodes()).containsExactlyElementsIn(nodes);
   }

   @Test
   public void removeNode_existingNode() {
     putEdge(N1, N2);
     putEdge(N4, N1);
     assertThat(graph.removeNode(N1)).isTrue();
     assertThat(graph.removeNode(N1)).isFalse();
     assertThat(graph.nodes()).containsExactly(N2, N4);
     assertThat(graph.adjacentNodes(N2)).isEmpty();
     assertThat(graph.adjacentNodes(N4)).isEmpty();
   }

   @Test
   public void removeNode_antiparallelEdges() {
     putEdge(N1, N2);
     putEdge(N2, N1);

     assertThat(graph.removeNode(N1)).isTrue();
     assertThat(graph.nodes()).containsExactly(N2);
     assertThat(graph.edges()).isEmpty();

     assertThat(graph.removeNode(N2)).isTrue();
     assertThat(graph.nodes()).isEmpty();
     assertThat(graph.edges()).isEmpty();
   }

   @Test
   public void removeNode_nodeNotPresent() {
     addNode(N1);
     ImmutableSet<Integer> nodes = ImmutableSet.copyOf(graph.nodes());
     assertThat(graph.removeNode(NODE_NOT_IN_GRAPH)).isFalse();
     assertThat(graph.nodes()).containsExactlyElementsIn(nodes);
   }

   @Test
   public void removeNode_queryAfterRemoval() {
     addNode(N1);
     @SuppressWarnings("unused")
     Set<Integer> unused = graph.adjacentNodes(N1); // ensure cache (if any) is populated
     assertThat(graph.removeNode(N1)).isTrue();
     try {
       graph.adjacentNodes(N1);
       fail(ERROR_NODE_NOT_IN_GRAPH);
     } catch (IllegalArgumentException e) {
       assertNodeNotInGraphErrorMessage(e);
     }
   }

   @Test
   public void removeEdge_existingEdge() {
     putEdge(N1, N2);
     assertThat(graph.successors(N1)).containsExactly(N2);
     assertThat(graph.predecessors(N2)).containsExactly(N1);
     assertThat(graph.removeEdge(N1, N2)).isTrue();
     assertThat(graph.removeEdge(N1, N2)).isFalse();
     assertThat(graph.successors(N1)).isEmpty();
     assertThat(graph.predecessors(N2)).isEmpty();
   }

   @Test
   public void removeEdge_oneOfMany() {
     putEdge(N1, N2);
     putEdge(N1, N3);
     putEdge(N1, N4);
     assertThat(graph.removeEdge(N1, N3)).isTrue();
     assertThat(graph.adjacentNodes(N1)).containsExactly(N2, N4);
   }

   @Test
   public void removeEdge_nodeNotPresent() {
     putEdge(N1, N2);
     assertThat(graph.removeEdge(N1, NODE_NOT_IN_GRAPH)).isFalse();
     assertThat(graph.successors(N1)).contains(N2);
   }

   @Test
   public void removeEdge_edgeNotPresent() {
     putEdge(N1, N2);
     addNode(N3);
     assertThat(graph.removeEdge(N1, N3)).isFalse();
     assertThat(graph.successors(N1)).contains(N2);
   }
 }
	/*
	* Copyright (C) 2014 The Guava Authors
	*
	* Licensed under the Apache License, Version 2.0 (the "License");
	* you may not use this file except in compliance with the License.
	* You may obtain a copy of the License at
	*
	* http://www.apache.org/licenses/LICENSE-2.0
	*
	* Unless required by applicable law or agreed to in writing, software
	* distributed under the License is distributed on an "AS IS" BASIS,
	* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
	* See the License for the specific language governing permissions and
	* limitations under the License.
	*/

	package com.google.common.graph;

	import static com.google.common.graph.TestUtil.ERROR_NODE_NOT_IN_GRAPH;
	import static com.google.common.graph.TestUtil.assertNodeNotInGraphErrorMessage;
	import static com.google.common.graph.TestUtil.assertStronglyEquivalent;
	import static com.google.common.graph.TestUtil.sanityCheckSet;
	import static com.google.common.truth.Truth.assertThat;
	import static org.junit.Assert.fail;

	import com.google.common.collect.ImmutableSet;
	import com.google.errorprone.annotations.CanIgnoreReturnValue;
	import java.util.HashSet;
	import java.util.Set;
	import org.junit.After;
	import org.junit.Before;
	import org.junit.Test;

	/**
	* Abstract base class for testing implementations of {@link Graph} interface. Graph instances
	* created for testing should have Integer node and String edge objects.
	*
	* <p>Test cases that should be handled similarly in any graph implementation are included in this
	* class. For example, testing that {@code nodes()} method returns the set of the nodes in the
	* graph. The following test cases are left for the subclasses to handle:
	*
	* <ul>
	* <li>Test cases related to whether the graph is directed, undirected, mutable, or immutable.
	* <li>Test cases related to the specific implementation of the {@link Graph} interface.
	* </ul>
	*
	* TODO(user): Make this class generic (using <N, E>) for all node and edge types.
	* TODO(user): Differentiate between directed and undirected edge strings.
	*/
	public abstract class AbstractGraphTest {
	MutableGraph<Integer> graph;
	static final Integer N1 = 1;
	static final Integer N2 = 2;
	static final Integer N3 = 3;
	static final Integer N4 = 4;
	static final Integer N5 = 5;
	static final Integer NODE_NOT_IN_GRAPH = 1000;

	// TODO(user): Consider separating Strings that we've defined here to capture
	// identifiable substrings of expected error messages, from Strings that we've defined
	// here to provide error messages.
	// TODO(user): Some Strings used in the subclasses can be added as static Strings
	// here too.
	static final String ERROR_MODIFIABLE_SET = "Set returned is unexpectedly modifiable";
	static final String ERROR_SELF_LOOP = "self-loops are not allowed";
	static final String ERROR_ADDED_SELF_LOOP = "Should not be allowed to add a self-loop edge.";

	/** Creates and returns an instance of the graph to be tested. */
	public abstract MutableGraph<Integer> createGraph();

	/**
	* A proxy method that adds the node {@code n} to the graph being tested. In case of Immutable
	* graph implementations, this method should add {@code n} to the graph builder and build a new
	* graph with the current builder state.
	*
	* @return {@code true} iff the graph was modified as a result of this call
	*/
	@CanIgnoreReturnValue
	protected boolean addNode(Integer n) {
	return graph.addNode(n);
	}

	/**
	* A proxy method that adds the edge {@code e} to the graph being tested. In case of Immutable
	* graph implementations, this method should add {@code e} to the graph builder and build a new
	* graph with the current builder state.
	*
	* <p>This method should be used in tests of specific implementations if you want to ensure
	* uniform behavior (including side effects) with how edges are added elsewhere in the tests. For
	* example, the existing implementations of this method explicitly add the supplied nodes to the
	* graph, and then call {@code graph.addEdge()} to connect the edge to the nodes; this is not part
	* of the contract of {@code graph.addEdge()} and is done for convenience. In cases where you want
	* to avoid such side effects (e.g., if you're testing what happens in your implementation if you
	* add an edge whose end-points don't already exist in the graph), you should <b>not</b> use this
	* method.
	*
	* @return {@code true} iff the graph was modified as a result of this call
	*/
	@CanIgnoreReturnValue
	protected boolean putEdge(Integer n1, Integer n2) {
	graph.addNode(n1);
	graph.addNode(n2);
	return graph.putEdge(n1, n2);
	}

	@CanIgnoreReturnValue
	protected boolean putEdge(EndpointPair<Integer> endpoints) {
	graph.addNode(endpoints.nodeU());
	graph.addNode(endpoints.nodeV());
	return graph.putEdge(endpoints);
	}

	@Before
	public void init() {
	graph = createGraph();
	}

	@After
	public void validateGraphState() {
	validateGraph(graph);
	}

	static <N> void validateGraph(Graph<N> graph) {
	assertStronglyEquivalent(graph, Graphs.copyOf(graph));
	assertStronglyEquivalent(graph, ImmutableGraph.copyOf(graph));

	String graphString = graph.toString();
	assertThat(graphString).contains("isDirected: " + graph.isDirected());
	assertThat(graphString).contains("allowsSelfLoops: " + graph.allowsSelfLoops());

	int nodeStart = graphString.indexOf("nodes:");
	int edgeStart = graphString.indexOf("edges:");
	String nodeString = graphString.substring(nodeStart, edgeStart);

	Set<EndpointPair<N>> allEndpointPairs = new HashSet<>();

	for (N node : sanityCheckSet(graph.nodes())) {
	assertThat(nodeString).contains(node.toString());

	if (graph.isDirected()) {
	assertThat(graph.degree(node)).isEqualTo(graph.inDegree(node) + graph.outDegree(node));
	assertThat(graph.predecessors(node)).hasSize(graph.inDegree(node));
	assertThat(graph.successors(node)).hasSize(graph.outDegree(node));
	} else {
	int selfLoopCount = graph.adjacentNodes(node).contains(node) ? 1 : 0;
	assertThat(graph.degree(node)).isEqualTo(graph.adjacentNodes(node).size() + selfLoopCount);
	assertThat(graph.predecessors(node)).isEqualTo(graph.adjacentNodes(node));
	assertThat(graph.successors(node)).isEqualTo(graph.adjacentNodes(node));
	assertThat(graph.inDegree(node)).isEqualTo(graph.degree(node));
	assertThat(graph.outDegree(node)).isEqualTo(graph.degree(node));
	}

	for (N adjacentNode : sanityCheckSet(graph.adjacentNodes(node))) {
	if (!graph.allowsSelfLoops()) {
	assertThat(node).isNotEqualTo(adjacentNode);
	}
	assertThat(
	graph.predecessors(node).contains(adjacentNode)
	\|\| graph.successors(node).contains(adjacentNode))
	.isTrue();
	}

	for (N predecessor : sanityCheckSet(graph.predecessors(node))) {
	assertThat(graph.successors(predecessor)).contains(node);
	assertThat(graph.hasEdgeConnecting(predecessor, node)).isTrue();
	assertThat(graph.incidentEdges(node)).contains(EndpointPair.of(graph, predecessor, node));
	}

	for (N successor : sanityCheckSet(graph.successors(node))) {
	allEndpointPairs.add(EndpointPair.of(graph, node, successor));
	assertThat(graph.predecessors(successor)).contains(node);
	assertThat(graph.hasEdgeConnecting(node, successor)).isTrue();
	assertThat(graph.incidentEdges(node)).contains(EndpointPair.of(graph, node, successor));
	}

	for (EndpointPair<N> endpoints : sanityCheckSet(graph.incidentEdges(node))) {
	if (graph.isDirected()) {
	assertThat(graph.hasEdgeConnecting(endpoints.source(), endpoints.target())).isTrue();
	} else {
	assertThat(graph.hasEdgeConnecting(endpoints.nodeU(), endpoints.nodeV())).isTrue();
	}
	}
	}

	sanityCheckSet(graph.edges());
	assertThat(graph.edges()).doesNotContain(EndpointPair.of(graph, new Object(), new Object()));
	assertThat(graph.edges()).isEqualTo(allEndpointPairs);
	}

	/**
	* Verifies that the {@code Set} returned by {@code nodes} has the expected mutability property
	* (see the {@code Graph} documentation for more information).
	*/
	@Test
	public abstract void nodes_checkReturnedSetMutability();

	/**
	* Verifies that the {@code Set} returned by {@code adjacentNodes} has the expected mutability
	* property (see the {@code Graph} documentation for more information).
	*/
	@Test
	public abstract void adjacentNodes_checkReturnedSetMutability();

	/**
	* Verifies that the {@code Set} returned by {@code predecessors} has the expected mutability
	* property (see the {@code Graph} documentation for more information).
	*/
	@Test
	public abstract void predecessors_checkReturnedSetMutability();

	/**
	* Verifies that the {@code Set} returned by {@code successors} has the expected mutability
	* property (see the {@code Graph} documentation for more information).
	*/
	@Test
	public abstract void successors_checkReturnedSetMutability();

	/**
	* Verifies that the {@code Set} returned by {@code incidentEdges} has the expected mutability
	* property (see the {@code Graph} documentation for more information).
	*/
	@Test
	public abstract void incidentEdges_checkReturnedSetMutability();

	@Test
	public void nodes_oneNode() {
	addNode(N1);
	assertThat(graph.nodes()).containsExactly(N1);
	}

	@Test
	public void nodes_noNodes() {
	assertThat(graph.nodes()).isEmpty();
	}

	@Test
	public void adjacentNodes_oneEdge() {
	putEdge(N1, N2);
	assertThat(graph.adjacentNodes(N1)).containsExactly(N2);
	assertThat(graph.adjacentNodes(N2)).containsExactly(N1);
	}

	@Test
	public void adjacentNodes_noAdjacentNodes() {
	addNode(N1);
	assertThat(graph.adjacentNodes(N1)).isEmpty();
	}

	@Test
	public void adjacentNodes_nodeNotInGraph() {
	try {
	graph.adjacentNodes(NODE_NOT_IN_GRAPH);
	fail(ERROR_NODE_NOT_IN_GRAPH);
	} catch (IllegalArgumentException e) {
	assertNodeNotInGraphErrorMessage(e);
	}
	}

	@Test
	public void predecessors_noPredecessors() {
	addNode(N1);
	assertThat(graph.predecessors(N1)).isEmpty();
	}

	@Test
	public void predecessors_nodeNotInGraph() {
	try {
	graph.predecessors(NODE_NOT_IN_GRAPH);
	fail(ERROR_NODE_NOT_IN_GRAPH);
	} catch (IllegalArgumentException e) {
	assertNodeNotInGraphErrorMessage(e);
	}
	}

	@Test
	public void successors_noSuccessors() {
	addNode(N1);
	assertThat(graph.successors(N1)).isEmpty();
	}

	@Test
	public void successors_nodeNotInGraph() {
	try {
	graph.successors(NODE_NOT_IN_GRAPH);
	fail(ERROR_NODE_NOT_IN_GRAPH);
	} catch (IllegalArgumentException e) {
	assertNodeNotInGraphErrorMessage(e);
	}
	}

	@Test
	public void incidentEdges_noIncidentEdges() {
	addNode(N1);
	assertThat(graph.incidentEdges(N1)).isEmpty();
	}

	@Test
	public void incidentEdges_nodeNotInGraph() {
	try {
	graph.incidentEdges(NODE_NOT_IN_GRAPH);
	fail(ERROR_NODE_NOT_IN_GRAPH);
	} catch (IllegalArgumentException e) {
	assertNodeNotInGraphErrorMessage(e);
	}
	}

	@Test
	public void degree_oneEdge() {
	putEdge(N1, N2);
	assertThat(graph.degree(N1)).isEqualTo(1);
	assertThat(graph.degree(N2)).isEqualTo(1);
	}

	@Test
	public void degree_isolatedNode() {
	addNode(N1);
	assertThat(graph.degree(N1)).isEqualTo(0);
	}

	@Test
	public void degree_nodeNotInGraph() {
	try {
	graph.degree(NODE_NOT_IN_GRAPH);
	fail(ERROR_NODE_NOT_IN_GRAPH);
	} catch (IllegalArgumentException e) {
	assertNodeNotInGraphErrorMessage(e);
	}
	}

	@Test
	public void inDegree_isolatedNode() {
	addNode(N1);
	assertThat(graph.inDegree(N1)).isEqualTo(0);
	}

	@Test
	public void inDegree_nodeNotInGraph() {
	try {
	graph.inDegree(NODE_NOT_IN_GRAPH);
	fail(ERROR_NODE_NOT_IN_GRAPH);
	} catch (IllegalArgumentException e) {
	assertNodeNotInGraphErrorMessage(e);
	}
	}

	@Test
	public void outDegree_isolatedNode() {
	addNode(N1);
	assertThat(graph.outDegree(N1)).isEqualTo(0);
	}

	@Test
	public void outDegree_nodeNotInGraph() {
	try {
	graph.outDegree(NODE_NOT_IN_GRAPH);
	fail(ERROR_NODE_NOT_IN_GRAPH);
	} catch (IllegalArgumentException e) {
	assertNodeNotInGraphErrorMessage(e);
	}
	}

	@Test
	public void addNode_newNode() {
	assertThat(addNode(N1)).isTrue();
	assertThat(graph.nodes()).contains(N1);
	}

	@Test
	public void addNode_existingNode() {
	addNode(N1);
	ImmutableSet<Integer> nodes = ImmutableSet.copyOf(graph.nodes());
	assertThat(addNode(N1)).isFalse();
	assertThat(graph.nodes()).containsExactlyElementsIn(nodes);
	}

	@Test
	public void removeNode_existingNode() {
	putEdge(N1, N2);
	putEdge(N4, N1);
	assertThat(graph.removeNode(N1)).isTrue();
	assertThat(graph.removeNode(N1)).isFalse();
	assertThat(graph.nodes()).containsExactly(N2, N4);
	assertThat(graph.adjacentNodes(N2)).isEmpty();
	assertThat(graph.adjacentNodes(N4)).isEmpty();
	}

	@Test
	public void removeNode_antiparallelEdges() {
	putEdge(N1, N2);
	putEdge(N2, N1);

	assertThat(graph.removeNode(N1)).isTrue();
	assertThat(graph.nodes()).containsExactly(N2);
	assertThat(graph.edges()).isEmpty();

	assertThat(graph.removeNode(N2)).isTrue();
	assertThat(graph.nodes()).isEmpty();
	assertThat(graph.edges()).isEmpty();
	}

	@Test
	public void removeNode_nodeNotPresent() {
	addNode(N1);
	ImmutableSet<Integer> nodes = ImmutableSet.copyOf(graph.nodes());
	assertThat(graph.removeNode(NODE_NOT_IN_GRAPH)).isFalse();
	assertThat(graph.nodes()).containsExactlyElementsIn(nodes);
	}

	@Test
	public void removeNode_queryAfterRemoval() {
	addNode(N1);
	@SuppressWarnings("unused")
	Set<Integer> unused = graph.adjacentNodes(N1); // ensure cache (if any) is populated
	assertThat(graph.removeNode(N1)).isTrue();
	try {
	graph.adjacentNodes(N1);
	fail(ERROR_NODE_NOT_IN_GRAPH);
	} catch (IllegalArgumentException e) {
	assertNodeNotInGraphErrorMessage(e);
	}
	}

	@Test
	public void removeEdge_existingEdge() {
	putEdge(N1, N2);
	assertThat(graph.successors(N1)).containsExactly(N2);
	assertThat(graph.predecessors(N2)).containsExactly(N1);
	assertThat(graph.removeEdge(N1, N2)).isTrue();
	assertThat(graph.removeEdge(N1, N2)).isFalse();
	assertThat(graph.successors(N1)).isEmpty();
	assertThat(graph.predecessors(N2)).isEmpty();
	}

	@Test
	public void removeEdge_oneOfMany() {
	putEdge(N1, N2);
	putEdge(N1, N3);
	putEdge(N1, N4);
	assertThat(graph.removeEdge(N1, N3)).isTrue();
	assertThat(graph.adjacentNodes(N1)).containsExactly(N2, N4);
	}

	@Test
	public void removeEdge_nodeNotPresent() {
	putEdge(N1, N2);
	assertThat(graph.removeEdge(N1, NODE_NOT_IN_GRAPH)).isFalse();
	assertThat(graph.successors(N1)).contains(N2);
	}

	@Test
	public void removeEdge_edgeNotPresent() {
	putEdge(N1, N2);
	addNode(N3);
	assertThat(graph.removeEdge(N1, N3)).isFalse();
	assertThat(graph.successors(N1)).contains(N2);
	}
	}