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 Network}. */ 31 @RunWith(JUnit4.class) 32 33 public final class NetworkMutationTest { 34 private static final int NUM_TRIALS = 25; 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 directedNetwork()40 public void directedNetwork() { 41 testNetworkMutation(NetworkBuilder.directed()); 42 } 43 44 @Test undirectedNetwork()45 public void undirectedNetwork() { 46 testNetworkMutation(NetworkBuilder.undirected()); 47 } 48 testNetworkMutation(NetworkBuilder<? super Integer, Object> networkBuilder)49 private static void testNetworkMutation(NetworkBuilder<? super Integer, Object> networkBuilder) { 50 Random gen = new Random(42); // Fixed seed so test results are deterministic. 51 52 for (int trial = 0; trial < NUM_TRIALS; ++trial) { 53 MutableNetwork<Integer, Object> network = 54 networkBuilder.allowsParallelEdges(true).allowsSelfLoops(true).build(); 55 56 assertThat(network.nodes()).isEmpty(); 57 assertThat(network.edges()).isEmpty(); 58 AbstractNetworkTest.validateNetwork(network); 59 60 while (network.nodes().size() < NUM_NODES) { 61 network.addNode(gen.nextInt(NODE_POOL_SIZE)); 62 } 63 ArrayList<Integer> nodeList = new ArrayList<>(network.nodes()); 64 for (int i = 0; i < NUM_EDGES; ++i) { 65 // Parallel edges are allowed, so this should always succeed. 66 assertThat( 67 network.addEdge( 68 getRandomElement(nodeList, gen), getRandomElement(nodeList, gen), new Object())) 69 .isTrue(); 70 } 71 ArrayList<Object> edgeList = new ArrayList<>(network.edges()); 72 73 assertThat(network.nodes()).hasSize(NUM_NODES); 74 assertThat(network.edges()).hasSize(NUM_EDGES); 75 AbstractNetworkTest.validateNetwork(network); 76 77 Collections.shuffle(edgeList, gen); 78 int numEdgesToRemove = gen.nextInt(NUM_EDGES); 79 for (int i = 0; i < numEdgesToRemove; ++i) { 80 Object edge = edgeList.get(i); 81 assertThat(network.removeEdge(edge)).isTrue(); 82 } 83 84 assertThat(network.nodes()).hasSize(NUM_NODES); 85 assertThat(network.edges()).hasSize(NUM_EDGES - numEdgesToRemove); 86 AbstractNetworkTest.validateNetwork(network); 87 88 Collections.shuffle(nodeList, gen); 89 int numNodesToRemove = gen.nextInt(NUM_NODES); 90 for (int i = 0; i < numNodesToRemove; ++i) { 91 assertThat(network.removeNode(nodeList.get(i))).isTrue(); 92 } 93 94 assertThat(network.nodes()).hasSize(NUM_NODES - numNodesToRemove); 95 // Number of edges remaining is unknown (node's incident edges have been removed). 96 AbstractNetworkTest.validateNetwork(network); 97 98 for (int i = numNodesToRemove; i < NUM_NODES; ++i) { 99 assertThat(network.removeNode(nodeList.get(i))).isTrue(); 100 } 101 102 assertThat(network.nodes()).isEmpty(); 103 assertThat(network.edges()).isEmpty(); // no edges can remain if there's no nodes 104 AbstractNetworkTest.validateNetwork(network); 105 106 Collections.shuffle(nodeList, gen); 107 for (Integer node : nodeList) { 108 assertThat(network.addNode(node)).isTrue(); 109 } 110 Collections.shuffle(edgeList, gen); 111 for (Object edge : edgeList) { 112 assertThat( 113 network.addEdge( 114 getRandomElement(nodeList, gen), getRandomElement(nodeList, gen), edge)) 115 .isTrue(); 116 } 117 118 assertThat(network.nodes()).hasSize(NUM_NODES); 119 assertThat(network.edges()).hasSize(NUM_EDGES); 120 AbstractNetworkTest.validateNetwork(network); 121 } 122 } 123 getRandomElement(L list, Random gen)124 private static <L extends List<T> & RandomAccess, T> T getRandomElement(L list, Random gen) { 125 return list.get(gen.nextInt(list.size())); 126 } 127 } 128