    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}