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