2 * Copyright (c) 2013 Cisco Systems, Inc. and others. All rights reserved.
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
8 package org.opendaylight.controller.yang.model.parser.util;
10 import java.util.List;
13 import com.google.common.base.Preconditions;
14 import com.google.common.collect.Lists;
15 import com.google.common.collect.Sets;
18 * Utility class that provides topological sort
20 public class TopologicalSort {
23 * Topological sort of dependent nodes in acyclic graphs.
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
30 public static List<Node> sort(Set<Node> nodes) {
31 List<Node> sortedNodes = Lists.newArrayList();
33 Set<Node> dependentNodes = getDependentNodes(nodes);
35 while (!dependentNodes.isEmpty()) {
36 Node n = dependentNodes.iterator().next();
37 dependentNodes.remove(n);
41 for (Edge e : n.getInEdges()) {
43 m.getOutEdges().remove(e);
45 if (m.getOutEdges().isEmpty()) {
46 dependentNodes.add(m);
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) {
66 private static void detectCycles(Set<Node> nodes) {
68 boolean cycle = false;
69 Node cycledNode = null;
71 for (Node n : nodes) {
72 if (!n.getOutEdges().isEmpty()) {
78 Preconditions.checkState(cycle == false,
79 "Cycle detected in graph around node: " + cycledNode);
83 * Interface for nodes in graph that can be sorted topologically
85 public static interface Node {
86 Set<Edge> getInEdges();
88 Set<Edge> getOutEdges();
92 * Interface for edges in graph that can be sorted topologically
94 public static interface Edge {
101 * Basic Node implementation.
103 public static class NodeImpl implements Node {
104 private final Set<Edge> inEdges;
105 private final Set<Edge> outEdges;
108 public Set<Edge> getInEdges() {
113 public Set<Edge> getOutEdges() {
117 public void addEdge(Node to) {
118 Edge e = new EdgeImpl(this, to);
120 to.getInEdges().add(e);
124 inEdges = Sets.newHashSet();
125 outEdges = Sets.newHashSet();
130 * Basic Edge implementation
132 public static class EdgeImpl implements Edge {
133 private final Node from;
134 private final Node to;
137 public Node getFrom() {
142 public Node getTo() {
146 public EdgeImpl(Node from, Node to) {
153 public int hashCode() {
154 final int prime = 31;
156 result = prime * result + ((from == null) ? 0 : from.hashCode());
157 result = prime * result + ((to == null) ? 0 : to.hashCode());
162 public boolean equals(Object obj) {
167 if (getClass() != obj.getClass())
169 EdgeImpl other = (EdgeImpl) obj;
171 if (other.from != null)
173 } else if (!from.equals(other.from))
176 if (other.to != null)
178 } else if (!to.equals(other.to))