• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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