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 package com.android.tradefed.util; 17 18 import junit.framework.TestCase; 19 20 /** 21 * Unit tests for {@link DirectedGraph} 22 */ 23 public class DirectedGraphTest extends TestCase { 24 25 public void testBasicGraph() { 26 DirectedGraph<Integer> graph = new DirectedGraph<Integer>(); 27 graph.addEdge(0, 1); 28 graph.addEdge(1, 2); 29 graph.addEdge(2, 3); 30 assertTrue(graph.contains(0)); 31 assertTrue(graph.contains(1)); 32 assertTrue(graph.contains(2)); 33 assertTrue(graph.contains(3)); 34 // no cycle 35 assertTrue(graph.isDag()); 36 } 37 38 public void testCyclicGraph() { 39 DirectedGraph<Integer> graph = new DirectedGraph<Integer>(); 40 graph.addEdge(0, 1); graph.addEdge(0, 2); graph.addEdge(0, 3); 41 graph.addEdge(1, 2); graph.addEdge(1, 3); graph.addEdge(2, 3); 42 graph.addEdge(2, 4); graph.addEdge(4, 5); graph.addEdge(5, 6); 43 // not a cycle. 44 assertTrue(graph.isDag()); 45 // Create a cycle 46 graph.addEdge(4, 1); 47 // cycle now 48 assertFalse(graph.isDag()); 49 // remove the cyle edge 50 graph.removeEdge(4, 1); 51 assertTrue(graph.isDag()); 52 } 53 54 public void testRemoveUnexistingVertex() { 55 DirectedGraph<Integer> graph = new DirectedGraph<Integer>(); 56 try { 57 graph.addEdge(0, 1); 58 // 2 doesn't exists as a destination vertex 59 graph.removeEdge(0, 2); 60 fail("Should have thrown an exception"); 61 } catch (IllegalArgumentException expected) { 62 // expected 63 } 64 65 try { 66 graph.addEdge(0, 1); 67 // 3 doesn't exists as a initial vertex 68 graph.removeEdge(3, 0); 69 fail("Should have thrown an exception"); 70 } catch (IllegalArgumentException expected) { 71 // expected 72 } 73 } 74 } 75