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().size() == 0) {
  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         @Override
 112         public Set<Edge> getInEdges() {
 113             return inEdges;
 114         }
 115
 116         @Override
 117         public Set<Edge> getOutEdges() {
 118             return outEdges;
 119         }
 120
 121         public void addEdge(Node to) {
 122             Edge e = new EdgeImpl(this, to);
 123             outEdges.add(e);
 124             to.getInEdges().add(e);
 125         }
 126
 127         public NodeImpl() {
 128             inEdges = Sets.newHashSet();
 129             outEdges = Sets.newHashSet();
 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         @Override
 141         public Node getFrom() {
 142             return from;
 143         }
 144
 145         @Override
 146         public Node getTo() {
 147             return to;
 148         }
 149
 150         public EdgeImpl(Node from, Node to) {
 151             this.from = from;
 152             this.to = to;
 153
 154         }
 155
 156         @Override
 157         public int hashCode() {
 158             final int prime = 31;
 159             int result = 1;
 160             result = prime * result + ((from == null) ? 0 : from.hashCode());
 161             result = prime * result + ((to == null) ? 0 : to.hashCode());
 162             return result;
 163         }
 164
 165         @Override
 166         public boolean equals(Object obj) {
 167             if (this == obj) {
 168                 return true;
 169             }
 170             if (obj == null) {
 171                 return false;
 172             }
 173             if (getClass() != obj.getClass()) {
 174                 return false;
 175             }
 176             EdgeImpl other = (EdgeImpl) obj;
 177             if (from == null) {
 178                 if (other.from != null) {
 179                     return false;
 180                 }
 181             } else if (!from.equals(other.from)) {
 182                 return false;
 183             }
 184             if (to == null) {
 185                 if (other.to != null) {
 186                     return false;
 187                 }
 188             } else if (!to.equals(other.to)) {
 189                 return false;
 190             }
 191             return true;
 192         }
 193     }
 194
 195 }