Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Source code for blog post "List sorting using topological ordering of a digraph" http://octodecillion.com/blog/sort-using-digraph/
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
You can’t perform that action at this time.