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 The sorted mods list.
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    }