    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}