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.fail; 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 try { 95 endpointPair.adjacentNode(3); 96 fail("Should have rejected adjacentNode() called with a node not incident to edge."); 97 } catch (IllegalArgumentException expected) { 98 } 99 } 100 } 101 102 @Test testEquals()103 public void testEquals() { 104 EndpointPair<String> ordered = EndpointPair.ordered("a", "b"); 105 EndpointPair<String> orderedMirror = EndpointPair.ordered("b", "a"); 106 EndpointPair<String> unordered = EndpointPair.unordered("a", "b"); 107 EndpointPair<String> unorderedMirror = EndpointPair.unordered("b", "a"); 108 109 new EqualsTester() 110 .addEqualityGroup(ordered) 111 .addEqualityGroup(orderedMirror) 112 .addEqualityGroup(unordered, unorderedMirror) 113 .testEquals(); 114 } 115 116 // Tests for Graph.edges() and Network.asGraph().edges() methods 117 // TODO(user): Move these to a more appropriate location in the test suite. 118 119 @Test endpointPair_directedGraph()120 public void endpointPair_directedGraph() { 121 MutableGraph<Integer> directedGraph = GraphBuilder.directed().allowsSelfLoops(true).build(); 122 directedGraph.addNode(N0); 123 directedGraph.putEdge(N1, N2); 124 directedGraph.putEdge(N2, N1); 125 directedGraph.putEdge(N1, N3); 126 directedGraph.putEdge(N4, N4); 127 containsExactlySanityCheck( 128 directedGraph.edges(), 129 EndpointPair.ordered(N1, N2), 130 EndpointPair.ordered(N2, N1), 131 EndpointPair.ordered(N1, N3), 132 EndpointPair.ordered(N4, N4)); 133 } 134 135 @Test endpointPair_undirectedGraph()136 public void endpointPair_undirectedGraph() { 137 MutableGraph<Integer> undirectedGraph = GraphBuilder.undirected().allowsSelfLoops(true).build(); 138 undirectedGraph.addNode(N0); 139 undirectedGraph.putEdge(N1, N2); 140 undirectedGraph.putEdge(N2, N1); // does nothing 141 undirectedGraph.putEdge(N1, N3); 142 undirectedGraph.putEdge(N4, N4); 143 containsExactlySanityCheck( 144 undirectedGraph.edges(), 145 EndpointPair.unordered(N1, N2), 146 EndpointPair.unordered(N1, N3), 147 EndpointPair.unordered(N4, N4)); 148 } 149 150 @Test endpointPair_directedNetwork()151 public void endpointPair_directedNetwork() { 152 MutableNetwork<Integer, String> directedNetwork = 153 NetworkBuilder.directed().allowsSelfLoops(true).build(); 154 directedNetwork.addNode(N0); 155 directedNetwork.addEdge(N1, N2, E12); 156 directedNetwork.addEdge(N2, N1, E21); 157 directedNetwork.addEdge(N1, N3, E13); 158 directedNetwork.addEdge(N4, N4, E44); 159 containsExactlySanityCheck( 160 directedNetwork.asGraph().edges(), 161 EndpointPair.ordered(N1, N2), 162 EndpointPair.ordered(N2, N1), 163 EndpointPair.ordered(N1, N3), 164 EndpointPair.ordered(N4, N4)); 165 } 166 167 @Test endpointPair_undirectedNetwork()168 public void endpointPair_undirectedNetwork() { 169 MutableNetwork<Integer, String> undirectedNetwork = 170 NetworkBuilder.undirected().allowsParallelEdges(true).allowsSelfLoops(true).build(); 171 undirectedNetwork.addNode(N0); 172 undirectedNetwork.addEdge(N1, N2, E12); 173 undirectedNetwork.addEdge(N2, N1, E12_A); // adds parallel edge, won't be in Graph edges 174 undirectedNetwork.addEdge(N1, N3, E13); 175 undirectedNetwork.addEdge(N4, N4, E44); 176 containsExactlySanityCheck( 177 undirectedNetwork.asGraph().edges(), 178 EndpointPair.unordered(N1, N2), 179 EndpointPair.unordered(N1, N3), 180 EndpointPair.unordered(N4, N4)); 181 } 182 183 @Test endpointPair_unmodifiableView()184 public void endpointPair_unmodifiableView() { 185 MutableGraph<Integer> directedGraph = GraphBuilder.directed().build(); 186 Set<EndpointPair<Integer>> edges = directedGraph.edges(); 187 188 directedGraph.putEdge(N1, N2); 189 containsExactlySanityCheck(edges, EndpointPair.ordered(N1, N2)); 190 191 directedGraph.putEdge(N2, N1); 192 containsExactlySanityCheck(edges, EndpointPair.ordered(N1, N2), EndpointPair.ordered(N2, N1)); 193 194 directedGraph.removeEdge(N1, N2); 195 directedGraph.removeEdge(N2, N1); 196 containsExactlySanityCheck(edges); 197 198 try { 199 edges.add(EndpointPair.ordered(N1, N2)); 200 fail("Set returned by edges() should be unmodifiable"); 201 } catch (UnsupportedOperationException expected) { 202 } 203 } 204 205 @Test endpointPair_undirected_contains()206 public void endpointPair_undirected_contains() { 207 MutableGraph<Integer> undirectedGraph = GraphBuilder.undirected().allowsSelfLoops(true).build(); 208 undirectedGraph.putEdge(N1, N1); 209 undirectedGraph.putEdge(N1, N2); 210 Set<EndpointPair<Integer>> edges = undirectedGraph.edges(); 211 212 assertThat(edges).hasSize(2); 213 assertThat(edges).contains(EndpointPair.unordered(N1, N1)); 214 assertThat(edges).contains(EndpointPair.unordered(N1, N2)); 215 assertThat(edges).contains(EndpointPair.unordered(N2, N1)); // equal to unordered(N1, N2) 216 217 // ordered endpoints OK for undirected graph (because ordering is irrelevant) 218 assertThat(edges).contains(EndpointPair.ordered(N1, N2)); 219 220 assertThat(edges).doesNotContain(EndpointPair.unordered(N2, N2)); // edge not present 221 assertThat(edges).doesNotContain(EndpointPair.unordered(N3, N4)); // nodes not in graph 222 } 223 224 @Test endpointPair_directed_contains()225 public void endpointPair_directed_contains() { 226 MutableGraph<Integer> directedGraph = GraphBuilder.directed().allowsSelfLoops(true).build(); 227 directedGraph.putEdge(N1, N1); 228 directedGraph.putEdge(N1, N2); 229 Set<EndpointPair<Integer>> edges = directedGraph.edges(); 230 231 assertThat(edges).hasSize(2); 232 assertThat(edges).contains(EndpointPair.ordered(N1, N1)); 233 assertThat(edges).contains(EndpointPair.ordered(N1, N2)); 234 235 // unordered endpoints not OK for directed graph (undefined behavior) 236 assertThat(edges).doesNotContain(EndpointPair.unordered(N1, N2)); 237 238 assertThat(edges).doesNotContain(EndpointPair.ordered(N2, N1)); // wrong order 239 assertThat(edges).doesNotContain(EndpointPair.ordered(N2, N2)); // edge not present 240 assertThat(edges).doesNotContain(EndpointPair.ordered(N3, N4)); // nodes not in graph 241 } 242 containsExactlySanityCheck(Collection<?> collection, Object... varargs)243 private static void containsExactlySanityCheck(Collection<?> collection, Object... varargs) { 244 assertThat(collection).hasSize(varargs.length); 245 for (Object obj : varargs) { 246 assertThat(collection).contains(obj); 247 } 248 assertThat(collection).containsExactly(varargs); 249 } 250 } 251