001 /* 002 * The FML Forge Mod Loader suite. 003 * Copyright (C) 2012 cpw 004 * 005 * This library is free software; you can redistribute it and/or modify it under the terms of the GNU Lesser General Public License as published by the Free 006 * Software Foundation; either version 2.1 of the License, or any later version. 007 * 008 * This library is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR 009 * A PARTICULAR PURPOSE. See the GNU Lesser General Public License for more details. 010 * 011 * You should have received a copy of the GNU Lesser General Public License along with this library; if not, write to the Free Software Foundation, Inc., 51 012 * Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA 013 */ 014 package cpw.mods.fml.common.toposort; 015 016 import java.util.ArrayList; 017 import java.util.Collections; 018 import java.util.Comparator; 019 import java.util.HashMap; 020 import java.util.HashSet; 021 import java.util.Iterator; 022 import java.util.List; 023 import java.util.Map; 024 import java.util.NoSuchElementException; 025 import java.util.Set; 026 import java.util.SortedSet; 027 import java.util.TreeSet; 028 029 /** 030 * Topological sort for mod loading 031 * 032 * Based on a variety of sources, including http://keithschwarz.com/interesting/code/?dir=topological-sort 033 * @author cpw 034 * 035 */ 036 public class TopologicalSort 037 { 038 public static class DirectedGraph<T> implements Iterable<T> 039 { 040 private final Map<T, SortedSet<T>> graph = new HashMap<T, SortedSet<T>>(); 041 private List<T> orderedNodes = new ArrayList<T>(); 042 043 public boolean addNode(T node) 044 { 045 // Ignore nodes already added 046 if (graph.containsKey(node)) 047 { 048 return false; 049 } 050 051 orderedNodes.add(node); 052 graph.put(node, new TreeSet<T>(new Comparator<T>() 053 { 054 public int compare(T o1, T o2) { 055 return orderedNodes.indexOf(o1)-orderedNodes.indexOf(o2); 056 } 057 })); 058 return true; 059 } 060 061 public void addEdge(T from, T to) 062 { 063 if (!(graph.containsKey(from) && graph.containsKey(to))) 064 { 065 throw new NoSuchElementException("Missing nodes from graph"); 066 } 067 068 graph.get(from).add(to); 069 } 070 071 public void removeEdge(T from, T to) 072 { 073 if (!(graph.containsKey(from) && graph.containsKey(to))) 074 { 075 throw new NoSuchElementException("Missing nodes from graph"); 076 } 077 078 graph.get(from).remove(to); 079 } 080 081 public boolean edgeExists(T from, T to) 082 { 083 if (!(graph.containsKey(from) && graph.containsKey(to))) 084 { 085 throw new NoSuchElementException("Missing nodes from graph"); 086 } 087 088 return graph.get(from).contains(to); 089 } 090 091 public Set<T> edgesFrom(T from) 092 { 093 if (!graph.containsKey(from)) 094 { 095 throw new NoSuchElementException("Missing node from graph"); 096 } 097 098 return Collections.unmodifiableSortedSet(graph.get(from)); 099 } 100 @Override 101 public Iterator<T> iterator() 102 { 103 return orderedNodes.iterator(); 104 } 105 106 public int size() 107 { 108 return graph.size(); 109 } 110 111 public boolean isEmpty() 112 { 113 return graph.isEmpty(); 114 } 115 116 @Override 117 public String toString() 118 { 119 return graph.toString(); 120 } 121 } 122 123 /** 124 * Sort the input graph into a topologically sorted list 125 * 126 * Uses the reverse depth first search as outlined in ... 127 * @param graph 128 * @return 129 */ 130 public static <T> List<T> topologicalSort(DirectedGraph<T> graph) 131 { 132 DirectedGraph<T> rGraph = reverse(graph); 133 List<T> sortedResult = new ArrayList<T>(); 134 Set<T> visitedNodes = new HashSet<T>(); 135 // A list of "fully explored" nodes. Leftovers in here indicate cycles in the graph 136 Set<T> expandedNodes = new HashSet<T>(); 137 138 for (T node : rGraph) 139 { 140 explore(node, rGraph, sortedResult, visitedNodes, expandedNodes); 141 } 142 143 return sortedResult; 144 } 145 146 public static <T> DirectedGraph<T> reverse(DirectedGraph<T> graph) 147 { 148 DirectedGraph<T> result = new DirectedGraph<T>(); 149 150 for (T node : graph) 151 { 152 result.addNode(node); 153 } 154 155 for (T from : graph) 156 { 157 for (T to : graph.edgesFrom(from)) 158 { 159 result.addEdge(to, from); 160 } 161 } 162 163 return result; 164 } 165 166 public static <T> void explore(T node, DirectedGraph<T> graph, List<T> sortedResult, Set<T> visitedNodes, Set<T> expandedNodes) 167 { 168 // Have we been here before? 169 if (visitedNodes.contains(node)) 170 { 171 // And have completed this node before 172 if (expandedNodes.contains(node)) 173 { 174 // Then we're fine 175 return; 176 } 177 178 System.out.printf("%s: %s\n%s\n%s\n", node, sortedResult, visitedNodes, expandedNodes); 179 throw new ModSortingException("There was a cycle detected in the input graph, sorting is not possible", node, visitedNodes); 180 } 181 182 // Visit this node 183 visitedNodes.add(node); 184 185 // Recursively explore inbound edges 186 for (T inbound : graph.edgesFrom(node)) 187 { 188 explore(inbound, graph, sortedResult, visitedNodes, expandedNodes); 189 } 190 191 // Add ourselves now 192 sortedResult.add(node); 193 // And mark ourselves as explored 194 expandedNodes.add(node); 195 } 196 }