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