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.graph.GraphConstants.ENDPOINTS_MISMATCH; 20 import static com.google.common.graph.TestUtil.assertStronglyEquivalent; 21 import static com.google.common.truth.Truth.assertThat; 22 import static org.junit.Assert.fail; 23 24 import org.junit.After; 25 import org.junit.Test; 26 import org.junit.runner.RunWith; 27 import org.junit.runners.JUnit4; 28 29 /** Tests for {@link ConfigurableMutableValueGraph} and related functionality. */ 30 // TODO(user): Expand coverage and move to proper test suite. 31 @RunWith(JUnit4.class) 32 public final class ValueGraphTest { 33 private static final String DEFAULT = "default"; 34 35 MutableValueGraph<Integer, String> graph; 36 37 @After validateGraphState()38 public void validateGraphState() { 39 assertStronglyEquivalent(graph, Graphs.copyOf(graph)); 40 assertStronglyEquivalent(graph, ImmutableValueGraph.copyOf(graph)); 41 42 Graph<Integer> asGraph = graph.asGraph(); 43 AbstractGraphTest.validateGraph(asGraph); 44 assertThat(graph.nodes()).isEqualTo(asGraph.nodes()); 45 assertThat(graph.edges()).isEqualTo(asGraph.edges()); 46 assertThat(graph.nodeOrder()).isEqualTo(asGraph.nodeOrder()); 47 assertThat(graph.isDirected()).isEqualTo(asGraph.isDirected()); 48 assertThat(graph.allowsSelfLoops()).isEqualTo(asGraph.allowsSelfLoops()); 49 50 for (Integer node : graph.nodes()) { 51 assertThat(graph.adjacentNodes(node)).isEqualTo(asGraph.adjacentNodes(node)); 52 assertThat(graph.predecessors(node)).isEqualTo(asGraph.predecessors(node)); 53 assertThat(graph.successors(node)).isEqualTo(asGraph.successors(node)); 54 assertThat(graph.degree(node)).isEqualTo(asGraph.degree(node)); 55 assertThat(graph.inDegree(node)).isEqualTo(asGraph.inDegree(node)); 56 assertThat(graph.outDegree(node)).isEqualTo(asGraph.outDegree(node)); 57 58 for (Integer otherNode : graph.nodes()) { 59 boolean hasEdge = graph.hasEdgeConnecting(node, otherNode); 60 assertThat(hasEdge).isEqualTo(asGraph.hasEdgeConnecting(node, otherNode)); 61 assertThat(graph.edgeValueOrDefault(node, otherNode, null) != null).isEqualTo(hasEdge); 62 assertThat(!graph.edgeValueOrDefault(node, otherNode, DEFAULT).equals(DEFAULT)) 63 .isEqualTo(hasEdge); 64 } 65 } 66 } 67 68 @Test directedGraph()69 public void directedGraph() { 70 graph = ValueGraphBuilder.directed().allowsSelfLoops(true).build(); 71 graph.putEdgeValue(1, 2, "valueA"); 72 graph.putEdgeValue(2, 1, "valueB"); 73 graph.putEdgeValue(2, 3, "valueC"); 74 graph.putEdgeValue(4, 4, "valueD"); 75 76 assertThat(graph.edgeValueOrDefault(1, 2, null)).isEqualTo("valueA"); 77 assertThat(graph.edgeValueOrDefault(2, 1, null)).isEqualTo("valueB"); 78 assertThat(graph.edgeValueOrDefault(2, 3, null)).isEqualTo("valueC"); 79 assertThat(graph.edgeValueOrDefault(4, 4, null)).isEqualTo("valueD"); 80 assertThat(graph.edgeValueOrDefault(1, 2, DEFAULT)).isEqualTo("valueA"); 81 assertThat(graph.edgeValueOrDefault(2, 1, DEFAULT)).isEqualTo("valueB"); 82 assertThat(graph.edgeValueOrDefault(2, 3, DEFAULT)).isEqualTo("valueC"); 83 assertThat(graph.edgeValueOrDefault(4, 4, DEFAULT)).isEqualTo("valueD"); 84 85 String toString = graph.toString(); 86 assertThat(toString).contains("valueA"); 87 assertThat(toString).contains("valueB"); 88 assertThat(toString).contains("valueC"); 89 assertThat(toString).contains("valueD"); 90 } 91 92 @Test undirectedGraph()93 public void undirectedGraph() { 94 graph = ValueGraphBuilder.undirected().allowsSelfLoops(true).build(); 95 graph.putEdgeValue(1, 2, "valueA"); 96 graph.putEdgeValue(2, 1, "valueB"); // overwrites valueA in undirected case 97 graph.putEdgeValue(2, 3, "valueC"); 98 graph.putEdgeValue(4, 4, "valueD"); 99 100 assertThat(graph.edgeValueOrDefault(1, 2, null)).isEqualTo("valueB"); 101 assertThat(graph.edgeValueOrDefault(2, 1, null)).isEqualTo("valueB"); 102 assertThat(graph.edgeValueOrDefault(2, 3, null)).isEqualTo("valueC"); 103 assertThat(graph.edgeValueOrDefault(4, 4, null)).isEqualTo("valueD"); 104 assertThat(graph.edgeValueOrDefault(1, 2, DEFAULT)).isEqualTo("valueB"); 105 assertThat(graph.edgeValueOrDefault(2, 1, DEFAULT)).isEqualTo("valueB"); 106 assertThat(graph.edgeValueOrDefault(2, 3, DEFAULT)).isEqualTo("valueC"); 107 assertThat(graph.edgeValueOrDefault(4, 4, DEFAULT)).isEqualTo("valueD"); 108 109 String toString = graph.toString(); 110 assertThat(toString).doesNotContain("valueA"); 111 assertThat(toString).contains("valueB"); 112 assertThat(toString).contains("valueC"); 113 assertThat(toString).contains("valueD"); 114 } 115 116 @Test hasEdgeConnecting_directed_correct()117 public void hasEdgeConnecting_directed_correct() { 118 graph = ValueGraphBuilder.directed().build(); 119 graph.putEdgeValue(1, 2, "A"); 120 assertThat(graph.hasEdgeConnecting(EndpointPair.ordered(1, 2))).isTrue(); 121 } 122 123 @Test hasEdgeConnecting_directed_backwards()124 public void hasEdgeConnecting_directed_backwards() { 125 graph = ValueGraphBuilder.directed().build(); 126 graph.putEdgeValue(1, 2, "A"); 127 assertThat(graph.hasEdgeConnecting(EndpointPair.ordered(2, 1))).isFalse(); 128 } 129 130 @Test hasEdgeConnecting_directed_mismatch()131 public void hasEdgeConnecting_directed_mismatch() { 132 graph = ValueGraphBuilder.directed().build(); 133 graph.putEdgeValue(1, 2, "A"); 134 assertThat(graph.hasEdgeConnecting(EndpointPair.unordered(1, 2))).isFalse(); 135 assertThat(graph.hasEdgeConnecting(EndpointPair.unordered(2, 1))).isFalse(); 136 } 137 138 @Test hasEdgeConnecting_undirected_correct()139 public void hasEdgeConnecting_undirected_correct() { 140 graph = ValueGraphBuilder.undirected().build(); 141 graph.putEdgeValue(1, 2, "A"); 142 assertThat(graph.hasEdgeConnecting(EndpointPair.unordered(1, 2))).isTrue(); 143 } 144 145 @Test hasEdgeConnecting_undirected_backwards()146 public void hasEdgeConnecting_undirected_backwards() { 147 graph = ValueGraphBuilder.undirected().build(); 148 graph.putEdgeValue(1, 2, "A"); 149 assertThat(graph.hasEdgeConnecting(EndpointPair.unordered(2, 1))).isTrue(); 150 } 151 152 @Test hasEdgeConnecting_undirected_mismatch()153 public void hasEdgeConnecting_undirected_mismatch() { 154 graph = ValueGraphBuilder.undirected().build(); 155 graph.putEdgeValue(1, 2, "A"); 156 assertThat(graph.hasEdgeConnecting(EndpointPair.ordered(1, 2))).isTrue(); 157 assertThat(graph.hasEdgeConnecting(EndpointPair.ordered(2, 1))).isTrue(); 158 } 159 160 @Test edgeValueOrDefault_directed_correct()161 public void edgeValueOrDefault_directed_correct() { 162 graph = ValueGraphBuilder.directed().build(); 163 graph.putEdgeValue(1, 2, "A"); 164 assertThat(graph.edgeValueOrDefault(EndpointPair.ordered(1, 2), "default")).isEqualTo("A"); 165 } 166 167 @Test edgeValueOrDefault_directed_backwards()168 public void edgeValueOrDefault_directed_backwards() { 169 graph = ValueGraphBuilder.directed().build(); 170 graph.putEdgeValue(1, 2, "A"); 171 assertThat(graph.edgeValueOrDefault(EndpointPair.ordered(2, 1), "default")) 172 .isEqualTo("default"); 173 } 174 175 @Test edgeValueOrDefault_directed_mismatch()176 public void edgeValueOrDefault_directed_mismatch() { 177 graph = ValueGraphBuilder.directed().build(); 178 graph.putEdgeValue(1, 2, "A"); 179 try { 180 String unused = graph.edgeValueOrDefault(EndpointPair.unordered(1, 2), "default"); 181 unused = graph.edgeValueOrDefault(EndpointPair.unordered(2, 1), "default"); 182 fail("Expected IllegalArgumentException: " + ENDPOINTS_MISMATCH); 183 } catch (IllegalArgumentException e) { 184 assertThat(e).hasMessageThat().contains(ENDPOINTS_MISMATCH); 185 } 186 } 187 188 @Test edgeValueOrDefault_undirected_correct()189 public void edgeValueOrDefault_undirected_correct() { 190 graph = ValueGraphBuilder.undirected().build(); 191 graph.putEdgeValue(1, 2, "A"); 192 assertThat(graph.edgeValueOrDefault(EndpointPair.unordered(1, 2), "default")).isEqualTo("A"); 193 } 194 195 @Test edgeValueOrDefault_undirected_backwards()196 public void edgeValueOrDefault_undirected_backwards() { 197 graph = ValueGraphBuilder.undirected().build(); 198 graph.putEdgeValue(1, 2, "A"); 199 assertThat(graph.edgeValueOrDefault(EndpointPair.unordered(2, 1), "default")).isEqualTo("A"); 200 } 201 202 @Test edgeValueOrDefault_undirected_mismatch()203 public void edgeValueOrDefault_undirected_mismatch() { 204 graph = ValueGraphBuilder.undirected().build(); 205 graph.putEdgeValue(1, 2, "A"); 206 assertThat(graph.edgeValueOrDefault(EndpointPair.ordered(2, 1), "default")).isEqualTo("A"); 207 assertThat(graph.edgeValueOrDefault(EndpointPair.ordered(2, 1), "default")).isEqualTo("A"); 208 } 209 210 @Test putEdgeValue_directed()211 public void putEdgeValue_directed() { 212 graph = ValueGraphBuilder.directed().build(); 213 214 assertThat(graph.putEdgeValue(1, 2, "valueA")).isNull(); 215 assertThat(graph.putEdgeValue(2, 1, "valueB")).isNull(); 216 assertThat(graph.putEdgeValue(1, 2, "valueC")).isEqualTo("valueA"); 217 assertThat(graph.putEdgeValue(2, 1, "valueD")).isEqualTo("valueB"); 218 } 219 220 @Test putEdgeValue_directed_orderMismatch()221 public void putEdgeValue_directed_orderMismatch() { 222 graph = ValueGraphBuilder.directed().build(); 223 try { 224 graph.putEdgeValue(EndpointPair.unordered(1, 2), "irrelevant"); 225 fail("Expected IllegalArgumentException: " + ENDPOINTS_MISMATCH); 226 } catch (IllegalArgumentException e) { 227 assertThat(e).hasMessageThat().contains(ENDPOINTS_MISMATCH); 228 } 229 } 230 231 @Test putEdgeValue_undirected_orderMismatch()232 public void putEdgeValue_undirected_orderMismatch() { 233 graph = ValueGraphBuilder.undirected().build(); 234 assertThat(graph.putEdgeValue(EndpointPair.ordered(1, 2), "irrelevant")).isNull(); 235 } 236 237 @Test putEdgeValue_undirected()238 public void putEdgeValue_undirected() { 239 graph = ValueGraphBuilder.undirected().build(); 240 241 assertThat(graph.putEdgeValue(1, 2, "valueA")).isNull(); 242 assertThat(graph.putEdgeValue(2, 1, "valueB")).isEqualTo("valueA"); 243 assertThat(graph.putEdgeValue(1, 2, "valueC")).isEqualTo("valueB"); 244 assertThat(graph.putEdgeValue(2, 1, "valueD")).isEqualTo("valueC"); 245 } 246 247 @Test removeEdge_directed()248 public void removeEdge_directed() { 249 graph = ValueGraphBuilder.directed().build(); 250 graph.putEdgeValue(1, 2, "valueA"); 251 graph.putEdgeValue(2, 1, "valueB"); 252 graph.putEdgeValue(2, 3, "valueC"); 253 254 assertThat(graph.removeEdge(1, 2)).isEqualTo("valueA"); 255 assertThat(graph.removeEdge(1, 2)).isNull(); 256 assertThat(graph.removeEdge(2, 1)).isEqualTo("valueB"); 257 assertThat(graph.removeEdge(2, 1)).isNull(); 258 assertThat(graph.removeEdge(2, 3)).isEqualTo("valueC"); 259 assertThat(graph.removeEdge(2, 3)).isNull(); 260 } 261 262 @Test removeEdge_undirected()263 public void removeEdge_undirected() { 264 graph = ValueGraphBuilder.undirected().build(); 265 graph.putEdgeValue(1, 2, "valueA"); 266 graph.putEdgeValue(2, 1, "valueB"); 267 graph.putEdgeValue(2, 3, "valueC"); 268 269 assertThat(graph.removeEdge(1, 2)).isEqualTo("valueB"); 270 assertThat(graph.removeEdge(1, 2)).isNull(); 271 assertThat(graph.removeEdge(2, 1)).isNull(); 272 assertThat(graph.removeEdge(2, 3)).isEqualTo("valueC"); 273 assertThat(graph.removeEdge(2, 3)).isNull(); 274 } 275 276 @Test removeEdge_directed_orderMismatch()277 public void removeEdge_directed_orderMismatch() { 278 graph = ValueGraphBuilder.directed().build(); 279 graph.putEdgeValue(1, 2, "1->2"); 280 graph.putEdgeValue(2, 1, "2->1"); 281 try { 282 graph.removeEdge(EndpointPair.unordered(1, 2)); 283 graph.removeEdge(EndpointPair.unordered(2, 1)); 284 fail("Expected IllegalArgumentException: " + ENDPOINTS_MISMATCH); 285 } catch (IllegalArgumentException e) { 286 assertThat(e).hasMessageThat().contains(ENDPOINTS_MISMATCH); 287 } 288 } 289 290 @Test removeEdge_undirected_orderMismatch()291 public void removeEdge_undirected_orderMismatch() { 292 graph = ValueGraphBuilder.undirected().build(); 293 graph.putEdgeValue(1, 2, "1-2"); 294 assertThat(graph.removeEdge(EndpointPair.ordered(1, 2))).isEqualTo("1-2"); 295 } 296 297 @Test edgeValue_missing()298 public void edgeValue_missing() { 299 graph = ValueGraphBuilder.directed().build(); 300 301 assertThat(graph.edgeValueOrDefault(1, 2, DEFAULT)).isEqualTo(DEFAULT); 302 assertThat(graph.edgeValueOrDefault(2, 1, DEFAULT)).isEqualTo(DEFAULT); 303 assertThat(graph.edgeValueOrDefault(1, 2, null)).isNull(); 304 assertThat(graph.edgeValueOrDefault(2, 1, null)).isNull(); 305 306 graph.putEdgeValue(1, 2, "valueA"); 307 graph.putEdgeValue(2, 1, "valueB"); 308 assertThat(graph.edgeValueOrDefault(1, 2, DEFAULT)).isEqualTo("valueA"); 309 assertThat(graph.edgeValueOrDefault(2, 1, DEFAULT)).isEqualTo("valueB"); 310 assertThat(graph.edgeValueOrDefault(1, 2, null)).isEqualTo("valueA"); 311 assertThat(graph.edgeValueOrDefault(2, 1, null)).isEqualTo("valueB"); 312 313 graph.removeEdge(1, 2); 314 graph.putEdgeValue(2, 1, "valueC"); 315 assertThat(graph.edgeValueOrDefault(1, 2, DEFAULT)).isEqualTo(DEFAULT); 316 assertThat(graph.edgeValueOrDefault(2, 1, DEFAULT)).isEqualTo("valueC"); 317 assertThat(graph.edgeValueOrDefault(1, 2, null)).isNull(); 318 assertThat(graph.edgeValueOrDefault(2, 1, null)).isEqualTo("valueC"); 319 } 320 321 @Test equivalence_considersEdgeValue()322 public void equivalence_considersEdgeValue() { 323 graph = ValueGraphBuilder.undirected().build(); 324 graph.putEdgeValue(1, 2, "valueA"); 325 326 MutableValueGraph<Integer, String> otherGraph = ValueGraphBuilder.undirected().build(); 327 otherGraph.putEdgeValue(1, 2, "valueA"); 328 assertThat(graph).isEqualTo(otherGraph); 329 330 otherGraph.putEdgeValue(1, 2, "valueB"); 331 assertThat(graph).isNotEqualTo(otherGraph); // values differ 332 } 333 } 334