1 /* 2 * Copyright 2018 The Android Open Source Project 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 androidx.coordinatorlayout.widget; 18 19 import static org.junit.Assert.assertEquals; 20 import static org.junit.Assert.assertFalse; 21 import static org.junit.Assert.assertNotNull; 22 import static org.junit.Assert.assertTrue; 23 24 import androidx.annotation.NonNull; 25 26 import org.junit.Before; 27 import org.junit.Test; 28 import org.junit.runner.RunWith; 29 import org.junit.runners.JUnit4; 30 31 import java.util.List; 32 33 @RunWith(JUnit4.class) 34 public class DirectedAcyclicGraphTest { 35 36 private DirectedAcyclicGraph<TestNode> mGraph; 37 38 @Before 39 public void setup() { 40 mGraph = new DirectedAcyclicGraph<>(); 41 } 42 43 @Test 44 public void test_addNode() { 45 final TestNode node = new TestNode("node"); 46 mGraph.addNode(node); 47 assertEquals(1, mGraph.size()); 48 assertTrue(mGraph.contains(node)); 49 } 50 51 @Test 52 public void test_addNodeAgain() { 53 final TestNode node = new TestNode("node"); 54 mGraph.addNode(node); 55 mGraph.addNode(node); 56 57 assertEquals(1, mGraph.size()); 58 assertTrue(mGraph.contains(node)); 59 } 60 61 @Test 62 public void test_addEdge() { 63 final TestNode node = new TestNode("node"); 64 final TestNode edge = new TestNode("edge"); 65 66 mGraph.addNode(node); 67 mGraph.addNode(edge); 68 mGraph.addEdge(node, edge); 69 } 70 71 @Test(expected = IllegalArgumentException.class) 72 public void test_addEdgeWithNotAddedEdgeNode() { 73 final TestNode node = new TestNode("node"); 74 final TestNode edge = new TestNode("edge"); 75 76 // Add the node, but not the edge node 77 mGraph.addNode(node); 78 79 // Now add the link 80 mGraph.addEdge(node, edge); 81 } 82 83 @Test 84 public void test_getIncomingEdges() { 85 final TestNode node = new TestNode("node"); 86 final TestNode edge = new TestNode("edge"); 87 mGraph.addNode(node); 88 mGraph.addNode(edge); 89 mGraph.addEdge(node, edge); 90 91 final List<TestNode> incomingEdges = mGraph.getIncomingEdges(node); 92 assertNotNull(incomingEdges); 93 assertEquals(1, incomingEdges.size()); 94 assertEquals(edge, incomingEdges.get(0)); 95 } 96 97 @Test 98 public void test_getOutgoingEdges() { 99 final TestNode node = new TestNode("node"); 100 final TestNode edge = new TestNode("edge"); 101 mGraph.addNode(node); 102 mGraph.addNode(edge); 103 mGraph.addEdge(node, edge); 104 105 // Now assert the getOutgoingEdges returns a list which has one element (node) 106 final List<TestNode> outgoingEdges = mGraph.getOutgoingEdges(edge); 107 assertNotNull(outgoingEdges); 108 assertEquals(1, outgoingEdges.size()); 109 assertTrue(outgoingEdges.contains(node)); 110 } 111 112 @Test 113 public void test_getOutgoingEdgesMultiple() { 114 final TestNode node1 = new TestNode("1"); 115 final TestNode node2 = new TestNode("2"); 116 final TestNode edge = new TestNode("edge"); 117 mGraph.addNode(node1); 118 mGraph.addNode(node2); 119 mGraph.addNode(edge); 120 121 mGraph.addEdge(node1, edge); 122 mGraph.addEdge(node2, edge); 123 124 // Now assert the getOutgoingEdges returns a list which has 2 elements (node1 & node2) 125 final List<TestNode> outgoingEdges = mGraph.getOutgoingEdges(edge); 126 assertNotNull(outgoingEdges); 127 assertEquals(2, outgoingEdges.size()); 128 assertTrue(outgoingEdges.contains(node1)); 129 assertTrue(outgoingEdges.contains(node2)); 130 } 131 132 @Test 133 public void test_hasOutgoingEdges() { 134 final TestNode node = new TestNode("node"); 135 final TestNode edge = new TestNode("edge"); 136 mGraph.addNode(node); 137 mGraph.addNode(edge); 138 139 // There is no edge currently and assert that fact 140 assertFalse(mGraph.hasOutgoingEdges(edge)); 141 // Now add the edge 142 mGraph.addEdge(node, edge); 143 // and assert that the methods returns true; 144 assertTrue(mGraph.hasOutgoingEdges(edge)); 145 } 146 147 @Test 148 public void test_clear() { 149 final TestNode node1 = new TestNode("1"); 150 final TestNode node2 = new TestNode("2"); 151 final TestNode edge = new TestNode("edge"); 152 mGraph.addNode(node1); 153 mGraph.addNode(node2); 154 mGraph.addNode(edge); 155 156 // Now clear the graph 157 mGraph.clear(); 158 159 // Now assert the graph is empty and that contains returns false 160 assertEquals(0, mGraph.size()); 161 assertFalse(mGraph.contains(node1)); 162 assertFalse(mGraph.contains(node2)); 163 assertFalse(mGraph.contains(edge)); 164 } 165 166 @Test 167 public void test_getSortedList() { 168 final TestNode node1 = new TestNode("A"); 169 final TestNode node2 = new TestNode("B"); 170 final TestNode node3 = new TestNode("C"); 171 final TestNode node4 = new TestNode("D"); 172 173 // Now we'll add the nodes 174 mGraph.addNode(node1); 175 mGraph.addNode(node2); 176 mGraph.addNode(node3); 177 mGraph.addNode(node4); 178 179 // Now we'll add edges so that 4 <- 2, 2 <- 3, 3 <- 1 (where <- denotes a dependency) 180 mGraph.addEdge(node4, node2); 181 mGraph.addEdge(node2, node3); 182 mGraph.addEdge(node3, node1); 183 184 final List<TestNode> sorted = mGraph.getSortedList(); 185 // Assert that it is the correct size 186 assertEquals(4, sorted.size()); 187 // Assert that all of the nodes are present and in their sorted order 188 assertEquals(node1, sorted.get(0)); 189 assertEquals(node3, sorted.get(1)); 190 assertEquals(node2, sorted.get(2)); 191 assertEquals(node4, sorted.get(3)); 192 } 193 194 private static class TestNode { 195 private final String mLabel; 196 197 TestNode(@NonNull String label) { 198 mLabel = label; 199 } 200 201 @Override 202 public String toString() { 203 return "TestNode: " + mLabel; 204 } 205 } 206 207 } 208