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 */
014package cpw.mods.fml.common.toposort;
015
016import java.util.ArrayList;
017import java.util.Collections;
018import java.util.Comparator;
019import java.util.HashMap;
020import java.util.HashSet;
021import java.util.Iterator;
022import java.util.List;
023import java.util.Map;
024import java.util.NoSuchElementException;
025import java.util.Set;
026import java.util.SortedSet;
027import 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 */
036public 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}