Category: algorithm

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 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> 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) { // indegree zero? Or source?
				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

	/**
	 * A node.
	 * 
	 * @param <T>
	 */
	static class Node<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];
				Edge<T> e = new Edge<T>(this, node);
				outEdges.add(e);
				node.inEdges.add(e);
			}

			return this;
		}

		public Node<T> addEquiEdge(final Node<T> node) {
			Edge<T> e = new Edge<T>(this, node);
			equiEdges.add(e);
			// node.equiEdges.add(e);
			node.duplicate = true;
			return this;
		}

		@Override
		public String toString() {
			return String.format("%s:%s", name, value);
		}
	} // Node<T>

	/**
	 * A directed edge.
	 */
	static class Edge<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() {
			// TODO Auto-generated method stub
			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=
	 * "http://benjchristensen.com/2011/10/23/junit-tests-as-inner-classes/"
	 * >"JUnit Tests as Inner Classes"</a>
	 * 
	 * @author jbetancourt
	 * 
	 */
	@RunWith(JUnit4.class)
	public static class GraphSortTest {
		@SuppressWarnings("unchecked")
		private Node<Integer>[] allNodes = new Node[0];

		/**
		 * Sort list with no duplicate nodes.
		 */
		@SuppressWarnings("boxing")
		@Test
		public void should_sort_without_duplicates() {
			uniqueList();
			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() {
			dupeList();
			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));

		}

		@SuppressWarnings("unchecked")
		private void uniqueList() {
			String nodeData = "nine,9;two,2;forty,40;twelve,12;three,3;one,1;";
			String dagData = "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";

			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()]);

		}

		@SuppressWarnings("unchecked")
		private void dupeList() {
			String nodeData = "nine,9;two,2;forty,40;twelve,12;three,3;one,1;twelve2,12";
			String dagData = "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";

			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()]);

		}

		/**
		 * 
		 * @param nodes
		 * @param dagData
		 */
		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(",");

				@SuppressWarnings("unchecked")
				Node<Integer> source = (Node<Integer>) nodes.get(spec[0]);
				@SuppressWarnings("unchecked")
				Node<Integer> sink = (Node<Integer>) nodes.get(spec[1]);

				if (!sink.duplicate || (source.value != sink.value)) {
					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

[/expand]