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 java.util.List;
  11 import java.util.Set;
  12
  13 import com.google.common.base.Preconditions;
  14 import com.google.common.collect.Lists;
  15 import com.google.common.collect.Sets;
  16
  17 /**
  18  * Utility class that provides topological sort
  19  */
  20 public final class TopologicalSort {
  21
  22     /**
  23      * It isn't desirable to create instance of this class
  24      */
  25     private TopologicalSort() {
  26     }
  27
  28     /**
  29      * Topological sort of dependent nodes in acyclic graphs.
  30      *
  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().size() == 0) {
  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         @Override
 113         public Set<Edge> getInEdges() {
 114             return inEdges;
 115         }
 116
 117         @Override
 118         public Set<Edge> getOutEdges() {
 119             return outEdges;
 120         }
 121
 122         public void addEdge(Node to) {
 123             Edge e = new EdgeImpl(this, to);
 124             outEdges.add(e);
 125             to.getInEdges().add(e);
 126         }
 127
 128         public NodeImpl() {
 129             inEdges = Sets.newHashSet();
 130             outEdges = Sets.newHashSet();
 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         @Override
 142         public Node getFrom() {
 143             return from;
 144         }
 145
 146         @Override
 147         public Node getTo() {
 148             return to;
 149         }
 150
 151         public EdgeImpl(Node from, Node to) {
 152             this.from = from;
 153             this.to = to;
 154
 155         }
 156
 157         @Override
 158         public int hashCode() {
 159             final int prime = 31;
 160             int result = 1;
 161             result = prime * result + ((from == null) ? 0 : from.hashCode());
 162             result = prime * result + ((to == null) ? 0 : to.hashCode());
 163             return result;
 164         }
 165
 166         @Override
 167         public boolean equals(Object obj) {
 168             if (this == obj) {
 169                 return true;
 170             }
 171             if (obj == null) {
 172                 return false;
 173             }
 174             if (getClass() != obj.getClass()) {
 175                 return false;
 176             }
 177             EdgeImpl other = (EdgeImpl) obj;
 178             if (from == null) {
 179                 if (other.from != null) {
 180                     return false;
 181                 }
 182             } else if (!from.equals(other.from)) {
 183                 return false;
 184             }
 185             if (to == null) {
 186                 if (other.to != null) {
 187                     return false;
 188                 }
 189             } else if (!to.equals(other.to)) {
 190                 return false;
 191             }
 192             return true;
 193         }
 194     }
 195
 196 }