1 /* 2 * Copyright (C) 2016 The Guava Authors 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17 package com.google.common.graph; 18 19 import static com.google.common.truth.Truth.assertThat; 20 21 import java.util.ArrayList; 22 import java.util.Collections; 23 import java.util.List; 24 import java.util.Random; 25 import java.util.RandomAccess; 26 import org.junit.Test; 27 import org.junit.runner.RunWith; 28 import org.junit.runners.JUnit4; 29 30 /** Tests for repeated node and edge addition and removal in a {@link Graph}. */ 31 @RunWith(JUnit4.class) 32 33 public final class GraphMutationTest { 34 private static final int NUM_TRIALS = 50; 35 private static final int NUM_NODES = 100; 36 private static final int NUM_EDGES = 1000; 37 private static final int NODE_POOL_SIZE = 1000; // must be >> NUM_NODES 38 39 @Test directedGraph()40 public void directedGraph() { 41 testGraphMutation(GraphBuilder.directed()); 42 } 43 44 @Test undirectedGraph()45 public void undirectedGraph() { 46 testGraphMutation(GraphBuilder.undirected()); 47 } 48 testGraphMutation(GraphBuilder<? super Integer> graphBuilder)49 private static void testGraphMutation(GraphBuilder<? super Integer> graphBuilder) { 50 Random gen = new Random(42); // Fixed seed so test results are deterministic. 51 52 for (int trial = 0; trial < NUM_TRIALS; ++trial) { 53 MutableGraph<Integer> graph = graphBuilder.allowsSelfLoops(true).build(); 54 55 assertThat(graph.nodes()).isEmpty(); 56 assertThat(graph.edges()).isEmpty(); 57 AbstractGraphTest.validateGraph(graph); 58 59 while (graph.nodes().size() < NUM_NODES) { 60 graph.addNode(gen.nextInt(NODE_POOL_SIZE)); 61 } 62 ArrayList<Integer> nodeList = new ArrayList<>(graph.nodes()); 63 while (graph.edges().size() < NUM_EDGES) { 64 graph.putEdge(getRandomElement(nodeList, gen), getRandomElement(nodeList, gen)); 65 } 66 ArrayList<EndpointPair<Integer>> edgeList = new ArrayList<>(graph.edges()); 67 68 assertThat(graph.nodes()).hasSize(NUM_NODES); 69 assertThat(graph.edges()).hasSize(NUM_EDGES); 70 AbstractGraphTest.validateGraph(graph); 71 72 Collections.shuffle(edgeList, gen); 73 int numEdgesToRemove = gen.nextInt(NUM_EDGES); 74 for (int i = 0; i < numEdgesToRemove; ++i) { 75 EndpointPair<Integer> edge = edgeList.get(i); 76 assertThat(graph.removeEdge(edge.nodeU(), edge.nodeV())).isTrue(); 77 } 78 79 assertThat(graph.nodes()).hasSize(NUM_NODES); 80 assertThat(graph.edges()).hasSize(NUM_EDGES - numEdgesToRemove); 81 AbstractGraphTest.validateGraph(graph); 82 83 Collections.shuffle(nodeList, gen); 84 int numNodesToRemove = gen.nextInt(NUM_NODES); 85 for (int i = 0; i < numNodesToRemove; ++i) { 86 assertThat(graph.removeNode(nodeList.get(i))).isTrue(); 87 } 88 89 assertThat(graph.nodes()).hasSize(NUM_NODES - numNodesToRemove); 90 // Number of edges remaining is unknown (node's incident edges have been removed). 91 AbstractGraphTest.validateGraph(graph); 92 93 for (int i = numNodesToRemove; i < NUM_NODES; ++i) { 94 assertThat(graph.removeNode(nodeList.get(i))).isTrue(); 95 } 96 97 assertThat(graph.nodes()).isEmpty(); 98 assertThat(graph.edges()).isEmpty(); // no edges can remain if there's no nodes 99 AbstractGraphTest.validateGraph(graph); 100 101 Collections.shuffle(nodeList, gen); 102 for (Integer node : nodeList) { 103 assertThat(graph.addNode(node)).isTrue(); 104 } 105 Collections.shuffle(edgeList, gen); 106 for (EndpointPair<Integer> edge : edgeList) { 107 assertThat(graph.putEdge(edge.nodeU(), edge.nodeV())).isTrue(); 108 } 109 110 assertThat(graph.nodes()).hasSize(NUM_NODES); 111 assertThat(graph.edges()).hasSize(NUM_EDGES); 112 AbstractGraphTest.validateGraph(graph); 113 } 114 } 115 getRandomElement(L list, Random gen)116 private static <L extends List<T> & RandomAccess, T> T getRandomElement(L list, Random gen) { 117 return list.get(gen.nextInt(list.size())); 118 } 119 } 120