common/util/src/main/java/org/opendaylight/yangtools/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.util;
   9
  10 import static com.google.common.base.Preconditions.checkState;
  11
  12 import com.google.common.annotations.Beta;
  13 import java.util.ArrayList;
  14 import java.util.HashSet;
  15 import java.util.List;
  16 import java.util.Objects;
  17 import java.util.Set;
  18
  19 /**
  20  * Utility class that provides topological sort.
  21  *
  22  * <p>
  23  * Note this class is non-public to allow for API transition.
  24  */
  25 @Beta
  26 public final class TopologicalSort {
  27
  28     /**
  29      * It isn't desirable to create instance of this class.
  30      */
  31     private TopologicalSort() {
  32     }
  33
  34     /**
  35      * Topological sort of dependent nodes in acyclic graphs.
  36      *
  37      * @param nodes graph nodes
  38      * @return Sorted {@link List} of {@link Node}s. Order: Nodes with no dependencies starting.
  39      * @throws IllegalStateException when cycle is present in the graph
  40      */
  41     public static List<Node> sort(final Set<Node> nodes) {
  42         List<Node> sortedNodes = new ArrayList<>(nodes.size());
  43
  44         Set<Node> dependentNodes = getDependentNodes(nodes);
  45
  46         while (!dependentNodes.isEmpty()) {
  47             Node node = dependentNodes.iterator().next();
  48             dependentNodes.remove(node);
  49
  50             sortedNodes.add(node);
  51
  52             for (Edge edge : node.getInEdges()) {
  53                 Node referent = edge.getFrom();
  54                 referent.getOutEdges().remove(edge);
  55
  56                 if (referent.getOutEdges().isEmpty()) {
  57                     dependentNodes.add(referent);
  58                 }
  59             }
  60         }
  61
  62         detectCycles(nodes);
  63
  64         return sortedNodes;
  65     }
  66
  67     private static Set<Node> getDependentNodes(final Set<Node> nodes) {
  68         Set<Node> dependentNodes = new HashSet<>();
  69         for (Node node : nodes) {
  70             if (node.getOutEdges().isEmpty()) {
  71                 dependentNodes.add(node);
  72             }
  73         }
  74         return dependentNodes;
  75     }
  76
  77     private static void detectCycles(final Set<Node> nodes) {
  78         // Detect cycles
  79         boolean cycle = false;
  80         Node cycledNode = null;
  81
  82         for (Node node : nodes) {
  83             if (!node.getOutEdges().isEmpty()) {
  84                 cycle = true;
  85                 cycledNode = node;
  86                 break;
  87             }
  88         }
  89         checkState(!cycle, "Cycle detected in graph around node: " + cycledNode);
  90     }
  91
  92     /**
  93      * Interface for nodes in graph that can be sorted topologically.
  94      */
  95     @Beta
  96     public interface Node {
  97         Set<Edge> getInEdges();
  98
  99         Set<Edge> getOutEdges();
 100     }
 101
 102     /**
 103      * Interface for edges in graph that can be sorted topologically.
 104      */
 105     @Beta
 106     public interface Edge {
 107         Node getFrom();
 108
 109         Node getTo();
 110     }
 111
 112     /**
 113      * Basic Node implementation.
 114      */
 115     @Beta
 116     public static class NodeImpl implements Node {
 117         private final Set<Edge> inEdges = new HashSet<>();
 118         private final Set<Edge> outEdges = new HashSet<>();
 119
 120         @Override
 121         public Set<Edge> getInEdges() {
 122             return inEdges;
 123         }
 124
 125         @Override
 126         public Set<Edge> getOutEdges() {
 127             return outEdges;
 128         }
 129
 130         public void addEdge(final Node to) {
 131             Edge edge = new EdgeImpl(this, to);
 132             outEdges.add(edge);
 133             to.getInEdges().add(edge);
 134         }
 135     }
 136
 137     /**
 138      * Basic Edge implementation.
 139      */
 140     @Beta
 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 }