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 import static org.junit.Assert.assertThrows; 21 22 import com.google.common.collect.ImmutableList; 23 import com.google.common.collect.ImmutableSet; 24 import com.google.common.testing.EqualsTester; 25 import java.util.Collection; 26 import java.util.Set; 27 import org.junit.Test; 28 import org.junit.runner.RunWith; 29 import org.junit.runners.JUnit4; 30 31 /** Tests for {@link EndpointPair} and {@link Graph#edges()}. */ 32 @RunWith(JUnit4.class) 33 public final class EndpointPairTest { 34 private static final Integer N0 = 0; 35 private static final Integer N1 = 1; 36 private static final Integer N2 = 2; 37 private static final Integer N3 = 3; 38 private static final Integer N4 = 4; 39 private static final String E12 = "1-2"; 40 private static final String E12_A = "1-2a"; 41 private static final String E21 = "2-1"; 42 private static final String E13 = "1-3"; 43 private static final String E44 = "4-4"; 44 45 // Test for EndpointPair class 46 47 @Test testOrderedEndpointPair()48 public void testOrderedEndpointPair() { 49 EndpointPair<String> ordered = EndpointPair.ordered("source", "target"); 50 assertThat(ordered.isOrdered()).isTrue(); 51 assertThat(ordered).containsExactly("source", "target").inOrder(); 52 assertThat(ordered.source()).isEqualTo("source"); 53 assertThat(ordered.target()).isEqualTo("target"); 54 assertThat(ordered.nodeU()).isEqualTo("source"); 55 assertThat(ordered.nodeV()).isEqualTo("target"); 56 assertThat(ordered.adjacentNode("source")).isEqualTo("target"); 57 assertThat(ordered.adjacentNode("target")).isEqualTo("source"); 58 assertThat(ordered.toString()).isEqualTo("<source -> target>"); 59 } 60 61 @Test testUnorderedEndpointPair()62 public void testUnorderedEndpointPair() { 63 EndpointPair<String> unordered = EndpointPair.unordered("chicken", "egg"); 64 assertThat(unordered.isOrdered()).isFalse(); 65 assertThat(unordered).containsExactly("chicken", "egg"); 66 assertThat(ImmutableSet.of(unordered.nodeU(), unordered.nodeV())) 67 .containsExactly("chicken", "egg"); 68 assertThat(unordered.adjacentNode(unordered.nodeU())).isEqualTo(unordered.nodeV()); 69 assertThat(unordered.adjacentNode(unordered.nodeV())).isEqualTo(unordered.nodeU()); 70 assertThat(unordered.toString()).contains("chicken"); 71 assertThat(unordered.toString()).contains("egg"); 72 } 73 74 @Test testSelfLoop()75 public void testSelfLoop() { 76 EndpointPair<String> unordered = EndpointPair.unordered("node", "node"); 77 assertThat(unordered.isOrdered()).isFalse(); 78 assertThat(unordered).containsExactly("node", "node"); 79 assertThat(unordered.nodeU()).isEqualTo("node"); 80 assertThat(unordered.nodeV()).isEqualTo("node"); 81 assertThat(unordered.adjacentNode("node")).isEqualTo("node"); 82 assertThat(unordered.toString()).isEqualTo("[node, node]"); 83 } 84 85 @Test testAdjacentNode_nodeNotIncident()86 public void testAdjacentNode_nodeNotIncident() { 87 ImmutableList<MutableNetwork<Integer, String>> testNetworks = 88 ImmutableList.of( 89 NetworkBuilder.directed().<Integer, String>build(), 90 NetworkBuilder.undirected().<Integer, String>build()); 91 for (MutableNetwork<Integer, String> network : testNetworks) { 92 network.addEdge(1, 2, "1-2"); 93 EndpointPair<Integer> endpointPair = network.incidentNodes("1-2"); 94 assertThrows(IllegalArgumentException.class, () -> endpointPair.adjacentNode(3)); 95 } 96 } 97 98 @Test testEquals()99 public void testEquals() { 100 EndpointPair<String> ordered = EndpointPair.ordered("a", "b"); 101 EndpointPair<String> orderedMirror = EndpointPair.ordered("b", "a"); 102 EndpointPair<String> unordered = EndpointPair.unordered("a", "b"); 103 EndpointPair<String> unorderedMirror = EndpointPair.unordered("b", "a"); 104 105 new EqualsTester() 106 .addEqualityGroup(ordered) 107 .addEqualityGroup(orderedMirror) 108 .addEqualityGroup(unordered, unorderedMirror) 109 .testEquals(); 110 } 111 112 // Tests for Graph.edges() and Network.asGraph().edges() methods 113 // TODO(user): Move these to a more appropriate location in the test suite. 114 115 @Test endpointPair_directedGraph()116 public void endpointPair_directedGraph() { 117 MutableGraph<Integer> directedGraph = GraphBuilder.directed().allowsSelfLoops(true).build(); 118 directedGraph.addNode(N0); 119 directedGraph.putEdge(N1, N2); 120 directedGraph.putEdge(N2, N1); 121 directedGraph.putEdge(N1, N3); 122 directedGraph.putEdge(N4, N4); 123 containsExactlySanityCheck( 124 directedGraph.edges(), 125 EndpointPair.ordered(N1, N2), 126 EndpointPair.ordered(N2, N1), 127 EndpointPair.ordered(N1, N3), 128 EndpointPair.ordered(N4, N4)); 129 } 130 131 @Test endpointPair_undirectedGraph()132 public void endpointPair_undirectedGraph() { 133 MutableGraph<Integer> undirectedGraph = GraphBuilder.undirected().allowsSelfLoops(true).build(); 134 undirectedGraph.addNode(N0); 135 undirectedGraph.putEdge(N1, N2); 136 undirectedGraph.putEdge(N2, N1); // does nothing 137 undirectedGraph.putEdge(N1, N3); 138 undirectedGraph.putEdge(N4, N4); 139 containsExactlySanityCheck( 140 undirectedGraph.edges(), 141 EndpointPair.unordered(N1, N2), 142 EndpointPair.unordered(N1, N3), 143 EndpointPair.unordered(N4, N4)); 144 } 145 146 @Test endpointPair_directedNetwork()147 public void endpointPair_directedNetwork() { 148 MutableNetwork<Integer, String> directedNetwork = 149 NetworkBuilder.directed().allowsSelfLoops(true).build(); 150 directedNetwork.addNode(N0); 151 directedNetwork.addEdge(N1, N2, E12); 152 directedNetwork.addEdge(N2, N1, E21); 153 directedNetwork.addEdge(N1, N3, E13); 154 directedNetwork.addEdge(N4, N4, E44); 155 containsExactlySanityCheck( 156 directedNetwork.asGraph().edges(), 157 EndpointPair.ordered(N1, N2), 158 EndpointPair.ordered(N2, N1), 159 EndpointPair.ordered(N1, N3), 160 EndpointPair.ordered(N4, N4)); 161 } 162 163 @Test endpointPair_undirectedNetwork()164 public void endpointPair_undirectedNetwork() { 165 MutableNetwork<Integer, String> undirectedNetwork = 166 NetworkBuilder.undirected().allowsParallelEdges(true).allowsSelfLoops(true).build(); 167 undirectedNetwork.addNode(N0); 168 undirectedNetwork.addEdge(N1, N2, E12); 169 undirectedNetwork.addEdge(N2, N1, E12_A); // adds parallel edge, won't be in Graph edges 170 undirectedNetwork.addEdge(N1, N3, E13); 171 undirectedNetwork.addEdge(N4, N4, E44); 172 containsExactlySanityCheck( 173 undirectedNetwork.asGraph().edges(), 174 EndpointPair.unordered(N1, N2), 175 EndpointPair.unordered(N1, N3), 176 EndpointPair.unordered(N4, N4)); 177 } 178 179 @Test endpointPair_unmodifiableView()180 public void endpointPair_unmodifiableView() { 181 MutableGraph<Integer> directedGraph = GraphBuilder.directed().build(); 182 Set<EndpointPair<Integer>> edges = directedGraph.edges(); 183 184 directedGraph.putEdge(N1, N2); 185 containsExactlySanityCheck(edges, EndpointPair.ordered(N1, N2)); 186 187 directedGraph.putEdge(N2, N1); 188 containsExactlySanityCheck(edges, EndpointPair.ordered(N1, N2), EndpointPair.ordered(N2, N1)); 189 190 directedGraph.removeEdge(N1, N2); 191 directedGraph.removeEdge(N2, N1); 192 containsExactlySanityCheck(edges); 193 194 assertThrows( 195 UnsupportedOperationException.class, () -> edges.add(EndpointPair.ordered(N1, N2))); 196 } 197 198 @Test endpointPair_undirected_contains()199 public void endpointPair_undirected_contains() { 200 MutableGraph<Integer> undirectedGraph = GraphBuilder.undirected().allowsSelfLoops(true).build(); 201 undirectedGraph.putEdge(N1, N1); 202 undirectedGraph.putEdge(N1, N2); 203 Set<EndpointPair<Integer>> edges = undirectedGraph.edges(); 204 205 assertThat(edges).hasSize(2); 206 assertThat(edges).contains(EndpointPair.unordered(N1, N1)); 207 assertThat(edges).contains(EndpointPair.unordered(N1, N2)); 208 assertThat(edges).contains(EndpointPair.unordered(N2, N1)); // equal to unordered(N1, N2) 209 210 // ordered endpoints not compatible with undirected graph 211 assertThat(edges).doesNotContain(EndpointPair.ordered(N1, N2)); 212 213 assertThat(edges).doesNotContain(EndpointPair.unordered(N2, N2)); // edge not present 214 assertThat(edges).doesNotContain(EndpointPair.unordered(N3, N4)); // nodes not in graph 215 } 216 217 @Test endpointPair_directed_contains()218 public void endpointPair_directed_contains() { 219 MutableGraph<Integer> directedGraph = GraphBuilder.directed().allowsSelfLoops(true).build(); 220 directedGraph.putEdge(N1, N1); 221 directedGraph.putEdge(N1, N2); 222 Set<EndpointPair<Integer>> edges = directedGraph.edges(); 223 224 assertThat(edges).hasSize(2); 225 assertThat(edges).contains(EndpointPair.ordered(N1, N1)); 226 assertThat(edges).contains(EndpointPair.ordered(N1, N2)); 227 228 // unordered endpoints not OK for directed graph (undefined behavior) 229 assertThat(edges).doesNotContain(EndpointPair.unordered(N1, N2)); 230 231 assertThat(edges).doesNotContain(EndpointPair.ordered(N2, N1)); // wrong order 232 assertThat(edges).doesNotContain(EndpointPair.ordered(N2, N2)); // edge not present 233 assertThat(edges).doesNotContain(EndpointPair.ordered(N3, N4)); // nodes not in graph 234 } 235 containsExactlySanityCheck(Collection<?> collection, Object... varargs)236 private static void containsExactlySanityCheck(Collection<?> collection, Object... varargs) { 237 assertThat(collection).hasSize(varargs.length); 238 for (Object obj : varargs) { 239 assertThat(collection).contains(obj); 240 } 241 assertThat(collection).containsExactly(varargs); 242 } 243 } 244