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 com.google.common.annotations.Beta;
  11 import com.google.common.base.Preconditions;
  12 import java.util.ArrayList;
  13 import java.util.HashSet;
  14 import java.util.List;
  15 import java.util.Objects;
  16 import java.util.Set;
  17
  18 /**
  19  * Utility class that provides topological sort.
  20  *
  21  * <p>
  22  * Note this class is non-public to allow for API transition.
  23  */
  24 @Beta
  25 public final class TopologicalSort {
  26
  27     /**
  28      * It isn't desirable to create instance of this class.
  29      */
  30     private TopologicalSort() {
  31     }
  32
  33     /**
  34      * Topological sort of dependent nodes in acyclic graphs.
  35      *
  36      * @param nodes graph nodes
  37      * @return Sorted {@link List} of {@link Node}s. Order: Nodes with no dependencies starting.
  38      * @throws IllegalStateException when cycle is present in the graph
  39      */
  40     public static List<Node> sort(final Set<Node> nodes) {
  41         List<Node> sortedNodes = new ArrayList<>(nodes.size());
  42
  43         Set<Node> dependentNodes = getDependentNodes(nodes);
  44
  45         while (!dependentNodes.isEmpty()) {
  46             Node node = dependentNodes.iterator().next();
  47             dependentNodes.remove(node);
  48
  49             sortedNodes.add(node);
  50
  51             for (Edge edge : node.getInEdges()) {
  52                 Node referent = edge.getFrom();
  53                 referent.getOutEdges().remove(edge);
  54
  55                 if (referent.getOutEdges().isEmpty()) {
  56                     dependentNodes.add(referent);
  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 = new HashSet<>();
  68         for (Node node : nodes) {
  69             if (node.getOutEdges().isEmpty()) {
  70                 dependentNodes.add(node);
  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 node : nodes) {
  82             if (!node.getOutEdges().isEmpty()) {
  83                 cycle = true;
  84                 cycledNode = node;
  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     @Beta
  95     public interface Node {
  96         Set<Edge> getInEdges();
  97
  98         Set<Edge> getOutEdges();
  99     }
 100
 101     /**
 102      * Interface for edges in graph that can be sorted topologically.
 103      */
 104     @Beta
 105     public interface Edge {
 106         Node getFrom();
 107
 108         Node getTo();
 109     }
 110
 111     /**
 112      * Basic Node implementation.
 113      */
 114     @Beta
 115     public static class NodeImpl implements Node {
 116         private final Set<Edge> inEdges;
 117         private final Set<Edge> outEdges;
 118
 119         public NodeImpl() {
 120             inEdges = new HashSet<>();
 121             outEdges = new HashSet<>();
 122         }
 123
 124         @Override
 125         public Set<Edge> getInEdges() {
 126             return inEdges;
 127         }
 128
 129         @Override
 130         public Set<Edge> getOutEdges() {
 131             return outEdges;
 132         }
 133
 134         public void addEdge(final Node to) {
 135             Edge edge = new EdgeImpl(this, to);
 136             outEdges.add(edge);
 137             to.getInEdges().add(edge);
 138         }
 139     }
 140
 141     /**
 142      * Basic Edge implementation.
 143      */
 144     @Beta
 145     public static class EdgeImpl implements Edge {
 146         private final Node from;
 147         private final Node to;
 148
 149         public EdgeImpl(final Node from, final Node to) {
 150             this.from = from;
 151             this.to = to;
 152         }
 153
 154         @Override
 155         public Node getFrom() {
 156             return from;
 157         }
 158
 159         @Override
 160         public Node getTo() {
 161             return to;
 162         }
 163
 164         @Override
 165         public int hashCode() {
 166             final int prime = 31;
 167             int result = 1;
 168             result = prime * result + Objects.hashCode(from);
 169             result = prime * result + Objects.hashCode(to);
 170             return result;
 171         }
 172
 173         @Override
 174         public boolean equals(final Object obj) {
 175             if (this == obj) {
 176                 return true;
 177             }
 178             if (obj == null) {
 179                 return false;
 180             }
 181             if (getClass() != obj.getClass()) {
 182                 return false;
 183             }
 184             EdgeImpl other = (EdgeImpl) obj;
 185             if (from == null) {
 186                 if (other.from != null) {
 187                     return false;
 188                 }
 189             } else if (!from.equals(other.from)) {
 190                 return false;
 191             }
 192             if (to == null) {
 193                 if (other.to != null) {
 194                     return false;
 195                 }
 196             } else if (!to.equals(other.to)) {
 197                 return false;
 198             }
 199             return true;
 200         }
 201     }
 202
 203 }