--- /dev/null
+/*
+ * Copyright (c) 2013 Cisco Systems, Inc. and others. All rights reserved.
+ *
+ * This program and the accompanying materials are made available under the
+ * terms of the Eclipse Public License v1.0 which accompanies this distribution,
+ * and is available at http://www.eclipse.org/legal/epl-v10.html
+ */
+package org.opendaylight.controller.yang.parser.util;
+
+import java.util.List;
+import java.util.Set;
+
+import com.google.common.base.Preconditions;
+import com.google.common.collect.Lists;
+import com.google.common.collect.Sets;
+
+/**
+ * Utility class that provides topological sort
+ */
+public final class TopologicalSort {
+
+ /**
+ * Topological sort of dependent nodes in acyclic graphs.
+ *
+ * @return Sorted {@link List} of {@link Node}s. Order: Nodes with no
+ * dependencies starting.
+ * @throws IllegalStateException
+ * when cycle is present in the graph
+ */
+ public static List<Node> sort(Set<Node> nodes) {
+ List<Node> sortedNodes = Lists.newArrayList();
+
+ Set<Node> dependentNodes = getDependentNodes(nodes);
+
+ while (!dependentNodes.isEmpty()) {
+ Node n = dependentNodes.iterator().next();
+ dependentNodes.remove(n);
+
+ sortedNodes.add(n);
+
+ for (Edge e : n.getInEdges()) {
+ Node m = e.getFrom();
+ m.getOutEdges().remove(e);
+
+ if (m.getOutEdges().isEmpty()) {
+ dependentNodes.add(m);
+ }
+ }
+ }
+
+ detectCycles(nodes);
+
+ return sortedNodes;
+ }
+
+ private static Set<Node> getDependentNodes(Set<Node> nodes) {
+ Set<Node> S = Sets.newHashSet();
+ for (Node n : nodes) {
+ if (n.getOutEdges().size() == 0) {
+ S.add(n);
+ }
+ }
+ return S;
+ }
+
+ private static void detectCycles(Set<Node> nodes) {
+ // Detect cycles
+ boolean cycle = false;
+ Node cycledNode = null;
+
+ for (Node n : nodes) {
+ if (!n.getOutEdges().isEmpty()) {
+ cycle = true;
+ cycledNode = n;
+ break;
+ }
+ }
+ Preconditions.checkState(cycle == false,
+ "Cycle detected in graph around node: " + cycledNode);
+ }
+
+ /**
+ * Interface for nodes in graph that can be sorted topologically
+ */
+ public static interface Node {
+ Set<Edge> getInEdges();
+
+ Set<Edge> getOutEdges();
+ }
+
+ /**
+ * Interface for edges in graph that can be sorted topologically
+ */
+ public static interface Edge {
+ Node getFrom();
+
+ Node getTo();
+ }
+
+ /**
+ * Basic Node implementation.
+ */
+ public static class NodeImpl implements Node {
+ private final Set<Edge> inEdges;
+ private final Set<Edge> outEdges;
+
+ @Override
+ public Set<Edge> getInEdges() {
+ return inEdges;
+ }
+
+ @Override
+ public Set<Edge> getOutEdges() {
+ return outEdges;
+ }
+
+ public void addEdge(Node to) {
+ Edge e = new EdgeImpl(this, to);
+ outEdges.add(e);
+ to.getInEdges().add(e);
+ }
+
+ public NodeImpl() {
+ inEdges = Sets.newHashSet();
+ outEdges = Sets.newHashSet();
+ }
+ }
+
+ /**
+ * Basic Edge implementation
+ */
+ public static class EdgeImpl implements Edge {
+ private final Node from;
+ private final Node to;
+
+ @Override
+ public Node getFrom() {
+ return from;
+ }
+
+ @Override
+ public Node getTo() {
+ return to;
+ }
+
+ public EdgeImpl(Node from, Node to) {
+ this.from = from;
+ this.to = to;
+
+ }
+
+ @Override
+ public int hashCode() {
+ final int prime = 31;
+ int result = 1;
+ result = prime * result + ((from == null) ? 0 : from.hashCode());
+ result = prime * result + ((to == null) ? 0 : to.hashCode());
+ return result;
+ }
+
+ @Override
+ public boolean equals(Object obj) {
+ if (this == obj)
+ return true;
+ if (obj == null)
+ return false;
+ if (getClass() != obj.getClass())
+ return false;
+ EdgeImpl other = (EdgeImpl) obj;
+ if (from == null) {
+ if (other.from != null)
+ return false;
+ } else if (!from.equals(other.from))
+ return false;
+ if (to == null) {
+ if (other.to != null)
+ return false;
+ } else if (!to.equals(other.to))
+ return false;
+ return true;
+ }
+ }
+
+}