Last active
December 10, 2015 12:18
-
-
Save josefbetancourt/4432759 to your computer and use it in GitHub Desktop.
Source code for blog post "List sorting using topological ordering of a digraph" http://octodecillion.com/blog/sort-using-digraph/
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
package com.octodecillion.sort; | |
import static org.hamcrest.core.Is.is; | |
import static org.hamcrest.core.IsEqual.equalTo; | |
import static org.junit.Assert.assertFalse; | |
import static org.junit.Assert.assertThat; | |
import static org.junit.Assert.assertTrue; | |
import java.util.ArrayList; | |
import java.util.Arrays; | |
import java.util.HashMap; | |
import java.util.HashSet; | |
import java.util.Iterator; | |
import java.util.List; | |
import java.util.Map; | |
import java.util.Map.Entry; | |
import java.util.concurrent.ExecutorService; | |
import java.util.concurrent.Executors; | |
import org.junit.Test; | |
import org.junit.runner.RunWith; | |
import org.junit.runners.JUnit4; | |
/** | |
* | |
* Sorting using directed graph embedding based topological ordering. | |
* | |
* @author Josef Betancourt | |
* @since 20120101T1212 | |
* | |
* | |
* Example code based on code created from M. Jessup's * | |
* {@link "http://stackoverflow.com/questions/2739392/sample-directed-graph-and-topological-sort-code"} | |
* Which itself is an implementation of one presented in Wikipedia | |
* article: {@link "http://en.wikipedia.org/wiki/Topological_sort"} | |
* | |
* | |
*/ | |
public class GraphSort { | |
/** | |
* Modification of algorthim presented in Wikipedia article. | |
* | |
* {@link "http://en.wikipedia.org/wiki/Topological_sort"} | |
* | |
* <pre> | |
* L ? Empty list that will contain the sorted elements | |
* S ? Set of all nodes with no incoming edges | |
* while S is non-empty do | |
* remove a node n from S | |
* insert n into L | |
* for each node m with an edge e from n to m do | |
* remove edge e from the graph | |
* if m has no other incoming edges then | |
* insert m into S | |
* if graph has edges then | |
* return error (graph has at least one cycle) | |
* else | |
* return L (a topologically sorted order) | |
* </pre> | |
* | |
* See also: Algorithm presented in "Algorithms", 4th Edition by R. | |
* Sedgewick and K. Wayne. | |
* {@link "http://algs4.cs.princeton.edu/42directed/Topological.java.html"} | |
* * | |
* | |
* @param <T> | |
* @param allNodes | |
* @return sorted list or empty list if not possible | |
* @throws IllegalArgumentException | |
* if graph has cycles | |
*/ | |
public static <T extends Comparable<T>> ArrayList<Node<T>> topoSort( | |
final Node<T>[] allNodes) { | |
ArrayList<Node<T>> workList = new ArrayList<Node<T>>(); | |
HashSet<Node<T>> sinks = new HashSet<Node<T>>(); | |
for (Node<T> n : allNodes) { | |
if (n.inEdges.size() == 0) { | |
sinks.add(n); | |
} | |
} | |
while (!sinks.isEmpty()) { | |
Node<T> nextNode = sinks.iterator().next(); | |
sinks.remove(nextNode); | |
if (nextNode.duplicate) { | |
continue; | |
} | |
workList.add(nextNode); | |
for (Iterator<Edge<T>> it = nextNode.outEdges.iterator(); it | |
.hasNext();) { | |
Edge<T> outNode = it.next(); | |
Node<T> dest = outNode.to; | |
it.remove(); | |
dest.inEdges.remove(outNode); | |
if (dest.inEdges.isEmpty()) { | |
sinks.add(dest); | |
} | |
} | |
} | |
// All edges are removed? If not, we have a cycle. | |
for (Node<T> n : allNodes) { | |
if (!n.inEdges.isEmpty()) { | |
throw new IllegalArgumentException("Cycle present. Node, " | |
+ n.name | |
+ " has inEdges. Topological sort not possible"); | |
} | |
} | |
ArrayList<Node<T>> resultList = new ArrayList<Node<T>>(); | |
for (Node<T> node : workList) { | |
resultList.add(node); | |
if (!node.equiEdges.isEmpty()) { | |
for (Iterator<Edge<T>> iterator = node.equiEdges.iterator(); iterator | |
.hasNext();) { | |
Edge<T> edge = iterator.next(); | |
resultList.add(edge.to); | |
} | |
} | |
} | |
return resultList; | |
} // topoSort | |
/** | |
* | |
* Create the edges of the graph by updating the nodes in the nodes map. | |
* | |
* Almost like "Loop tiling", chunk an array of all the nodes into smaller | |
* blocks and then invokeSlice on each. | |
* | |
* See {@link "http://en.wikipedia.org/wiki/Loop_tiling"} | |
* | |
* @param nodes | |
* @param numThreads | |
*/ | |
public static <T extends Comparable<T>> void createGraph( | |
final Map<String, Node<T>> nodes, final int numThreads) { | |
final String[] arr = nodes.keySet().toArray(new String[1]); | |
ExecutorService pool = Executors.newFixedThreadPool(numThreads); | |
int chunk = nodes.size() / numThreads; | |
int start = 0; | |
int end = ((start + chunk) - 1) + (nodes.size() % numThreads); | |
for (int i = 0; i < (numThreads); i++) { | |
final int fStart = start; | |
final int fEnd = end; | |
Runnable task = new Runnable() { | |
/** */ | |
@Override | |
public void run() { | |
linkSlice(arr, nodes, fStart, fEnd); | |
} | |
}; | |
pool.submit(task); | |
start += chunk; | |
end = (start + chunk); | |
} // end for | |
} // loadNodes | |
/** | |
* | |
* In an array of Nodes, compare a node within a slice of nodes with all | |
* other nodes. | |
* | |
* The slice is bounded by start and end int indexes. | |
* | |
* @param arr | |
* @param nodes | |
* @param start | |
* @param end | |
*/ | |
@SuppressWarnings({ "boxing", "unchecked" }) | |
public static <T extends Comparable<T>> void linkSlice(final String[] arr, | |
final Map<String, Node<T>> nodes, final int start, final int end) { | |
// TODO: implement if the threading issues can be solved. | |
System.out.println(String.format("Thread (%s), [%s,%s]", Thread | |
.currentThread().getId(), start, end)); | |
for (int i = start; i <= end; i++) { | |
Node<T> pivot = nodes.get(arr[i]); | |
for (int j = 0; j < arr.length; j++) { | |
Node<T> other = nodes.get(arr[j]); | |
int compare = ((Comparable<T>) pivot).compareTo((T) other); | |
if (compare == 1) { | |
// | |
} else if (compare == 0) { | |
// | |
} | |
} | |
} | |
} | |
/** | |
* A node. | |
* | |
* @param <T> | |
*/ | |
static class Node<T extends Comparable<T>> { | |
public final String name; | |
public final T value; | |
public final HashSet<Edge<T>> inEdges; | |
public final HashSet<Edge<T>> outEdges; | |
public final HashSet<Edge<T>> equiEdges; | |
public boolean duplicate; | |
public Node(final String name, final T value) { | |
this.name = name; | |
this.value = value; | |
this.duplicate = false; | |
inEdges = new HashSet<Edge<T>>(); | |
outEdges = new HashSet<Edge<T>>(); | |
equiEdges = new HashSet<Edge<T>>(); | |
} | |
public Node<T> addEdge(final Node<T> node) { | |
Edge<T> e = new Edge<T>(this, node); | |
outEdges.add(e); | |
node.inEdges.add(e); | |
return this; | |
} | |
@SuppressWarnings("unchecked") | |
public Node<T> addEdges(final Node<T>... nodes) { | |
for (int i = 0; i < nodes.length; i++) { | |
Node<T> node = nodes[i]; | |
addEdge(node); | |
} | |
return this; | |
} | |
public Node<T> addEquiEdge(final Node<T> node) { | |
Edge<T> e = new Edge<T>(this, node); | |
equiEdges.add(e); | |
node.duplicate = true; | |
return this; | |
} | |
@Override | |
public String toString() { | |
return String.format("%s:%s", name, value); | |
} | |
@SuppressWarnings("unchecked") | |
public int compareTo(final Node<?> n2) { | |
return value.compareTo((T) n2.value); | |
} | |
} // Node<T> | |
/** | |
* A directed edge. | |
*/ | |
static class Edge<T extends Comparable<T>> { | |
public final Node<T> from; | |
public final Node<T> to; | |
public Edge(final Node<T> from, final Node<T> to) { | |
this.from = from; | |
this.to = to; | |
} | |
@Override | |
public boolean equals(final Object obj) { | |
@SuppressWarnings("unchecked") | |
Edge<T> e = (Edge<T>) obj; | |
return (e.from == from) && (e.to == to); | |
} | |
@Override | |
public int hashCode() { | |
return super.hashCode(); | |
} | |
@Override | |
public String toString() { | |
return String.format("%s->%s", from, to); | |
} | |
} // Edge<T> | |
// ==================================================================== | |
// Nested JUnit test. | |
// ==================================================================== | |
/** | |
* | |
* Tests {@link GraphSort}. | |
* | |
* Uses nested JUnit testing approach advocated by Ben J. Christensen in <a | |
* href= | |
* "https://benjchristensen.wordpress.com/2011/10/23/junit-tests-as-inner-classes/" | |
* >"JUnit Tests as Inner Classes"</a> | |
* | |
* @author jbetancourt | |
* | |
*/ | |
@RunWith(JUnit4.class) | |
public static class GraphSortTest { | |
private static final String EDGES_CYCLE = "one,three;one,twelve;twelve,twelve2,one,forty;one,two;one,nine;two,twelve;two,forty;two,three;two,nine;three,nine;three,forty;three,twelve;nine,twelve;nine,forty;twelve,forty;twelve2,forty;forty,nine"; | |
private static final String EDGES_DATA_DUPE_1 = "one,three;one,twelve;twelve,twelve2,one,forty;one,two;one,nine;two,twelve;two,forty;two,three;two,nine;three,nine;three,forty;three,twelve;nine,twelve;nine,forty;twelve,forty;twelve2,forty"; | |
private static final String NODE_DATA_2 = "nine,9;two,2;forty,40;twelve,12;three,3;one,1;twelve2,12"; | |
private static final String EDGES_UNIQUE_1 = "one,three;one,twelve;one,forty;one,two;one,nine;two,twelve;two,forty;two,three;two,nine;three,nine;three,forty;three,twelve;nine,twelve;nine,forty;twelve,forty"; | |
private static final String NODE_DATA_1 = "nine,9;two,2;forty,40;twelve,12;three,3;one,1;"; | |
@SuppressWarnings("unchecked") | |
private Node<Integer>[] allNodes = new Node[0]; | |
/** | |
* | |
*/ | |
@SuppressWarnings("boxing") | |
@Test | |
public void compareLessThan() { | |
Node<Integer> n1 = new Node<Integer>("n1", 1); | |
Node<Integer> n2 = new Node<Integer>("n2", 2); | |
int result = n1.compareTo(n2); | |
assertThat(result, is(equalTo(-1))); | |
} | |
/** | |
* | |
*/ | |
@SuppressWarnings("boxing") | |
@Test | |
public void compareGreaterThan() { | |
Node<Integer> n1 = new Node<Integer>("n1", 20); | |
Node<Integer> n2 = new Node<Integer>("n2", 8); | |
int result = n1.compareTo(n2); | |
assertThat(result, is(equalTo(1))); | |
} | |
/** | |
* | |
*/ | |
@SuppressWarnings("boxing") | |
@Test | |
public void compareEqual() { | |
Node<Integer> n1 = new Node<Integer>("n1", 24); | |
Node<Integer> n2 = new Node<Integer>("n2", 24); | |
int result = n1.compareTo(n2); | |
assertThat(result, is(equalTo(0))); | |
} | |
/** | |
* Sort list with no duplicate nodes. | |
*/ | |
@SuppressWarnings("boxing") | |
@Test | |
public void should_sort_without_duplicates() { | |
createData(NODE_DATA_1, EDGES_UNIQUE_1); | |
ArrayList<Node<Integer>> result = GraphSort.topoSort(allNodes); | |
assertFalse("empty result", result.isEmpty()); | |
assertThat(Integer.valueOf(result.size()), is(equalTo(6))); | |
assertTrue("result not sorted", inOrder(result)); | |
System.out.println("Sort with unique: " | |
+ Arrays.toString(result.toArray())); | |
} | |
/** | |
* Sort list with no duplicate nodes. | |
*/ | |
@SuppressWarnings("boxing") | |
@Test | |
public void should_sort_with_duplicates() { | |
createData(NODE_DATA_2, EDGES_DATA_DUPE_1); | |
ArrayList<Node<Integer>> result = GraphSort.topoSort(allNodes); | |
assertFalse("empty result", result.isEmpty()); | |
System.out.println("Sort with dupes: " | |
+ Arrays.toString(result.toArray())); | |
assertThat(Integer.valueOf(result.size()), is(equalTo(7))); | |
assertTrue("result not sorted", inOrder(result)); | |
} | |
/** | |
* Sort list with no duplicate nodes. | |
*/ | |
@Test(expected = IllegalArgumentException.class) | |
public void should_have_a_cycle() { | |
createData(NODE_DATA_2, EDGES_CYCLE); | |
GraphSort.topoSort(allNodes); | |
} | |
@SuppressWarnings("unchecked") | |
private void createData(final String nodeData, final String dagData) { | |
Map<String, Node<Integer>> nodes = loadNodes(nodeData); | |
loadDag(nodes, dagData); | |
List<Node<Integer>> list = new ArrayList<Node<Integer>>(); | |
for (Entry<String, Node<Integer>> entry : nodes.entrySet()) { | |
list.add(entry.getValue()); | |
} | |
allNodes = list.toArray(new Node[list.size()]); | |
} | |
/** | |
* | |
*/ | |
@Test | |
public void doTasks() { | |
Map<String, Node<Integer>> nodes = loadNodes(NODE_DATA_1); | |
GraphSort.createGraph(nodes, 2); | |
} | |
/** | |
* | |
* @param nodes | |
* @param dagData | |
*/ | |
@SuppressWarnings({ "unchecked" }) | |
private void loadDag(final Map<?, ?> nodes, final String dagData) { | |
String[] dagStrings = dagData.split(";"); | |
for (int i = 0; i < dagStrings.length; i++) { | |
String[] spec = dagStrings[i].split(","); | |
Node<Integer> source = (Node<Integer>) nodes.get(spec[0]); | |
Node<Integer> sink = (Node<Integer>) nodes.get(spec[1]); | |
// if (!sink.duplicate || (source.value != sink.value)) { | |
if (!sink.duplicate | |
|| (((Comparable<Node<?>>) source).compareTo(sink) != 0)) { | |
source.addEdge(sink); | |
} else { | |
source.addEquiEdge(sink); | |
} | |
} | |
} | |
/** | |
* | |
* @param nodeData | |
* @return | |
*/ | |
private Map<String, Node<Integer>> loadNodes(final String nodeData) { | |
Map<String, Node<Integer>> nodeMap = new HashMap<String, Node<Integer>>(); | |
String[] nodeSpec = nodeData.split(";"); | |
for (int i = 0; i < nodeSpec.length; i++) { | |
String[] string = nodeSpec[i].split(","); | |
String name = string[0]; | |
String value = string[1]; | |
@SuppressWarnings("boxing") | |
Node<Integer> node = new Node<Integer>(name, | |
Integer.parseInt(value.trim())); | |
nodeMap.put(name, node); | |
} | |
return nodeMap; | |
} | |
/** | |
* Check that list is sorted. | |
* | |
* @param nodes | |
* @return | |
*/ | |
@SuppressWarnings("boxing") | |
private boolean inOrder(final ArrayList<Node<Integer>> nodes) { | |
boolean result = true; | |
Iterator<Node<Integer>> iterator = nodes.iterator(); | |
Node<Integer> prev = iterator.next(); | |
while (iterator.hasNext()) { | |
Node<Integer> current = iterator.next(); | |
// in order? | |
if (!(current.value >= prev.value)) { | |
result = false; | |
break; | |
} | |
} | |
return result; | |
} | |
} | |
} // End class GraphSort.java |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment