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 java.util.ArrayList; 19 import java.util.HashMap; 20 import java.util.List; 21 import java.util.Map; 22 import java.util.Stack; 23 24 /** 25 * A directed unweighted graphs implementation. The vertex type can be specified. 26 */ 27 public class DirectedGraph<V> { 28 29 /** 30 * The implementation here is basically an adjacency list, but instead 31 * of an array of lists, a Map is used to map each vertex to its list of 32 * adjacent vertices. 33 */ 34 private Map<V,List<V>> neighbors = new HashMap<V, List<V>>(); 35 36 /** 37 * String representation of graph. 38 */ 39 @Override 40 public String toString() { 41 StringBuffer s = new StringBuffer(); 42 for (V v: neighbors.keySet()) s.append("\n " + v + " -> " + neighbors.get(v)); 43 return s.toString(); 44 } 45 46 /** 47 * Add a vertex to the graph. Inop if vertex is already in graph. 48 */ 49 public void addVertice(V vertex) { 50 if (neighbors.containsKey(vertex)) { 51 return; 52 } 53 neighbors.put(vertex, new ArrayList<V>()); 54 } 55 56 /** 57 * True if graph contains vertex. False otherwise. 58 */ 59 public boolean contains(V vertex) { 60 return neighbors.containsKey(vertex); 61 } 62 63 /** 64 * Add an edge to the graph; if either vertex does not exist, it's added. 65 * This implementation allows the creation of multi-edges and self-loops. 66 */ 67 public void addEdge(V from, V to) { 68 this.addVertice(from); 69 this.addVertice(to); 70 neighbors.get(from).add(to); 71 } 72 73 /** 74 * Remove an edge from the graph. 75 * 76 * @throws IllegalArgumentException if either vertex doesn't exist. 77 */ 78 public void removeEdge(V from, V to) { 79 if (!(this.contains(from) && this.contains(to))) { 80 throw new IllegalArgumentException("Nonexistent vertex"); 81 } 82 neighbors.get(from).remove(to); 83 } 84 85 /** 86 * Return a map representation the in-degree of each vertex. 87 */ 88 private Map<V, Integer> inDegree() { 89 Map<V, Integer> result = new HashMap<V, Integer>(); 90 // All initial in-degrees are 0 91 for (V v: neighbors.keySet()) { 92 result.put(v, 0); 93 } 94 // Iterate over an count the in-degree 95 for (V from: neighbors.keySet()) { 96 for (V to: neighbors.get(from)) { 97 result.put(to, result.get(to) + 1); 98 } 99 } 100 return result; 101 } 102 103 /** 104 * Return a List of the topological sort of the vertices; null for no such sort. 105 */ 106 private List<V> topSort() { 107 Map<V, Integer> degree = inDegree(); 108 // Determine all vertices with zero in-degree 109 Stack<V> zeroVerts = new Stack<V>(); 110 for (V v: degree.keySet()) { 111 if (degree.get(v) == 0) { 112 zeroVerts.push(v); 113 } 114 } 115 // Determine the topological order 116 List<V> result = new ArrayList<V>(); 117 while (!zeroVerts.isEmpty()) { 118 // Choose a vertex with zero in-degree 119 V v = zeroVerts.pop(); 120 // Vertex v is next in topol order 121 result.add(v); 122 // "Remove" vertex v by updating its neighbors 123 for (V neighbor: neighbors.get(v)) { 124 degree.put(neighbor, degree.get(neighbor) - 1); 125 // Remember any vertices that now have zero in-degree 126 if (degree.get(neighbor) == 0) { 127 zeroVerts.push(neighbor); 128 } 129 } 130 } 131 // Check that we have used the entire graph (if not, there was a cycle) 132 if (result.size() != neighbors.size()) { 133 return null; 134 } 135 return result; 136 } 137 138 /** 139 * True if graph is a dag (directed acyclic graph). 140 */ 141 public boolean isDag() { 142 return topSort() != null; 143 } 144 } 145