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
toString()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      */
addVertice(V vertex)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      */
contains(V vertex)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      */
addEdge(V from, V to)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      */
removeEdge(V from, V to)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      */
inDegree()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      */
topSort()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      */
isDag()141     public boolean isDag() {
142         return topSort() != null;
143     }
144 }
145