yang/yang-parser-impl/src/main/java/org/opendaylight/yangtools/yang/parser/util/TopologicalSort.java

   1 /*
   2  * Copyright (c) 2013 Cisco Systems, Inc. and others.  All rights reserved.
   3  *
   4  * This program and the accompanying materials are made available under the
   5  * terms of the Eclipse Public License v1.0 which accompanies this distribution,
   6  * and is available at http://www.eclipse.org/legal/epl-v10.html
   7  */
   8 package org.opendaylight.yangtools.yang.parser.util;
   9
  10 import com.google.common.base.Preconditions;
  11 import com.google.common.collect.Lists;
  12 import com.google.common.collect.Sets;
  13 import java.util.List;
  14 import java.util.Set;
  15
  16 /**
  17  * Utility class that provides topological sort
  18  */
  19 public final class TopologicalSort {
  20
  21     /**
  22      * It isn't desirable to create instance of this class
  23      */
  24     private TopologicalSort() {
  25     }
  26
  27     /**
  28      * Topological sort of dependent nodes in acyclic graphs.
  29      *
  30      * @return Sorted {@link List} of {@link Node}s. Order: Nodes with no
  31      *         dependencies starting.
  32      * @throws IllegalStateException
  33      *             when cycle is present in the graph
  34      */
  35     public static List<Node> sort(Set<Node> nodes) {
  36         List<Node> sortedNodes = Lists.newArrayList();
  37
  38         Set<Node> dependentNodes = getDependentNodes(nodes);
  39
  40         while (!dependentNodes.isEmpty()) {
  41             Node n = dependentNodes.iterator().next();
  42             dependentNodes.remove(n);
  43
  44             sortedNodes.add(n);
  45
  46             for (Edge e : n.getInEdges()) {
  47                 Node m = e.getFrom();
  48                 m.getOutEdges().remove(e);
  49
  50                 if (m.getOutEdges().isEmpty()) {
  51                     dependentNodes.add(m);
  52                 }
  53             }
  54         }
  55
  56         detectCycles(nodes);
  57
  58         return sortedNodes;
  59     }
  60
  61     private static Set<Node> getDependentNodes(Set<Node> nodes) {
  62         Set<Node> dependentNodes = Sets.newHashSet();
  63         for (Node n : nodes) {
  64             if (n.getOutEdges().isEmpty()) {
  65                 dependentNodes.add(n);
  66             }
  67         }
  68         return dependentNodes;
  69     }
  70
  71     private static void detectCycles(Set<Node> nodes) {
  72         // Detect cycles
  73         boolean cycle = false;
  74         Node cycledNode = null;
  75
  76         for (Node n : nodes) {
  77             if (!n.getOutEdges().isEmpty()) {
  78                 cycle = true;
  79                 cycledNode = n;
  80                 break;
  81             }
  82         }
  83         Preconditions.checkState(!cycle, "Cycle detected in graph around node: " + cycledNode);
  84     }
  85
  86     /**
  87      * Interface for nodes in graph that can be sorted topologically
  88      */
  89     public interface Node {
  90         Set<Edge> getInEdges();
  91
  92         Set<Edge> getOutEdges();
  93     }
  94
  95     /**
  96      * Interface for edges in graph that can be sorted topologically
  97      */
  98     public interface Edge {
  99         Node getFrom();
 100
 101         Node getTo();
 102     }
 103
 104     /**
 105      * Basic Node implementation.
 106      */
 107     public static class NodeImpl implements Node {
 108         private final Set<Edge> inEdges;
 109         private final Set<Edge> outEdges;
 110
 111         public NodeImpl() {
 112             inEdges = Sets.newHashSet();
 113             outEdges = Sets.newHashSet();
 114         }
 115
 116         @Override
 117         public Set<Edge> getInEdges() {
 118             return inEdges;
 119         }
 120
 121         @Override
 122         public Set<Edge> getOutEdges() {
 123             return outEdges;
 124         }
 125
 126         public void addEdge(Node to) {
 127             Edge e = new EdgeImpl(this, to);
 128             outEdges.add(e);
 129             to.getInEdges().add(e);
 130         }
 131     }
 132
 133     /**
 134      * Basic Edge implementation
 135      */
 136     public static class EdgeImpl implements Edge {
 137         private final Node from;
 138         private final Node to;
 139
 140         public EdgeImpl(Node from, Node to) {
 141             this.from = from;
 142             this.to = to;
 143         }
 144
 145         @Override
 146         public Node getFrom() {
 147             return from;
 148         }
 149
 150         @Override
 151         public Node getTo() {
 152             return to;
 153         }
 154
 155         @Override
 156         public int hashCode() {
 157             final int prime = 31;
 158             int result = 1;
 159             result = prime * result + ((from == null) ? 0 : from.hashCode());
 160             result = prime * result + ((to == null) ? 0 : to.hashCode());
 161             return result;
 162         }
 163
 164         @Override
 165         public boolean equals(Object obj) {
 166             if (this == obj) {
 167                 return true;
 168             }
 169             if (obj == null) {
 170                 return false;
 171             }
 172             if (getClass() != obj.getClass()) {
 173                 return false;
 174             }
 175             EdgeImpl other = (EdgeImpl) obj;
 176             if (from == null) {
 177                 if (other.from != null) {
 178                     return false;
 179                 }
 180             } else if (!from.equals(other.from)) {
 181                 return false;
 182             }
 183             if (to == null) {
 184                 if (other.to != null) {
 185                     return false;
 186                 }
 187             } else if (!to.equals(other.to)) {
 188                 return false;
 189             }
 190             return true;
 191         }
 192     }
 193
 194 }