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