Topological sort

2 files changed, 237 insertions, 0 deletions

diff --git a/vespajlib/src/main/java/com/yahoo/graph/Traversals.java b/vespajlib/src/main/java/com/yahoo/graph/Traversals.java
new file mode 100644
index 00000000000..8e80d44c44b
--- /dev/null
+++ b/vespajlib/src/main/java/com/yahoo/graph/Traversals.java
@@ -0,0 +1,116 @@
+package com.yahoo.graph;
+
+import java.util.ArrayDeque;
+import java.util.ArrayList;
+import java.util.Collection;
+import java.util.Collections;
+import java.util.Deque;
+import java.util.HashMap;
+import java.util.Iterator;
+import java.util.List;
+import java.util.Map;
+import java.util.function.Function;
+
+import static java.util.Collections.emptyList;
+
+/**
+ * Provides graph traversal algorithms in an ad-hoc manner.
+ *
+ * @author jvenstad / jonmv
+ */
+public class Traversals {
+
+    private Traversals() { }
+
+    /**
+     * Returns an {@link Iterable} over the given nodes with a topological iteration order, per the given child mapper.
+     *
+     * @param nodes An iterable containing all nodes in the graph.
+     * @param children A function mapping a node to its children.
+     * @param <T> The node type.
+     * @return A topologically ordered iterable over the given nodes.
+            */
+    public static <T> Iterable<T> topologically(Iterable<T> nodes, Function<T, Iterable<T>> children) {
+        return () -> new Iterator<T>() {
+
+            Iterator<T> delegate = topological(nodes, children);
+
+            @Override
+            public boolean hasNext() {
+                return delegate.hasNext();
+            }
+
+            @Override
+            public T next() {
+                T next = delegate.next();
+                delegate.remove();
+                return next;
+            }
+        };
+    }
+
+
+    /**
+     * Returns an {@link Iterable} over the given nodes with a topological iteration order, per the given child mapper.
+     *
+     * The {@link Iterator#remove()} method must be called for each returned element in order to proceed to its children.
+     *
+     * @param nodes An iterable containing all nodes in the graph.
+     * @param children A function mapping a node to its children.
+     * @param <T> The node type.
+     * @return A topologically ordered iterable over the given nodes.
+     */
+    public static <T> Iterator<T> topological(Iterable<T> nodes, Function<T, Iterable<T>> children) {
+        Map<T, Long> indegrees = new HashMap<>();
+        for (T node : nodes)
+            for (T child : children.apply(node))
+                indegrees.merge(child, 1L, Long::sum);
+
+        Deque<T> ready = new ArrayDeque<>();
+        for (T node : nodes)
+            if ( ! indegrees.containsKey(node))
+                ready.add(node);
+
+        return new Iterator<T>() {
+
+            T last = null;
+
+            @Override
+            public boolean hasNext() {
+                return ! ready.isEmpty();
+            }
+
+            @Override
+            public T next() {
+                return last = ready.remove();
+            }
+
+            @Override
+            public void remove() {
+                if (last == null)
+                    throw new IllegalStateException();
+
+                for (T child : children.apply(last))
+                    indegrees.compute(child, (__, count) -> {
+                        if (--count == 0)
+                            ready.add(child);
+                        return count;
+                    });
+            }
+        };
+    }
+
+    public static <T> Function<T, Iterable<T>> reversed(Collection<T> nodes, Function<T, Iterable<T>> parents) {
+        Map<T, List<T>> reverse = new HashMap<>();
+        for (T node : nodes)
+            reverse.put(node, new ArrayList<>());
+
+        for (T node : nodes)
+            for (T parent : parents.apply(node))
+                if (reverse.containsKey(parent))
+                    reverse.get(parent).add(node);
+
+        return reverse::get;
+    }
+
+}
diff --git a/vespajlib/src/test/java/com/yahoo/graph/TraversalsTest.java b/vespajlib/src/test/java/com/yahoo/graph/TraversalsTest.java
new file mode 100644
index 00000000000..b1b59c94a4f
--- /dev/null
+++ b/vespajlib/src/test/java/com/yahoo/graph/TraversalsTest.java
@@ -0,0 +1,121 @@
+package com.yahoo.graph;
+
+import org.junit.Test;
+
+import java.util.ArrayList;
+import java.util.Collections;
+import java.util.Iterator;
+import java.util.List;
+
+import static com.yahoo.graph.Traversals.topologically;
+import static com.yahoo.graph.Traversals.topological;
+import static java.util.Arrays.asList;
+import static java.util.Collections.emptyList;
+import static java.util.Collections.singletonList;
+import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertFalse;
+
+/**
+ * @author jvenstad / jonmv
+ */
+public class TraversalsTest {
+
+    @Test
+    public void emptyGraph() {
+        assertFalse(topologically(emptyList(), Collections::singletonList).iterator().hasNext());
+    }
+
+    @Test
+    public void selfCycle() {
+        assertFalse(topologically(singletonList(new Object()), Collections::singletonList).iterator().hasNext());
+    }
+
+    @Test
+    public void singleChildless() {
+        Object single = new Object();
+        Iterator<?> iterator = topologically(singletonList(single), __ -> emptyList()).iterator();
+        assertEquals(single, iterator.next());
+        assertFalse(iterator.hasNext());
+    }
+
+    @Test
+    public void cycle() {
+        Node first = new Node(), second = new Node(first);
+        first.children.add(second);
+        Iterator<?> iterator = topologically(asList(first, second), Node::children).iterator();
+        assertFalse(iterator.hasNext());
+    }
+
+    @Test
+    public void severalChildren() {
+        Node third = new Node(), second = new Node(), first = new Node(second, third);
+        Iterator<?> iterator = topologically(asList(first, second, third), Node::children).iterator();
+        assertEquals(first, iterator.next());
+        assertEquals(second, iterator.next());
+        assertEquals(third, iterator.next());
+        assertFalse(iterator.hasNext());
+    }
+
+    @Test
+    public void severalParents() {
+        Node third = new Node(), second = new Node(third), first = new Node(third);
+        Iterator<?> iterator = topologically(asList(first, second, third), Node::children).iterator();
+        assertEquals(first, iterator.next());
+        assertEquals(second, iterator.next());
+        assertEquals(third, iterator.next());
+        assertFalse(iterator.hasNext());
+    }
+
+    @Test
+    public void someGraph() {
+        Node    sixth = new Node(),
+                fifth = new Node(sixth),
+                fourth = new Node(fifth),
+                third = new Node(sixth, fifth, fourth),
+                second = new Node(),
+                first = new Node(sixth, second);
+        Iterator<?> iterator = topologically(asList(first, second, third, fourth, fifth, sixth), Node::children).iterator();
+        assertEquals(first, iterator.next());
+        assertEquals(third, iterator.next());
+        assertEquals(second, iterator.next());
+        assertEquals(fourth, iterator.next());
+        assertEquals(fifth, iterator.next());
+        assertEquals(sixth, iterator.next());
+        assertFalse(iterator.hasNext());
+    }
+
+    @Test
+    public void someGraphWithCycle() {
+        Node    sixth = new Node(),
+                fifth = new Node(sixth),
+                fourth = new Node(fifth),
+                third = new Node(sixth, fifth, fourth),
+                second = new Node(),
+                first = new Node(sixth, second);
+        sixth.children.add(first);
+        Iterator<?> iterator = topologically(asList(first, second, third, fourth, fifth, sixth), Node::children).iterator();
+        assertEquals(third, iterator.next());
+        assertEquals(fourth, iterator.next());
+        assertEquals(fifth, iterator.next());
+        assertFalse(iterator.hasNext());
+    }
+
+    @Test
+    public void incompleteParent() {
+        Node second = new Node(), first = new Node(second);
+        Iterator<?> iterator = topological(asList(first, second), Node::children);
+        assertEquals(first, iterator.next());
+        assertFalse(iterator.hasNext());
+        iterator.remove();
+        assertEquals(second, iterator.next());
+        assertFalse(iterator.hasNext());
+    }
+
+
+    static class Node {
+        final List<Node> children;
+        Node(Node ... children) { this.children = new ArrayList<>(asList(children)); }
+        List<Node> children() { return children; }
+    }
+
+}