1 files changed, 73 insertions, 0 deletions

diff --git a/subprojects/viatra-runtime-rete/src/main/java/tools/refinery/viatra/runtime/rete/itc/alg/misc/topsort/TopologicalSorting.java b/subprojects/viatra-runtime-rete/src/main/java/tools/refinery/viatra/runtime/rete/itc/alg/misc/topsort/TopologicalSorting.java
new file mode 100644
index 00000000..89be6804
--- /dev/null
+++ b/subprojects/viatra-runtime-rete/src/main/java/tools/refinery/viatra/runtime/rete/itc/alg/misc/topsort/TopologicalSorting.java
@@ -0,0 +1,73 @@
+/*******************************************************************************
+ * Copyright (c) 2010-2012, Tamas Szabo, Istvan Rath and Daniel Varro
+ * This program and the accompanying materials are made available under the
+ * terms of the Eclipse Public License v. 2.0 which is available at
+ * http://www.eclipse.org/legal/epl-v20.html.
+ *
+ * SPDX-License-Identifier: EPL-2.0
+ *******************************************************************************/
+
+package tools.refinery.viatra.runtime.rete.itc.alg.misc.topsort;
+
+import tools.refinery.viatra.runtime.rete.itc.igraph.IGraphDataSource;
+
+import java.util.*;
+
+/**
+ * @since 1.6
+ */
+public class TopologicalSorting {
+
+    private TopologicalSorting() {/*Utility class constructor*/}
+
+    private static final class Pair<T> {
+        public T element;
+        public boolean isParent;
+
+        public Pair(final T element, final boolean isParent) {
+            this.element = element;
+            this.isParent = isParent;
+        }
+    }
+
+    /**
+     * Returns a topological ordering for the given graph data source.
+     * Output format: if there is an a -> b (transitive) reachability, then node <code>a</code> will come before node <code>b</code> in the resulting list.
+     *
+     * @param gds the graph data source
+     * @return a topological ordering
+     */
+    public static <T> List<T> compute(final IGraphDataSource<T> gds) {
+        final Set<T> visited = new HashSet<T>();
+        final LinkedList<T> result = new LinkedList<T>();
+        final Deque<Pair<T>> dfsStack = new ArrayDeque<Pair<T>>();
+
+        for (final T node : gds.getAllNodes()) {
+            if (!visited.contains(node)) {
+                dfsStack.addLast(new Pair<T>(node, false));
+            }
+
+            while (!dfsStack.isEmpty()) {
+                final Pair<T> head = dfsStack.removeLast();
+                final T source = head.element;
+
+                if (head.isParent) {
+                    // we have already seen source, push it to the resulting stack
+                    result.addFirst(source);
+                } else {
+                    // first time we see source, continue with its children
+                    visited.add(source);
+                    dfsStack.addLast(new Pair<T>(source, true));
+
+                    for (final T target : gds.getTargetNodes(source).distinctValues()) {
+                        if (!visited.contains(target)) {
+                            dfsStack.addLast(new Pair<T>(target, false));
+                        }
+                    }
+                }
+            }
+        }
+
+        return result;
+    }
+}