1 /*
2  * Copyright (C) 2014 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.assertEdgeNotInGraphErrorMessage;
21 import static com.google.common.truth.Truth.assertThat;
22 import static com.google.common.truth.TruthJUnit.assume;
23 import static org.junit.Assert.assertTrue;
24 import static org.junit.Assert.fail;
25 
26 import com.google.common.collect.ImmutableSet;
27 import java.util.Collections;
28 import java.util.Set;
29 import org.junit.After;
30 import org.junit.Test;
31 
32 /**
33  * Abstract base class for testing directed {@link Network} implementations defined in this package.
34  */
35 public abstract class AbstractStandardDirectedNetworkTest extends AbstractNetworkTest {
36 
37   @After
validateSourceAndTarget()38   public void validateSourceAndTarget() {
39     for (Integer node : network.nodes()) {
40       for (String inEdge : network.inEdges(node)) {
41         EndpointPair<Integer> endpointPair = network.incidentNodes(inEdge);
42         assertThat(endpointPair.source()).isEqualTo(endpointPair.adjacentNode(node));
43         assertThat(endpointPair.target()).isEqualTo(node);
44       }
45 
46       for (String outEdge : network.outEdges(node)) {
47         EndpointPair<Integer> endpointPair = network.incidentNodes(outEdge);
48         assertThat(endpointPair.source()).isEqualTo(node);
49         assertThat(endpointPair.target()).isEqualTo(endpointPair.adjacentNode(node));
50       }
51 
52       for (Integer adjacentNode : network.adjacentNodes(node)) {
53         Set<String> edges = network.edgesConnecting(node, adjacentNode);
54         Set<String> antiParallelEdges = network.edgesConnecting(adjacentNode, node);
55         assertThat(node.equals(adjacentNode) || Collections.disjoint(edges, antiParallelEdges))
56             .isTrue();
57       }
58     }
59   }
60 
61   @Override
62   @Test
nodes_checkReturnedSetMutability()63   public void nodes_checkReturnedSetMutability() {
64     assume().that(graphIsMutable()).isTrue();
65 
66     Set<Integer> nodes = network.nodes();
67     try {
68       nodes.add(N2);
69       fail(ERROR_MODIFIABLE_COLLECTION);
70     } catch (UnsupportedOperationException e) {
71       addNode(N1);
72       assertThat(network.nodes()).containsExactlyElementsIn(nodes);
73     }
74   }
75 
76   @Override
77   @Test
edges_checkReturnedSetMutability()78   public void edges_checkReturnedSetMutability() {
79     assume().that(graphIsMutable()).isTrue();
80 
81     Set<String> edges = network.edges();
82     try {
83       edges.add(E12);
84       fail(ERROR_MODIFIABLE_COLLECTION);
85     } catch (UnsupportedOperationException e) {
86       addEdge(N1, N2, E12);
87       assertThat(network.edges()).containsExactlyElementsIn(edges);
88     }
89   }
90 
91   @Override
92   @Test
incidentEdges_checkReturnedSetMutability()93   public void incidentEdges_checkReturnedSetMutability() {
94     assume().that(graphIsMutable()).isTrue();
95 
96     addNode(N1);
97     Set<String> incidentEdges = network.incidentEdges(N1);
98     try {
99       incidentEdges.add(E12);
100       fail(ERROR_MODIFIABLE_COLLECTION);
101     } catch (UnsupportedOperationException e) {
102       addEdge(N1, N2, E12);
103       assertThat(network.incidentEdges(N1)).containsExactlyElementsIn(incidentEdges);
104     }
105   }
106 
107   @Override
108   @Test
adjacentNodes_checkReturnedSetMutability()109   public void adjacentNodes_checkReturnedSetMutability() {
110     assume().that(graphIsMutable()).isTrue();
111 
112     addNode(N1);
113     Set<Integer> adjacentNodes = network.adjacentNodes(N1);
114     try {
115       adjacentNodes.add(N2);
116       fail(ERROR_MODIFIABLE_COLLECTION);
117     } catch (UnsupportedOperationException e) {
118       addEdge(N1, N2, E12);
119       assertThat(network.adjacentNodes(N1)).containsExactlyElementsIn(adjacentNodes);
120     }
121   }
122 
123   @Override
adjacentEdges_checkReturnedSetMutability()124   public void adjacentEdges_checkReturnedSetMutability() {
125     assume().that(graphIsMutable()).isTrue();
126 
127     addEdge(N1, N2, E12);
128     Set<String> adjacentEdges = network.adjacentEdges(E12);
129     try {
130       adjacentEdges.add(E23);
131       fail(ERROR_MODIFIABLE_COLLECTION);
132     } catch (UnsupportedOperationException e) {
133       addEdge(N2, N3, E23);
134       assertThat(network.adjacentEdges(E12)).containsExactlyElementsIn(adjacentEdges);
135     }
136   }
137 
138   @Override
139   @Test
edgesConnecting_checkReturnedSetMutability()140   public void edgesConnecting_checkReturnedSetMutability() {
141     assume().that(graphIsMutable()).isTrue();
142 
143     addNode(N1);
144     addNode(N2);
145     Set<String> edgesConnecting = network.edgesConnecting(N1, N2);
146     try {
147       edgesConnecting.add(E23);
148       fail(ERROR_MODIFIABLE_COLLECTION);
149     } catch (UnsupportedOperationException e) {
150       addEdge(N1, N2, E12);
151       assertThat(network.edgesConnecting(N1, N2)).containsExactlyElementsIn(edgesConnecting);
152     }
153   }
154 
155   @Override
156   @Test
inEdges_checkReturnedSetMutability()157   public void inEdges_checkReturnedSetMutability() {
158     assume().that(graphIsMutable()).isTrue();
159 
160     addNode(N2);
161     Set<String> inEdges = network.inEdges(N2);
162     try {
163       inEdges.add(E12);
164       fail(ERROR_MODIFIABLE_COLLECTION);
165     } catch (UnsupportedOperationException e) {
166       addEdge(N1, N2, E12);
167       assertThat(network.inEdges(N2)).containsExactlyElementsIn(inEdges);
168     }
169   }
170 
171   @Override
172   @Test
outEdges_checkReturnedSetMutability()173   public void outEdges_checkReturnedSetMutability() {
174     assume().that(graphIsMutable()).isTrue();
175 
176     addNode(N1);
177     Set<String> outEdges = network.outEdges(N1);
178     try {
179       outEdges.add(E12);
180       fail(ERROR_MODIFIABLE_COLLECTION);
181     } catch (UnsupportedOperationException e) {
182       addEdge(N1, N2, E12);
183       assertThat(network.outEdges(N1)).containsExactlyElementsIn(outEdges);
184     }
185   }
186 
187   @Override
188   @Test
predecessors_checkReturnedSetMutability()189   public void predecessors_checkReturnedSetMutability() {
190     assume().that(graphIsMutable()).isTrue();
191 
192     addNode(N2);
193     Set<Integer> predecessors = network.predecessors(N2);
194     try {
195       predecessors.add(N1);
196       fail(ERROR_MODIFIABLE_COLLECTION);
197     } catch (UnsupportedOperationException e) {
198       addEdge(N1, N2, E12);
199       assertThat(network.predecessors(N2)).containsExactlyElementsIn(predecessors);
200     }
201   }
202 
203   @Override
204   @Test
successors_checkReturnedSetMutability()205   public void successors_checkReturnedSetMutability() {
206     assume().that(graphIsMutable()).isTrue();
207 
208     addNode(N1);
209     Set<Integer> successors = network.successors(N1);
210     try {
211       successors.add(N2);
212       fail(ERROR_MODIFIABLE_COLLECTION);
213     } catch (UnsupportedOperationException e) {
214       addEdge(N1, N2, E12);
215       assertThat(successors).containsExactlyElementsIn(network.successors(N1));
216     }
217   }
218 
219   @Test
edges_containsOrderMismatch()220   public void edges_containsOrderMismatch() {
221     addEdge(N1, N2, E12);
222     EndpointPair<Integer> endpointsN1N2 = EndpointPair.unordered(N1, N2);
223     EndpointPair<Integer> endpointsN2N1 = EndpointPair.unordered(N2, N1);
224     assertThat(network.asGraph().edges()).doesNotContain(endpointsN1N2);
225     assertThat(network.asGraph().edges()).doesNotContain(endpointsN2N1);
226   }
227 
228   @Test
edgesConnecting_orderMismatch()229   public void edgesConnecting_orderMismatch() {
230     addEdge(N1, N2, E12);
231     try {
232       Set<String> unused = network.edgesConnecting(EndpointPair.unordered(N1, N2));
233       fail("Expected IllegalArgumentException: " + ENDPOINTS_MISMATCH);
234     } catch (IllegalArgumentException e) {
235       assertThat(e).hasMessageThat().contains(ENDPOINTS_MISMATCH);
236     }
237   }
238 
239   @Test
edgeConnectingOrNull_orderMismatch()240   public void edgeConnectingOrNull_orderMismatch() {
241     addEdge(N1, N2, E12);
242     try {
243       String unused = network.edgeConnectingOrNull(EndpointPair.unordered(N1, N2));
244       fail("Expected IllegalArgumentException: " + ENDPOINTS_MISMATCH);
245     } catch (IllegalArgumentException e) {
246       assertThat(e).hasMessageThat().contains(ENDPOINTS_MISMATCH);
247     }
248   }
249 
250   @Override
251   @Test
incidentNodes_oneEdge()252   public void incidentNodes_oneEdge() {
253     addEdge(N1, N2, E12);
254     assertThat(network.incidentNodes(E12).source()).isEqualTo(N1);
255     assertThat(network.incidentNodes(E12).target()).isEqualTo(N2);
256   }
257 
258   @Test
edgesConnecting_oneEdge()259   public void edgesConnecting_oneEdge() {
260     addEdge(N1, N2, E12);
261     assertThat(network.edgesConnecting(N1, N2)).containsExactly(E12);
262     // Passed nodes should be in the correct edge direction, first is the
263     // source node and the second is the target node
264     assertThat(network.edgesConnecting(N2, N1)).isEmpty();
265   }
266 
267   @Test
inEdges_oneEdge()268   public void inEdges_oneEdge() {
269     addEdge(N1, N2, E12);
270     assertThat(network.inEdges(N2)).containsExactly(E12);
271     // Edge direction handled correctly
272     assertThat(network.inEdges(N1)).isEmpty();
273   }
274 
275   @Test
outEdges_oneEdge()276   public void outEdges_oneEdge() {
277     addEdge(N1, N2, E12);
278     assertThat(network.outEdges(N1)).containsExactly(E12);
279     // Edge direction handled correctly
280     assertThat(network.outEdges(N2)).isEmpty();
281   }
282 
283   @Test
predecessors_oneEdge()284   public void predecessors_oneEdge() {
285     addEdge(N1, N2, E12);
286     assertThat(network.predecessors(N2)).containsExactly(N1);
287     // Edge direction handled correctly
288     assertThat(network.predecessors(N1)).isEmpty();
289   }
290 
291   @Test
successors_oneEdge()292   public void successors_oneEdge() {
293     addEdge(N1, N2, E12);
294     assertThat(network.successors(N1)).containsExactly(N2);
295     // Edge direction handled correctly
296     assertThat(network.successors(N2)).isEmpty();
297   }
298 
299   @Test
source_oneEdge()300   public void source_oneEdge() {
301     addEdge(N1, N2, E12);
302     assertThat(network.incidentNodes(E12).source()).isEqualTo(N1);
303   }
304 
305   @Test
source_edgeNotInGraph()306   public void source_edgeNotInGraph() {
307     try {
308       network.incidentNodes(EDGE_NOT_IN_GRAPH).source();
309       fail(ERROR_EDGE_NOT_IN_GRAPH);
310     } catch (IllegalArgumentException e) {
311       assertEdgeNotInGraphErrorMessage(e);
312     }
313   }
314 
315   @Test
target_oneEdge()316   public void target_oneEdge() {
317     addEdge(N1, N2, E12);
318     assertThat(network.incidentNodes(E12).target()).isEqualTo(N2);
319   }
320 
321   @Test
target_edgeNotInGraph()322   public void target_edgeNotInGraph() {
323     try {
324       network.incidentNodes(EDGE_NOT_IN_GRAPH).target();
325       fail(ERROR_EDGE_NOT_IN_GRAPH);
326     } catch (IllegalArgumentException e) {
327       assertEdgeNotInGraphErrorMessage(e);
328     }
329   }
330 
331   @Test
inDegree_oneEdge()332   public void inDegree_oneEdge() {
333     addEdge(N1, N2, E12);
334     assertThat(network.inDegree(N2)).isEqualTo(1);
335     // Edge direction handled correctly
336     assertThat(network.inDegree(N1)).isEqualTo(0);
337   }
338 
339   @Test
outDegree_oneEdge()340   public void outDegree_oneEdge() {
341     addEdge(N1, N2, E12);
342     assertThat(network.outDegree(N1)).isEqualTo(1);
343     // Edge direction handled correctly
344     assertThat(network.outDegree(N2)).isEqualTo(0);
345   }
346 
347   @Test
edges_selfLoop()348   public void edges_selfLoop() {
349     assume().that(network.allowsSelfLoops()).isTrue();
350 
351     addEdge(N1, N1, E11);
352     assertThat(network.edges()).containsExactly(E11);
353   }
354 
355   @Test
incidentEdges_selfLoop()356   public void incidentEdges_selfLoop() {
357     assume().that(network.allowsSelfLoops()).isTrue();
358 
359     addEdge(N1, N1, E11);
360     assertThat(network.incidentEdges(N1)).containsExactly(E11);
361   }
362 
363   @Test
incidentNodes_selfLoop()364   public void incidentNodes_selfLoop() {
365     assume().that(network.allowsSelfLoops()).isTrue();
366 
367     addEdge(N1, N1, E11);
368     assertThat(network.incidentNodes(E11).source()).isEqualTo(N1);
369     assertThat(network.incidentNodes(E11).target()).isEqualTo(N1);
370   }
371 
372   @Test
adjacentNodes_selfLoop()373   public void adjacentNodes_selfLoop() {
374     assume().that(network.allowsSelfLoops()).isTrue();
375 
376     addEdge(N1, N1, E11);
377     addEdge(N1, N2, E12);
378     assertThat(network.adjacentNodes(N1)).containsExactly(N1, N2);
379   }
380 
381   @Test
adjacentEdges_selfLoop()382   public void adjacentEdges_selfLoop() {
383     assume().that(network.allowsSelfLoops()).isTrue();
384 
385     addEdge(N1, N1, E11);
386     addEdge(N1, N2, E12);
387     assertThat(network.adjacentEdges(E11)).containsExactly(E12);
388   }
389 
390   @Test
edgesConnecting_selfLoop()391   public void edgesConnecting_selfLoop() {
392     assume().that(network.allowsSelfLoops()).isTrue();
393 
394     addEdge(N1, N1, E11);
395     assertThat(network.edgesConnecting(N1, N1)).containsExactly(E11);
396     addEdge(N1, N2, E12);
397     assertThat(network.edgesConnecting(N1, N2)).containsExactly(E12);
398     assertThat(network.edgesConnecting(N1, N1)).containsExactly(E11);
399   }
400 
401   @Test
inEdges_selfLoop()402   public void inEdges_selfLoop() {
403     assume().that(network.allowsSelfLoops()).isTrue();
404 
405     addEdge(N1, N1, E11);
406     assertThat(network.inEdges(N1)).containsExactly(E11);
407     addEdge(N4, N1, E41);
408     assertThat(network.inEdges(N1)).containsExactly(E11, E41);
409   }
410 
411   @Test
outEdges_selfLoop()412   public void outEdges_selfLoop() {
413     assume().that(network.allowsSelfLoops()).isTrue();
414 
415     addEdge(N1, N1, E11);
416     assertThat(network.outEdges(N1)).containsExactly(E11);
417     addEdge(N1, N2, E12);
418     assertThat(network.outEdges(N1)).containsExactly(E11, E12);
419   }
420 
421   @Test
predecessors_selfLoop()422   public void predecessors_selfLoop() {
423     assume().that(network.allowsSelfLoops()).isTrue();
424 
425     addEdge(N1, N1, E11);
426     assertThat(network.predecessors(N1)).containsExactly(N1);
427     addEdge(N4, N1, E41);
428     assertThat(network.predecessors(N1)).containsExactly(N1, N4);
429   }
430 
431   @Test
successors_selfLoop()432   public void successors_selfLoop() {
433     assume().that(network.allowsSelfLoops()).isTrue();
434 
435     addEdge(N1, N1, E11);
436     assertThat(network.successors(N1)).containsExactly(N1);
437     addEdge(N1, N2, E12);
438     assertThat(network.successors(N1)).containsExactly(N1, N2);
439   }
440 
441   @Test
source_selfLoop()442   public void source_selfLoop() {
443     assume().that(network.allowsSelfLoops()).isTrue();
444 
445     addEdge(N1, N1, E11);
446     assertThat(network.incidentNodes(E11).source()).isEqualTo(N1);
447   }
448 
449   @Test
target_selfLoop()450   public void target_selfLoop() {
451     assume().that(network.allowsSelfLoops()).isTrue();
452 
453     addEdge(N1, N1, E11);
454     assertThat(network.incidentNodes(E11).target()).isEqualTo(N1);
455   }
456 
457   @Test
degree_selfLoop()458   public void degree_selfLoop() {
459     assume().that(network.allowsSelfLoops()).isTrue();
460 
461     addEdge(N1, N1, E11);
462     assertThat(network.degree(N1)).isEqualTo(2);
463     addEdge(N1, N2, E12);
464     assertThat(network.degree(N1)).isEqualTo(3);
465   }
466 
467   @Test
inDegree_selfLoop()468   public void inDegree_selfLoop() {
469     assume().that(network.allowsSelfLoops()).isTrue();
470 
471     addEdge(N1, N1, E11);
472     assertThat(network.inDegree(N1)).isEqualTo(1);
473     addEdge(N4, N1, E41);
474     assertThat(network.inDegree(N1)).isEqualTo(2);
475   }
476 
477   @Test
outDegree_selfLoop()478   public void outDegree_selfLoop() {
479     assume().that(network.allowsSelfLoops()).isTrue();
480 
481     addEdge(N1, N1, E11);
482     assertThat(network.outDegree(N1)).isEqualTo(1);
483     addEdge(N1, N2, E12);
484     assertThat(network.outDegree(N1)).isEqualTo(2);
485   }
486 
487   // Element Mutation
488 
489   @Test
addEdge_existingNodes()490   public void addEdge_existingNodes() {
491     assume().that(graphIsMutable()).isTrue();
492 
493     // Adding nodes initially for safety (insulating from possible future
494     // modifications to proxy methods)
495     addNode(N1);
496     addNode(N2);
497     assertThat(networkAsMutableNetwork.addEdge(N1, N2, E12)).isTrue();
498     assertThat(network.edges()).contains(E12);
499     assertThat(network.edgesConnecting(N1, N2)).containsExactly(E12);
500     // Direction of the added edge is correctly handled
501     assertThat(network.edgesConnecting(N2, N1)).isEmpty();
502   }
503 
504   @Test
addEdge_existingEdgeBetweenSameNodes()505   public void addEdge_existingEdgeBetweenSameNodes() {
506     assume().that(graphIsMutable()).isTrue();
507 
508     addEdge(N1, N2, E12);
509     ImmutableSet<String> edges = ImmutableSet.copyOf(network.edges());
510     assertThat(networkAsMutableNetwork.addEdge(N1, N2, E12)).isFalse();
511     assertThat(network.edges()).containsExactlyElementsIn(edges);
512   }
513 
514   @Test
addEdge_existingEdgeBetweenDifferentNodes()515   public void addEdge_existingEdgeBetweenDifferentNodes() {
516     assume().that(graphIsMutable()).isTrue();
517 
518     addEdge(N1, N2, E12);
519     try {
520       // Edge between totally different nodes
521       networkAsMutableNetwork.addEdge(N4, N5, E12);
522       fail(ERROR_ADDED_EXISTING_EDGE);
523     } catch (IllegalArgumentException e) {
524       assertThat(e).hasMessageThat().contains(ERROR_REUSE_EDGE);
525     }
526     try {
527       // Edge between same nodes but in reverse direction
528       addEdge(N2, N1, E12);
529       fail(ERROR_ADDED_EXISTING_EDGE);
530     } catch (IllegalArgumentException e) {
531       assertThat(e).hasMessageThat().contains(ERROR_REUSE_EDGE);
532     }
533   }
534 
535   @Test
addEdge_parallelEdge_notAllowed()536   public void addEdge_parallelEdge_notAllowed() {
537     assume().that(graphIsMutable()).isTrue();
538     assume().that(network.allowsParallelEdges()).isFalse();
539 
540     addEdge(N1, N2, E12);
541     try {
542       networkAsMutableNetwork.addEdge(N1, N2, EDGE_NOT_IN_GRAPH);
543       fail(ERROR_ADDED_PARALLEL_EDGE);
544     } catch (IllegalArgumentException e) {
545       assertThat(e).hasMessageThat().contains(ERROR_PARALLEL_EDGE);
546     }
547   }
548 
549   @Test
addEdge_parallelEdge_allowsParallelEdges()550   public void addEdge_parallelEdge_allowsParallelEdges() {
551     assume().that(graphIsMutable()).isTrue();
552     assume().that(network.allowsParallelEdges()).isTrue();
553 
554     assertTrue(networkAsMutableNetwork.addEdge(N1, N2, E12));
555     assertTrue(networkAsMutableNetwork.addEdge(N1, N2, E12_A));
556     assertThat(network.edgesConnecting(N1, N2)).containsExactly(E12, E12_A);
557   }
558 
559   @Test
addEdge_orderMismatch()560   public void addEdge_orderMismatch() {
561     assume().that(graphIsMutable()).isTrue();
562 
563     EndpointPair<Integer> endpoints = EndpointPair.unordered(N1, N2);
564     try {
565       networkAsMutableNetwork.addEdge(endpoints, E12);
566       fail("Expected IllegalArgumentException: " + ENDPOINTS_MISMATCH);
567     } catch (IllegalArgumentException e) {
568       assertThat(e).hasMessageThat().contains(ENDPOINTS_MISMATCH);
569     }
570   }
571 
572   @Test
addEdge_selfLoop_notAllowed()573   public void addEdge_selfLoop_notAllowed() {
574     assume().that(graphIsMutable()).isTrue();
575     assume().that(network.allowsSelfLoops()).isFalse();
576 
577     try {
578       networkAsMutableNetwork.addEdge(N1, N1, E11);
579       fail(ERROR_ADDED_SELF_LOOP);
580     } catch (IllegalArgumentException e) {
581       assertThat(e).hasMessageThat().contains(ERROR_SELF_LOOP);
582     }
583   }
584 
585   /**
586    * This test checks an implementation dependent feature. It tests that the method {@code addEdge}
587    * will silently add the missing nodes to the graph, then add the edge connecting them. We are not
588    * using the proxy methods here as we want to test {@code addEdge} when the end-points are not
589    * elements of the graph.
590    */
591   @Test
addEdge_nodesNotInGraph()592   public void addEdge_nodesNotInGraph() {
593     assume().that(graphIsMutable()).isTrue();
594 
595     networkAsMutableNetwork.addNode(N1);
596     assertTrue(networkAsMutableNetwork.addEdge(N1, N5, E15));
597     assertTrue(networkAsMutableNetwork.addEdge(N4, N1, E41));
598     assertTrue(networkAsMutableNetwork.addEdge(N2, N3, E23));
599     assertThat(network.nodes()).containsExactly(N1, N5, N4, N2, N3);
600     assertThat(network.edges()).containsExactly(E15, E41, E23);
601     assertThat(network.edgesConnecting(N1, N5)).containsExactly(E15);
602     assertThat(network.edgesConnecting(N4, N1)).containsExactly(E41);
603     assertThat(network.edgesConnecting(N2, N3)).containsExactly(E23);
604     // Direction of the added edge is correctly handled
605     assertThat(network.edgesConnecting(N3, N2)).isEmpty();
606   }
607 
608   @Test
addEdge_selfLoop_allowed()609   public void addEdge_selfLoop_allowed() {
610     assume().that(graphIsMutable()).isTrue();
611     assume().that(network.allowsSelfLoops()).isTrue();
612 
613     assertThat(networkAsMutableNetwork.addEdge(N1, N1, E11)).isTrue();
614     assertThat(network.edges()).contains(E11);
615     assertThat(network.edgesConnecting(N1, N1)).containsExactly(E11);
616   }
617 
618   @Test
addEdge_existingSelfLoopEdgeBetweenSameNodes()619   public void addEdge_existingSelfLoopEdgeBetweenSameNodes() {
620     assume().that(graphIsMutable()).isTrue();
621     assume().that(network.allowsSelfLoops()).isTrue();
622 
623     addEdge(N1, N1, E11);
624     ImmutableSet<String> edges = ImmutableSet.copyOf(network.edges());
625     assertThat(networkAsMutableNetwork.addEdge(N1, N1, E11)).isFalse();
626     assertThat(network.edges()).containsExactlyElementsIn(edges);
627   }
628 
629   @Test
addEdge_existingEdgeBetweenDifferentNodes_selfLoops()630   public void addEdge_existingEdgeBetweenDifferentNodes_selfLoops() {
631     assume().that(graphIsMutable()).isTrue();
632     assume().that(network.allowsSelfLoops()).isTrue();
633 
634     addEdge(N1, N1, E11);
635     try {
636       networkAsMutableNetwork.addEdge(N1, N2, E11);
637       fail("Reusing an existing self-loop edge to connect different nodes succeeded");
638     } catch (IllegalArgumentException e) {
639       assertThat(e.getMessage()).contains(ERROR_REUSE_EDGE);
640     }
641     try {
642       networkAsMutableNetwork.addEdge(N2, N2, E11);
643       fail("Reusing an existing self-loop edge to make a different self-loop edge succeeded");
644     } catch (IllegalArgumentException e) {
645       assertThat(e.getMessage()).contains(ERROR_REUSE_EDGE);
646     }
647     addEdge(N1, N2, E12);
648     try {
649       networkAsMutableNetwork.addEdge(N1, N1, E12);
650       fail("Reusing an existing edge to add a self-loop edge between different nodes succeeded");
651     } catch (IllegalArgumentException e) {
652       assertThat(e.getMessage()).contains(ERROR_REUSE_EDGE);
653     }
654   }
655 
656   @Test
addEdge_parallelSelfLoopEdge_notAllowed()657   public void addEdge_parallelSelfLoopEdge_notAllowed() {
658     assume().that(graphIsMutable()).isTrue();
659     assume().that(network.allowsSelfLoops()).isTrue();
660     assume().that(network.allowsParallelEdges()).isFalse();
661 
662     addEdge(N1, N1, E11);
663     try {
664       networkAsMutableNetwork.addEdge(N1, N1, EDGE_NOT_IN_GRAPH);
665       fail("Adding a parallel self-loop edge succeeded");
666     } catch (IllegalArgumentException e) {
667       assertThat(e.getMessage()).contains(ERROR_PARALLEL_EDGE);
668     }
669   }
670 
671   @Test
addEdge_parallelSelfLoopEdge_allowsParallelEdges()672   public void addEdge_parallelSelfLoopEdge_allowsParallelEdges() {
673     assume().that(graphIsMutable()).isTrue();
674     assume().that(network.allowsSelfLoops()).isTrue();
675     assume().that(network.allowsParallelEdges()).isTrue();
676 
677     assertTrue(networkAsMutableNetwork.addEdge(N1, N1, E11));
678     assertTrue(networkAsMutableNetwork.addEdge(N1, N1, E11_A));
679     assertThat(network.edgesConnecting(N1, N1)).containsExactly(E11, E11_A);
680   }
681 
682   @Test
removeNode_existingNodeWithSelfLoopEdge()683   public void removeNode_existingNodeWithSelfLoopEdge() {
684     assume().that(graphIsMutable()).isTrue();
685     assume().that(network.allowsSelfLoops()).isTrue();
686 
687     addNode(N1);
688     addEdge(N1, N1, E11);
689     assertThat(networkAsMutableNetwork.removeNode(N1)).isTrue();
690     assertThat(network.nodes()).isEmpty();
691     assertThat(network.edges()).doesNotContain(E11);
692   }
693 
694   @Test
removeEdge_existingSelfLoopEdge()695   public void removeEdge_existingSelfLoopEdge() {
696     assume().that(graphIsMutable()).isTrue();
697     assume().that(network.allowsSelfLoops()).isTrue();
698 
699     addEdge(N1, N1, E11);
700     assertThat(networkAsMutableNetwork.removeEdge(E11)).isTrue();
701     assertThat(network.edges()).doesNotContain(E11);
702     assertThat(network.edgesConnecting(N1, N1)).isEmpty();
703   }
704 }
705