| /* |
| * 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); |
| } |
| } |