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.TestUtil.EdgeType.DIRECTED; 20 import static com.google.common.graph.TestUtil.EdgeType.UNDIRECTED; 21 import static com.google.common.truth.Truth.assertThat; 22 23 import com.google.common.graph.TestUtil.EdgeType; 24 import java.util.Arrays; 25 import java.util.Collection; 26 import org.junit.Test; 27 import org.junit.runner.RunWith; 28 import org.junit.runners.Parameterized; 29 import org.junit.runners.Parameterized.Parameters; 30 31 @AndroidIncompatible 32 // TODO(cpovirk): Figure out Android JUnit 4 support. Does it work with Gingerbread? @RunWith? 33 @RunWith(Parameterized.class) 34 public final class GraphEquivalenceTest { 35 private static final Integer N1 = 1; 36 private static final Integer N2 = 2; 37 private static final Integer N3 = 3; 38 39 private final EdgeType edgeType; 40 private final MutableGraph<Integer> graph; 41 42 // add parameters: directed/undirected 43 @Parameters parameters()44 public static Collection<Object[]> parameters() { 45 return Arrays.asList(new Object[][] {{EdgeType.UNDIRECTED}, {EdgeType.DIRECTED}}); 46 } 47 GraphEquivalenceTest(EdgeType edgeType)48 public GraphEquivalenceTest(EdgeType edgeType) { 49 this.edgeType = edgeType; 50 this.graph = createGraph(edgeType); 51 } 52 createGraph(EdgeType edgeType)53 private static MutableGraph<Integer> createGraph(EdgeType edgeType) { 54 switch (edgeType) { 55 case UNDIRECTED: 56 return GraphBuilder.undirected().allowsSelfLoops(true).build(); 57 case DIRECTED: 58 return GraphBuilder.directed().allowsSelfLoops(true).build(); 59 default: 60 throw new IllegalStateException("Unexpected edge type: " + edgeType); 61 } 62 } 63 oppositeType(EdgeType edgeType)64 private static EdgeType oppositeType(EdgeType edgeType) { 65 switch (edgeType) { 66 case UNDIRECTED: 67 return EdgeType.DIRECTED; 68 case DIRECTED: 69 return EdgeType.UNDIRECTED; 70 default: 71 throw new IllegalStateException("Unexpected edge type: " + edgeType); 72 } 73 } 74 75 @Test equivalent_nodeSetsDiffer()76 public void equivalent_nodeSetsDiffer() { 77 graph.addNode(N1); 78 79 MutableGraph<Integer> g2 = createGraph(edgeType); 80 g2.addNode(N2); 81 82 assertThat(graph).isNotEqualTo(g2); 83 } 84 85 // Node/edge sets are the same, but node/edge connections differ due to edge type. 86 @Test equivalent_directedVsUndirected()87 public void equivalent_directedVsUndirected() { 88 graph.putEdge(N1, N2); 89 90 MutableGraph<Integer> g2 = createGraph(oppositeType(edgeType)); 91 g2.putEdge(N1, N2); 92 93 assertThat(graph).isNotEqualTo(g2); 94 } 95 96 // Node/edge sets and node/edge connections are the same, but directedness differs. 97 @Test equivalent_selfLoop_directedVsUndirected()98 public void equivalent_selfLoop_directedVsUndirected() { 99 graph.putEdge(N1, N1); 100 101 MutableGraph<Integer> g2 = createGraph(oppositeType(edgeType)); 102 g2.putEdge(N1, N1); 103 104 assertThat(graph).isNotEqualTo(g2); 105 } 106 107 // Node/edge sets and node/edge connections are the same, but graph properties differ. 108 // In this case the graphs are considered equivalent; the property differences are irrelevant. 109 @Test equivalent_propertiesDiffer()110 public void equivalent_propertiesDiffer() { 111 graph.putEdge(N1, N2); 112 113 MutableGraph<Integer> g2 = 114 GraphBuilder.from(graph).allowsSelfLoops(!graph.allowsSelfLoops()).build(); 115 g2.putEdge(N1, N2); 116 117 assertThat(graph).isEqualTo(g2); 118 } 119 120 // Node/edge sets and node/edge connections are the same, but edge order differs. 121 // In this case the graphs are considered equivalent; the edge add orderings are irrelevant. 122 @Test equivalent_edgeAddOrdersDiffer()123 public void equivalent_edgeAddOrdersDiffer() { 124 GraphBuilder<Integer> builder = GraphBuilder.from(graph); 125 MutableGraph<Integer> g1 = builder.build(); 126 MutableGraph<Integer> g2 = builder.build(); 127 128 // for g1, add 1->2 first, then 3->1 129 g1.putEdge(N1, N2); 130 g1.putEdge(N3, N1); 131 132 // for g2, add 3->1 first, then 1->2 133 g2.putEdge(N3, N1); 134 g2.putEdge(N1, N2); 135 136 assertThat(g1).isEqualTo(g2); 137 } 138 139 @Test equivalent_edgeDirectionsDiffer()140 public void equivalent_edgeDirectionsDiffer() { 141 graph.putEdge(N1, N2); 142 143 MutableGraph<Integer> g2 = createGraph(edgeType); 144 g2.putEdge(N2, N1); 145 146 switch (edgeType) { 147 case UNDIRECTED: 148 assertThat(graph).isEqualTo(g2); 149 break; 150 case DIRECTED: 151 assertThat(graph).isNotEqualTo(g2); 152 break; 153 default: 154 throw new IllegalStateException("Unexpected edge type: " + edgeType); 155 } 156 } 157 } 158