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}