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