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