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      * @param nodes graph nodes
  31      * @return Sorted {@link List} of {@link Node}s. Order: Nodes with no
  32      *         dependencies starting.
  33      * @throws IllegalStateException
  34      *             when cycle is present in the graph
  35      */
  36     public static List<Node> sort(Set<Node> nodes) {
  37         List<Node> sortedNodes = Lists.newArrayList();
  38
  39         Set<Node> dependentNodes = getDependentNodes(nodes);
  40
  41         while (!dependentNodes.isEmpty()) {
  42             Node n = dependentNodes.iterator().next();
  43             dependentNodes.remove(n);
  44
  45             sortedNodes.add(n);
  46
  47             for (Edge e : n.getInEdges()) {
  48                 Node m = e.getFrom();
  49                 m.getOutEdges().remove(e);
  50
  51                 if (m.getOutEdges().isEmpty()) {
  52                     dependentNodes.add(m);
  53                 }
  54             }
  55         }
  56
  57         detectCycles(nodes);
  58
  59         return sortedNodes;
  60     }
  61
  62     private static Set<Node> getDependentNodes(Set<Node> nodes) {
  63         Set<Node> dependentNodes = Sets.newHashSet();
  64         for (Node n : nodes) {
  65             if (n.getOutEdges().isEmpty()) {
  66                 dependentNodes.add(n);
  67             }
  68         }
  69         return dependentNodes;
  70     }
  71
  72     private static void detectCycles(Set<Node> nodes) {
  73         // Detect cycles
  74         boolean cycle = false;
  75         Node cycledNode = null;
  76
  77         for (Node n : nodes) {
  78             if (!n.getOutEdges().isEmpty()) {
  79                 cycle = true;
  80                 cycledNode = n;
  81                 break;
  82             }
  83         }
  84         Preconditions.checkState(!cycle, "Cycle detected in graph around node: " + cycledNode);
  85     }
  86
  87     /**
  88      * Interface for nodes in graph that can be sorted topologically
  89      */
  90     public interface Node {
  91         Set<Edge> getInEdges();
  92
  93         Set<Edge> getOutEdges();
  94     }
  95
  96     /**
  97      * Interface for edges in graph that can be sorted topologically
  98      */
  99     public interface Edge {
 100         Node getFrom();
 101
 102         Node getTo();
 103     }
 104
 105     /**
 106      * Basic Node implementation.
 107      */
 108     public static class NodeImpl implements Node {
 109         private final Set<Edge> inEdges;
 110         private final Set<Edge> outEdges;
 111
 112         public NodeImpl() {
 113             inEdges = Sets.newHashSet();
 114             outEdges = Sets.newHashSet();
 115         }
 116
 117         @Override
 118         public Set<Edge> getInEdges() {
 119             return inEdges;
 120         }
 121
 122         @Override
 123         public Set<Edge> getOutEdges() {
 124             return outEdges;
 125         }
 126
 127         public void addEdge(Node to) {
 128             Edge e = new EdgeImpl(this, to);
 129             outEdges.add(e);
 130             to.getInEdges().add(e);
 131         }
 132     }
 133
 134     /**
 135      * Basic Edge implementation
 136      */
 137     public static class EdgeImpl implements Edge {
 138         private final Node from;
 139         private final Node to;
 140
 141         public EdgeImpl(Node from, Node to) {
 142             this.from = from;
 143             this.to = to;
 144         }
 145
 146         @Override
 147         public Node getFrom() {
 148             return from;
 149         }
 150
 151         @Override
 152         public Node getTo() {
 153             return to;
 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 }