Source code for blog post "List sorting using topological ordering of a digraph" http://octodecillion.com/blog/sort-using-digraph/

GraphSort.java

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