Home | History | Annotate | Download | only in util 
      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