001
002 /*
003 * Copyright (C) 2008-2009 Archie L. Cobbs. All rights reserved.
004 *
005 * $Id: TopologicalSorter.java 195 2011-12-27 21:56:33Z archie.cobbs $
006 */
007
008 package org.dellroad.stuff.graph;
009
010 import java.util.ArrayList;
011 import java.util.Collection;
012 import java.util.Collections;
013 import java.util.Comparator;
014 import java.util.HashMap;
015 import java.util.List;
016 import java.util.Set;
017
018 /**
019 * Topological sorting utility class.
020 */
021 public class TopologicalSorter<E> {
022
023 private final Collection<E> nodes;
024 private final EdgeLister<E> edgeLister;
025 private final Comparator<? super E> tieBreaker;
026
027 private HashMap<E, Boolean> visited;
028 private ArrayList<E> ordering;
029
030 /**
031 * Primary constructor.
032 *
033 * @param nodes partially ordered nodes to be sorted
034 * @param edgeLister provides the edges defining the partial order
035 * @param tieBreaker used to sort nodes that are not otherwise ordered,
036 * or null to tie break based on the original ordering
037 */
038 public TopologicalSorter(Collection<E> nodes, EdgeLister<E> edgeLister, Comparator<? super E> tieBreaker) {
039 this.nodes = nodes;
040 this.edgeLister = edgeLister;
041 if (tieBreaker == null)
042 tieBreaker = getDefaultTieBreaker();
043 this.tieBreaker = tieBreaker;
044 }
045
046 /**
047 * Convenience constructor for when ties should be broken based on the original ordering.
048 *
049 * <p>
050 * Equivalent to:
051 * <blockquote>
052 * {@code TopologicalSorter(nodes, edgeLister, null);}
053 * </blockquote>
054 * </p>
055 */
056 public TopologicalSorter(Collection<E> nodes, EdgeLister<E> edgeLister) {
057 this(nodes, edgeLister, null);
058 }
059
060 /**
061 * Produce a total ordering of the nodes consistent with the partial ordering
062 * implied by the edge lister and tie breaker provided to the constructor.
063 *
064 * <p>
065 * The returned list will have the property that if there is an edge from X to Y,
066 * then X will appear before Y in the list. If there is no edge (or sequence of edges) from X to Y
067 * in either direction, then X will appear before Y if the tie breaker sorts X before Y.
068 * </p>
069 *
070 * <p>
071 * This implementation runs in linear time in the number of nodes in the graph.
072 * </p>
073 *
074 * @return sorted, mutable list of nodes
075 * @throws IllegalArgumentException if the partial ordering relation contains a cycle
076 */
077 public List<E> sort() {
078
079 // Order nodes according to reverse tie breaker ordering
080 ArrayList<E> startList = Collections.list(Collections.enumeration(this.nodes));
081 Collections.sort(startList, getTieBreaker(true));
082
083 // Perform depth-first search through nodes
084 this.visited = new HashMap<E, Boolean>(startList.size());
085 this.ordering = new ArrayList<E>(startList.size());
086 for (E node : startList)
087 visit(node, true);
088
089 // Reverse list
090 Collections.reverse(this.ordering);
091 return this.ordering;
092 }
093
094 /**
095 * Same as {@link #sort sort()} but treats all edges as reversed.
096 *
097 * <p>
098 * The returned list will have the property that if there is an edge from X to Y,
099 * then Y will appear before X in the list. If there is no edge (or sequence of edges) from X to Y
100 * in either direction, then X will appear before Y if the tie breaker sorts X before Y.
101 * </p>
102 *
103 * @return sorted, mutable list of nodes
104 * @throws IllegalArgumentException if the partial ordering relation contains a cycle
105 */
106 public List<E> sortEdgesReversed() {
107
108 // Order nodes according to normal tie breaker ordering
109 ArrayList<E> startList = Collections.list(Collections.enumeration(this.nodes));
110 Collections.sort(startList, getTieBreaker(false));
111
112 // Perform depth-first search through nodes
113 this.visited = new HashMap<E, Boolean>(startList.size());
114 this.ordering = new ArrayList<E>(startList.size());
115 for (E node : startList)
116 visit(node, false);
117
118 // Done
119 return this.ordering;
120 }
121
122 private void visit(E node, boolean reverse) {
123
124 // Have we been here before?
125 Boolean state = this.visited.get(node);
126 if (state != null) {
127 if (!state.booleanValue())
128 throw new IllegalArgumentException("cycle in graph containing " + node);
129 return;
130 }
131 this.visited.put(node, false);
132
133 // Get all destination nodes of all out-edges
134 ArrayList<E> targets = Collections.list(Collections.enumeration(this.edgeLister.getOutEdges(node)));
135
136 // Sort them in reverse desired order and recurse
137 Collections.sort(targets, getTieBreaker(reverse));
138 for (E target : targets)
139 visit(target, reverse);
140
141 // Add this node to list in post-order and mark complete
142 this.ordering.add(node);
143 this.visited.put(node, true);
144 }
145
146 private Comparator<? super E> getDefaultTieBreaker() {
147 final HashMap<E, Integer> orderMap = new HashMap<E, Integer>(this.nodes.size());
148 int posn = 0;
149 for (E node : this.nodes)
150 orderMap.put(node, posn++);
151 return new Comparator<E>() {
152 public int compare(E node1, E node2) {
153 return orderMap.get(node1) - orderMap.get(node2);
154 }
155 };
156 }
157
158 private Comparator<? super E> getTieBreaker(boolean reverse) {
159 if (reverse)
160 return Collections.reverseOrder(this.tieBreaker);
161 return this.tieBreaker;
162 }
163
164 /**
165 * Implemented by classes that can enumerate the outgoing edges from a node in a graph.
166 */
167 public interface EdgeLister<E> {
168
169 /**
170 * Get the set of all nodes X for which there is an edge from {@code node} to X.
171 */
172 Set<E> getOutEdges(E node);
173 }
174 }
175