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