13 files changed, 1279 insertions, 0 deletions

diff --git a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/misc/DFSPathFinder.java b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/misc/DFSPathFinder.java
new file mode 100644
index 00000000..51017b1a
--- /dev/null
+++ b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/misc/DFSPathFinder.java
@@ -0,0 +1,146 @@
+/*******************************************************************************
+ * Copyright (c) 2010-2016, Abel Hegedus and IncQueryLabs Ltd.
+ * 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.base.itc.alg.misc;
+
+import java.util.ArrayList;
+import java.util.Deque;
+import java.util.HashSet;
+import java.util.Iterator;
+import java.util.LinkedList;
+import java.util.List;
+import java.util.Set;
+
+import tools.refinery.viatra.runtime.base.itc.igraph.IGraphDataSource;
+import tools.refinery.viatra.runtime.base.itc.igraph.ITcDataSource;
+import tools.refinery.viatra.runtime.matchers.util.IMemoryView;
+
+/**
+ * A depth-first search implementation of the {@link IGraphPathFinder}.
+ * 
+ * TODO use ITC to filter nodes that must be traversed, instead of checks
+ * 
+ * @author Abel Hegedus
+ * 
+ * @param <V>
+ *            the node type of the graph
+ */
+public class DFSPathFinder<V> implements IGraphPathFinder<V> {
+
+    private IGraphDataSource<V> graph;
+    private ITcDataSource<V> itc;
+
+    public DFSPathFinder(IGraphDataSource<V> graph, ITcDataSource<V> itc) {
+        this.graph = graph;
+        this.itc = itc;
+    }
+
+    @Override
+    public Iterable<Deque<V>> getAllPaths(V sourceNode, V targetNode) {
+        Set<V> endNodes = new HashSet<V>();
+        endNodes.add(targetNode);
+        return getAllPathsToTargets(sourceNode, endNodes);
+    }
+
+    @Override
+    public Iterable<Deque<V>> getAllPathsToTargets(V sourceNode, Set<V> targetNodes) {
+        List<Deque<V>> paths = new ArrayList<Deque<V>>();
+        Deque<V> visited = new LinkedList<V>();
+        Set<V> reachableTargets = new HashSet<V>();
+        for (V targetNode : targetNodes) {
+            if (itc.isReachable(sourceNode, targetNode)) {
+                reachableTargets.add(targetNode);
+            }
+        }
+        if (!reachableTargets.isEmpty()) {
+            return paths;
+        }
+        visited.add(sourceNode);
+        return getPaths(paths, visited, reachableTargets);
+    }
+
+    protected Iterable<Deque<V>> getPaths(List<Deque<V>> paths, Deque<V> visited, Set<V> targetNodes) {
+        IMemoryView<V> nodes = graph.getTargetNodes(visited.getLast());
+        // examine adjacent nodes
+        for (V node : nodes.distinctValues()) {
+            if (visited.contains(node)) {
+                continue;
+            }
+            if (targetNodes.contains(node)) {
+                visited.add(node);
+                // clone visited LinkedList
+                Deque<V> visitedClone = new LinkedList<V>(visited);
+                paths.add(visitedClone);
+                visited.removeLast();
+                break;
+            }
+        }
+
+        // in breadth-first, recursion needs to come after visiting connected nodes
+        for (V node : nodes.distinctValues()) {
+            if (visited.contains(node) || targetNodes.contains(node)) {
+                continue;
+            }
+            boolean canReachTarget = false;
+            for (V target : targetNodes) {
+                if (itc.isReachable(node, target)) {
+                    canReachTarget = true;
+                    break;
+                }
+            }
+            if (canReachTarget) {
+                visited.addLast(node);
+                getPaths(paths, visited, targetNodes);
+                visited.removeLast();
+            }
+        }
+
+        return paths;
+    }
+
+    public String printPaths(List<Deque<V>> paths) {
+        StringBuilder sb = new StringBuilder();
+        for (Deque<V> visited : paths) {
+            sb.append("Path: ");
+            for (V node : visited) {
+                sb.append(node);
+                sb.append(" --> ");
+            }
+            sb.append("\n");
+        }
+        return sb.toString();
+    }
+
+    @Override
+    public Deque<V> getPath(V sourceNode, V targetNode) {
+        // TODO optimize
+        Iterable<Deque<V>> allPaths = getAllPaths(sourceNode, targetNode);
+        Iterator<Deque<V>> pathIterator = allPaths.iterator();
+        return pathIterator.hasNext() ? pathIterator.next() : new LinkedList<V>();
+    }
+
+    @Override
+    public Iterable<Deque<V>> getShortestPaths(V sourceNode, V targetNode) {
+        // TODO optimize
+        Iterable<Deque<V>> allPaths = getAllPaths(sourceNode, targetNode);
+        List<Deque<V>> shortestPaths = new ArrayList<Deque<V>>();
+        int shortestPathLength = -1;
+        for (Deque<V> path : allPaths) {
+            int pathLength = path.size();
+            if (shortestPathLength == -1 || pathLength < shortestPathLength) {
+                shortestPaths.clear();
+                shortestPathLength = pathLength;
+            }
+            if (pathLength == shortestPathLength) {
+                shortestPaths.add(path);
+            }
+        }
+        return shortestPaths;
+    }
+
+}
diff --git a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/misc/Edge.java b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/misc/Edge.java
new file mode 100644
index 00000000..cf68d36a
--- /dev/null
+++ b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/misc/Edge.java
@@ -0,0 +1,38 @@
+/*******************************************************************************
+ * 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.base.itc.alg.misc;
+
+public class Edge<V> {
+    private V source;
+    private V target;
+
+    public Edge(V source, V target) {
+        super();
+        this.source = source;
+        this.target = target;
+    }
+
+    public V getSource() {
+        return source;
+    }
+
+    public void setSource(V source) {
+        this.source = source;
+    }
+
+    public V getTarget() {
+        return target;
+    }
+
+    public void setTarget(V target) {
+        this.target = target;
+    }
+
+}
diff --git a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/misc/GraphHelper.java b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/misc/GraphHelper.java
new file mode 100644
index 00000000..194e979b
--- /dev/null
+++ b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/misc/GraphHelper.java
@@ -0,0 +1,173 @@
+/*******************************************************************************
+ * Copyright (c) 2010-2013, 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.base.itc.alg.misc;
+
+import java.util.ArrayList;
+import java.util.Collection;
+import java.util.HashSet;
+import java.util.List;
+import java.util.Map.Entry;
+import java.util.Set;
+
+import tools.refinery.viatra.runtime.base.itc.graphimpl.Graph;
+import tools.refinery.viatra.runtime.base.itc.igraph.IBiDirectionalGraphDataSource;
+import tools.refinery.viatra.runtime.base.itc.igraph.IGraphDataSource;
+import tools.refinery.viatra.runtime.matchers.util.IMemoryView;
+
+/**
+ * Utility class for graph related operations.
+ * 
+ * @author Tamas Szabo
+ */
+public class GraphHelper {
+
+    private GraphHelper() {/*Utility class constructor*/}
+    
+    /**
+     * Returns the subgraph from the given {@link IBiDirectionalGraphDataSource} which contains the given set of nodes.
+     * 
+     * @param nodesInSubGraph
+     *            the nodes that are present in the subgraph
+     * @param graphDataSource
+     *            the graph data source for the original graph
+     * @return the subgraph associated to the given nodes
+     */
+    public static <V> Graph<V> getSubGraph(Collection<V> nodesInSubGraph,
+            IBiDirectionalGraphDataSource<V> graphDataSource) {
+        Graph<V> g = new Graph<V>();
+        if (nodesInSubGraph != null) {
+            for (V node : nodesInSubGraph) {
+                g.insertNode(node);
+            }
+
+            for (V node : nodesInSubGraph) {
+                IMemoryView<V> sources = graphDataSource.getSourceNodes(node);
+                for (Entry<V, Integer> entry : sources.entriesWithMultiplicities()) {
+                    for (int i = 0; i < entry.getValue(); i++) {
+                        V s = entry.getKey();
+                        if (nodesInSubGraph.contains(s)) {
+                            g.insertEdge(s, node);
+                        }
+                    }
+                }
+            }
+        }
+
+        return g;
+    }
+
+    /**
+     * Constructs a path between source and target in the given graph. Both the {@link IGraphDataSource} and the set of
+     * nodes are used, this way it is possible to construct a path in a given subgraph.
+     * 
+     * The returned {@link List} contains the nodes along the path (this means that there is an edge in the graph
+     * between two consecutive nodes). A self loop (one edge) is indicated with the source node being present two times
+     * in the returned {@link List}.
+     * 
+     * @param source
+     *            the source node
+     * @param target
+     *            the target node
+     * @param nodesInGraph
+     *            the nodes that are present in the subgraph
+     * @param graphDataSource
+     *            the graph data source
+     * @return the path between the two nodes
+     */
+    public static <V> List<V> constructPath(V source, V target, Set<V> nodesInGraph,
+            IGraphDataSource<V> graphDataSource) {
+        Set<V> visitedNodes = new HashSet<V>();
+        List<V> path = new ArrayList<V>();
+
+        visitedNodes.add(source);
+        path.add(source);
+        V act = source;
+
+        // if source and target are the same node
+        if (source.equals(target) && graphDataSource.getTargetNodes(source).containsNonZero(target)) {
+            // the node will be present in the path two times
+            path.add(source);
+            return path;
+        } else {
+            while (act != null) {
+                V nextNode = getNextNodeToVisit(act, graphDataSource, nodesInGraph, visitedNodes);
+                if (nextNode == null && path.size() > 1) {
+                    // needs to backtrack along path
+                    // remove the last element in the path because we can't go
+                    // anywhere from there
+                    path.remove(path.size() - 1);
+                    while (nextNode == null && path.size() > 0) {
+                        V lastPathElement = path.get(path.size() - 1);
+                        nextNode = getNextNodeToVisit(lastPathElement, graphDataSource, nodesInGraph, visitedNodes);
+                        if (nextNode == null) {
+                            path.remove(path.size() - 1);
+                        }
+                    }
+                }
+
+                if (nextNode != null) {
+                    visitedNodes.add(nextNode);
+                    path.add(nextNode);
+                    if (nextNode.equals(target)) {
+                        return path;
+                    }
+                }
+                act = nextNode;
+            }
+            return null;
+        }
+    }
+
+    private static <V> V getNextNodeToVisit(V act, IGraphDataSource<V> graphDataSource, Set<V> nodesInSubGraph,
+            Set<V> visitedNodes) {
+        IMemoryView<V> targetNodes = graphDataSource.getTargetNodes(act);
+        for (Entry<V, Integer> entry : targetNodes.entriesWithMultiplicities()) {
+            for (int i = 0; i < entry.getValue(); i++) {
+                V node = entry.getKey();
+                if (nodesInSubGraph.contains(node) && !visitedNodes.contains(node)) {
+                    return node;
+                }
+            }
+        }
+        return null;
+    }
+
+    /**
+     * Returns the number of self-loop edges for the given node.
+     * 
+     * @param node
+     *            the node
+     * @param graphDataSource
+     *            the graph data source
+     * @return the number of self-loop edges
+     */
+    public static <V> int getEdgeCount(V node, IGraphDataSource<V> graphDataSource) {
+        return getEdgeCount(node, node, graphDataSource);
+    }
+
+    /**
+     * Returns the number of edges between the given source and target nodes.
+     * 
+     * @param source
+     *            the source node
+     * @param target
+     *            the target node
+     * @param graphDataSource
+     *            the graph data source
+     * @return the number of parallel edges between the two nodes
+     */
+    public static <V> int getEdgeCount(V source, V target, IGraphDataSource<V> graphDataSource) {
+        Integer count = graphDataSource.getTargetNodes(source).getCount(target);
+        if (count == null) {
+            return 0;
+        } else {
+            return count;
+        }
+    }
+}
diff --git a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/misc/IGraphPathFinder.java b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/misc/IGraphPathFinder.java
new file mode 100644
index 00000000..cebb09c8
--- /dev/null
+++ b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/misc/IGraphPathFinder.java
@@ -0,0 +1,67 @@
+/*******************************************************************************
+ * Copyright (c) 2010-2013, Abel Hegedus, 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.base.itc.alg.misc;
+
+import java.util.Deque;
+import java.util.Set;
+
+import tools.refinery.viatra.runtime.base.itc.igraph.ITcDataSource;
+
+/**
+ * The path finder provides methods for retrieving paths in a graph between a source node and one or more target nodes.  
+ * Use {@link ITcDataSource#getPathFinder()} for instantiating.
+ * 
+ * @author Abel Hegedus
+ *
+ * @param <V> the node type of the graph
+ */
+public interface IGraphPathFinder<V> {
+
+    /**
+     * Returns an arbitrary path from the source node to the target node (if such exists). If there is no path
+     * between them, an empty collection is returned.
+     * 
+     * @param sourceNode the source node of the path
+     * @param targetNode the target node of the path
+     * @return the path from the source to the target, or empty collection if target is not reachable from source.
+     */
+    Deque<V> getPath(V sourceNode, V targetNode);
+
+    /**
+     * Returns the collection of shortest paths from the source node to the target node (if such exists). If there is no path
+     * between them, an empty collection is returned.
+     * 
+     * @param sourceNode the source node of the path
+     * @param targetNode the target node of the path
+     * @return the collection of shortest paths from the source to the target, or empty collection if target is not reachable from source.
+     */
+    Iterable<Deque<V>> getShortestPaths(V sourceNode, V targetNode);
+    
+    /**
+     * Returns the collection of paths from the source node to the target node (if such exists). If there is no path
+     * between them, an empty collection is returned.
+     * 
+     * @param sourceNode the source node of the path
+     * @param targetNode the target node of the path
+     * @return the collection of paths from the source to the target, or empty collection if target is not reachable from source.
+     */
+    Iterable<Deque<V>> getAllPaths(V sourceNode, V targetNode);
+
+    /**
+     * Returns the collection of paths from the source node to any of the target nodes (if such exists). If there is no path
+     * between them, an empty collection is returned.
+     * 
+     * @param sourceNode the source node of the path
+     * @param targetNodes the set of target nodes of the paths
+     * @return the collection of paths from the source to any of the targets, or empty collection if neither target is reachable from source.
+     */
+    Iterable<Deque<V>> getAllPathsToTargets(V sourceNode, Set<V> targetNodes);
+
+    
+}
\ No newline at end of file
diff --git a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/misc/ITcRelation.java b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/misc/ITcRelation.java
new file mode 100644
index 00000000..a41ff6c7
--- /dev/null
+++ b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/misc/ITcRelation.java
@@ -0,0 +1,31 @@
+/*******************************************************************************
+ * 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.base.itc.alg.misc;
+
+import java.util.Set;
+
+public interface ITcRelation<V> {
+
+    /**
+     * Returns the starting nodes from a transitive closure relation.
+     * 
+     * @return the set of starting nodes
+     */
+    public Set<V> getTupleStarts();
+
+    /**
+     * Returns the set of nodes that are reachable from the given node.
+     * 
+     * @param start
+     *            the starting node
+     * @return the set of reachable nodes
+     */
+    public Set<V> getTupleEnds(V start);
+}
diff --git a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/misc/Tuple.java b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/misc/Tuple.java
new file mode 100644
index 00000000..a2d54a59
--- /dev/null
+++ b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/misc/Tuple.java
@@ -0,0 +1,60 @@
+/*******************************************************************************
+ * 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.base.itc.alg.misc;
+
+public class Tuple<V> {
+
+    private V source;
+    private V target;
+
+    public Tuple(V source, V target) {
+        super();
+        this.source = source;
+        this.target = target;
+    }
+
+    public V getSource() {
+        return source;
+    }
+
+    public void setSource(V source) {
+        this.source = source;
+    }
+
+    public V getTarget() {
+        return target;
+    }
+
+    public void setTarget(V target) {
+        this.target = target;
+    }
+
+    @Override
+    public String toString() {
+        return "(" + source.toString() + "," + target.toString() + ")";
+    }
+
+    @Override
+    public boolean equals(Object o) {
+        if (o instanceof Tuple) {
+            Tuple<?> t = (Tuple<?>) o;
+
+            if (t.getSource().equals(this.source) && t.getTarget().equals(this.target)) {
+                return true;
+            }
+        }
+        return false;
+    }
+
+    @Override
+    public int hashCode() {
+        return source.hashCode() + target.hashCode();
+    }
+}
diff --git a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/misc/bfs/BFS.java b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/misc/bfs/BFS.java
new file mode 100644
index 00000000..798f31d2
--- /dev/null
+++ b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/misc/bfs/BFS.java
@@ -0,0 +1,151 @@
+/*******************************************************************************
+ * 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.base.itc.alg.misc.bfs;
+
+import java.util.ArrayList;
+import java.util.HashSet;
+import java.util.List;
+import java.util.Set;
+
+import tools.refinery.viatra.runtime.base.itc.igraph.IBiDirectionalGraphDataSource;
+import tools.refinery.viatra.runtime.base.itc.igraph.IGraphDataSource;
+
+public class BFS<V> {
+
+    private BFS() {/*Utility class constructor*/}
+    
+    /**
+     * Performs a breadth first search on the given graph to determine whether source is reachable from target.
+     * 
+     * @param <V>
+     *            the type parameter of the nodes in the graph
+     * @param source
+     *            the source node
+     * @param target
+     *            the target node
+     * @param graph
+     *            the graph data source
+     * @return true if source is reachable from target, false otherwise
+     */
+    public static <V> boolean isReachable(V source, V target, IGraphDataSource<V> graph) {
+        List<V> nodeQueue = new ArrayList<V>();
+        Set<V> visited = new HashSet<V>();
+
+        nodeQueue.add(source);
+        visited.add(source);
+
+        boolean ret = _isReachable(target, graph, nodeQueue, visited);
+        return ret;
+    }
+
+    private static <V> boolean _isReachable(V target, IGraphDataSource<V> graph, List<V> nodeQueue, Set<V> visited) {
+
+        while (!nodeQueue.isEmpty()) {
+            V node = nodeQueue.remove(0);
+            for (V t : graph.getTargetNodes(node).distinctValues()){
+                if (t.equals(target)) {
+                    return true;
+                }
+                if (!visited.contains(t)) {
+                    visited.add(t);
+                    nodeQueue.add(t);
+                }
+            }
+        }
+        return false;
+    }
+
+    public static <V> Set<V> reachableSources(IBiDirectionalGraphDataSource<V> graph, V target) {
+        Set<V> retSet = new HashSet<V>();
+        retSet.add(target);
+        List<V> nodeQueue = new ArrayList<V>();
+        nodeQueue.add(target);
+
+        _reachableSources(graph, nodeQueue, retSet);
+
+        return retSet;
+    }
+
+    private static <V> void _reachableSources(IBiDirectionalGraphDataSource<V> graph, List<V> nodeQueue,
+            Set<V> retSet) {
+        while (!nodeQueue.isEmpty()) {
+            V node = nodeQueue.remove(0);
+            for (V _node : graph.getSourceNodes(node).distinctValues()) {
+                if (!retSet.contains(_node)) {
+                    retSet.add(_node);
+                    nodeQueue.add(_node);
+                }
+            }
+        }
+    }
+
+    public static <V> Set<V> reachableTargets(IGraphDataSource<V> graph, V source) {
+        Set<V> retSet = new HashSet<V>();
+        retSet.add(source);
+        List<V> nodeQueue = new ArrayList<V>();
+        nodeQueue.add(source);
+
+        _reachableTargets(graph, nodeQueue, retSet);
+
+        return retSet;
+    }
+
+    private static <V> void _reachableTargets(IGraphDataSource<V> graph, List<V> nodeQueue, Set<V> retSet) {
+        while (!nodeQueue.isEmpty()) {
+            V node = nodeQueue.remove(0);
+
+            for (V _node : graph.getTargetNodes(node).distinctValues()) {
+
+                if (!retSet.contains(_node)) {
+                    retSet.add(_node);
+                    nodeQueue.add(_node);
+                }
+            }
+        }
+    }
+
+    /**
+     * Performs a breadth first search on the given graph and collects all the nodes along the path from source to
+     * target if such path exists.
+     * 
+     * @param <V>
+     *            the type parameter of the nodes in the graph
+     * @param source
+     *            the source node
+     * @param target
+     *            the target node
+     * @param graph
+     *            the graph data source
+     * @return the set of nodes along the path
+     */
+    public static <V> Set<V> collectNodesAlongPath(V source, V target, IGraphDataSource<V> graph) {
+        Set<V> path = new HashSet<V>();
+        _collectNodesAlongPath(source, target, graph, path);
+        return path;
+    }
+
+    private static <V> boolean _collectNodesAlongPath(V node, V target, IGraphDataSource<V> graph, Set<V> path) {
+
+        boolean res = false;
+
+        // end recursion
+        if (node.equals(target)) {
+            path.add(node);
+            return true;
+        } else {
+            for (V _nodeT : graph.getTargetNodes(node).distinctValues()) {
+                res = (_collectNodesAlongPath(_nodeT, target, graph, path)) || res;
+            }
+            if (res)
+                path.add(node);
+            return res;
+        }
+    }
+}
diff --git a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/misc/dfs/DFSAlg.java b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/misc/dfs/DFSAlg.java
new file mode 100644
index 00000000..c8d25c4e
--- /dev/null
+++ b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/misc/dfs/DFSAlg.java
@@ -0,0 +1,93 @@
+/*******************************************************************************
+ * 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.base.itc.alg.misc.dfs;
+
+import java.util.HashMap;
+
+import tools.refinery.viatra.runtime.base.itc.alg.dred.DRedTcRelation;
+import tools.refinery.viatra.runtime.base.itc.igraph.IGraphDataSource;
+import tools.refinery.viatra.runtime.base.itc.igraph.IGraphObserver;
+
+public class DFSAlg<V> implements IGraphObserver<V> {
+
+    private IGraphDataSource<V> gds;
+    private DRedTcRelation<V> tc;
+    private int[] visited;
+    private HashMap<V, Integer> nodeMap;
+
+    public DFSAlg(IGraphDataSource<V> gds) {
+        this.gds = gds;
+        this.tc = new DRedTcRelation<V>();
+        gds.attachObserver(this);
+        deriveTc();
+    }
+
+    private void deriveTc() {
+        tc.clear();
+
+        this.visited = new int[gds.getAllNodes().size()];
+        nodeMap = new HashMap<V, Integer>();
+
+        int j = 0;
+        for (V n : gds.getAllNodes()) {
+            nodeMap.put(n, j);
+            j++;
+        }
+
+        for (V n : gds.getAllNodes()) {
+            oneDFS(n, n);
+            initVisitedArray();
+        }
+    }
+
+    private void initVisitedArray() {
+        for (int i = 0; i < visited.length; i++)
+            visited[i] = 0;
+    }
+
+    private void oneDFS(V act, V source) {
+
+        if (!act.equals(source)) {
+            tc.addTuple(source, act);
+        }
+
+        visited[nodeMap.get(act)] = 1;
+
+        for (V t : gds.getTargetNodes(act).distinctValues()) {
+            if (visited[nodeMap.get(t)] == 0) {
+                oneDFS(t, source);
+            }
+        }
+    }
+
+    public DRedTcRelation<V> getTcRelation() {
+        return this.tc;
+    }
+
+    @Override
+    public void edgeInserted(V source, V target) {
+        deriveTc();
+    }
+
+    @Override
+    public void edgeDeleted(V source, V target) {
+        deriveTc();
+    }
+
+    @Override
+    public void nodeInserted(V n) {
+        deriveTc();
+    }
+
+    @Override
+    public void nodeDeleted(V n) {
+        deriveTc();
+    }
+}
diff --git a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/misc/scc/PKAlg.java b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/misc/scc/PKAlg.java
new file mode 100644
index 00000000..c99a48ab
--- /dev/null
+++ b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/misc/scc/PKAlg.java
@@ -0,0 +1,179 @@
+/*******************************************************************************
+ * 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.base.itc.alg.misc.scc;
+
+import java.util.ArrayList;
+import java.util.Collections;
+import java.util.HashMap;
+import java.util.List;
+import java.util.Map;
+
+import tools.refinery.viatra.runtime.base.itc.igraph.IBiDirectionalGraphDataSource;
+import tools.refinery.viatra.runtime.base.itc.igraph.IBiDirectionalWrapper;
+import tools.refinery.viatra.runtime.base.itc.igraph.IGraphDataSource;
+import tools.refinery.viatra.runtime.base.itc.igraph.IGraphObserver;
+
+public class PKAlg<V> implements IGraphObserver<V> {
+
+    /**
+     * Maps the nodes to their indicies.
+     */
+    private Map<V, Integer> node2index;
+    private Map<Integer, V> index2node;
+    private Map<V, Boolean> node2mark;
+
+    /**
+     * Maps the index of a node to the index in the topsort.
+     */
+    private Map<Integer, Integer> index2topsort;
+    private Map<Integer, Integer> topsort2index;
+
+    /**
+     * Index associated to the inserted nodes (incrementing with every insertion).
+     */
+    private int index;
+
+    /**
+     * Index within the topsort for the target node when edge insertion occurs.
+     */
+    private int lower_bound;
+
+    /**
+     * Index within the topsort for the source node when edge insertion occurs.
+     */
+    private int upper_bound;
+
+    private List<V> RF;
+    private List<V> RB;
+    private IBiDirectionalGraphDataSource<V> gds;
+
+    public PKAlg(IGraphDataSource<V> gds) {
+        if (gds instanceof IBiDirectionalGraphDataSource<?>) {
+            this.gds = (IBiDirectionalGraphDataSource<V>) gds;
+        } else {
+            this.gds = new IBiDirectionalWrapper<V>(gds);
+        }
+
+        node2mark = new HashMap<V, Boolean>();
+        node2index = new HashMap<V, Integer>();
+        index2node = new HashMap<Integer, V>();
+        index2topsort = new HashMap<Integer, Integer>();
+        topsort2index = new HashMap<Integer, Integer>();
+        index = 0;
+
+        gds.attachObserver(this);
+    }
+
+    @Override
+    public void edgeInserted(V source, V target) {
+
+        RF = new ArrayList<V>();
+        RB = new ArrayList<V>();
+
+        lower_bound = index2topsort.get(node2index.get(target));
+        upper_bound = index2topsort.get(node2index.get(source));
+
+        if (lower_bound < upper_bound) {
+            dfsForward(target);
+            dfsBackward(source);
+            reorder();
+        }
+    }
+
+    private List<Integer> getIndicies(List<V> list) {
+        List<Integer> indicies = new ArrayList<Integer>();
+
+        for (V n : list)
+            indicies.add(index2topsort.get(node2index.get(n)));
+
+        return indicies;
+    }
+
+    private void reorder() {
+
+        Collections.reverse(RB);
+
+        // azon csomopontok indexei amelyek sorrendje nem jo
+        List<Integer> L = getIndicies(RF);
+        L.addAll(getIndicies(RB));
+        Collections.sort(L);
+
+        for (int i = 0; i < RB.size(); i++) {
+            index2topsort.put(node2index.get(RB.get(i)), L.get(i));
+            topsort2index.put(L.get(i), node2index.get(RB.get(i)));
+        }
+
+        for (int i = 0; i < RF.size(); i++) {
+            index2topsort.put(node2index.get(RF.get(i)), L.get(i + RB.size()));
+            topsort2index.put(L.get(i + RB.size()), node2index.get(RF.get(i)));
+        }
+    }
+
+    @SuppressWarnings("unused")
+    private List<V> getTopSort() {
+        List<V> topsort = new ArrayList<V>();
+
+        for (int i : topsort2index.values()) {
+            topsort.add(index2node.get(i));
+        }
+
+        return topsort;
+    }
+
+    private void dfsBackward(V node) {
+        node2mark.put(node, true);
+        RB.add(node);
+
+        for (V sn : gds.getSourceNodes(node).distinctValues()) {
+            int top_id = index2topsort.get(node2index.get(sn));
+
+            if (!node2mark.get(sn) && lower_bound < top_id)
+                dfsBackward(sn);
+        }
+    }
+
+    private void dfsForward(V node) {
+        node2mark.put(node, true);
+        RF.add(node);
+
+        for (V tn : gds.getTargetNodes(node).distinctValues()) {
+            int top_id = index2topsort.get(node2index.get(tn));
+
+            if (top_id == upper_bound)
+                System.out.println("!!!Cycle detected!!!");
+            else if (!node2mark.get(tn) && top_id < upper_bound)
+                dfsForward(tn);
+        }
+    }
+
+    @Override
+    public void edgeDeleted(V source, V target) {
+        // Edge deletion does not affect topsort
+    }
+
+    @Override
+    public void nodeInserted(V n) {
+        node2mark.put(n, false);
+        node2index.put(n, index);
+        index2node.put(index, n);
+        index2topsort.put(index, index);
+        topsort2index.put(index, index);
+        index++;
+    }
+
+    @Override
+    public void nodeDeleted(V n) {
+        node2mark.remove(n);
+        int node_id = node2index.remove(n);
+        index2node.remove(node_id);
+        int top_id = index2topsort.remove(node_id);
+        topsort2index.remove(top_id);
+    }
+}
diff --git a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/misc/scc/SCC.java b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/misc/scc/SCC.java
new file mode 100644
index 00000000..8915998b
--- /dev/null
+++ b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/misc/scc/SCC.java
@@ -0,0 +1,146 @@
+/*******************************************************************************
+ * 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.base.itc.alg.misc.scc;
+
+import java.util.HashSet;
+import java.util.Map;
+import java.util.Set;
+import java.util.Stack;
+
+import tools.refinery.viatra.runtime.base.itc.igraph.IGraphDataSource;
+import tools.refinery.viatra.runtime.matchers.util.CollectionsFactory;
+
+/**
+ * Efficient algorithms to compute the Strongly Connected Components in a directed graph.
+ * 
+ * @author Tamas Szabo
+ * 
+ * @param <V>
+ *            the type parameter of the nodes in the graph
+ */
+public class SCC<V> {
+
+    private SCC() {/*Utility class constructor*/}
+    
+    public static long sccId = 0;
+
+    /**
+     * Computes the SCCs for the given graph and returns them as a multiset. (Iterative version of Tarjan's algorithm)
+     * 
+     * @param g
+     *            the directed graph data source
+     * @return the set of SCCs
+     */
+    public static <V> SCCResult<V> computeSCC(IGraphDataSource<V> g) {
+        int index = 0;
+        Set<Set<V>> ret = new HashSet<Set<V>>();
+
+        // stores the lowlink and index information for the given node
+        Map<V, SCCProperty> nodeMap = CollectionsFactory.createMap();
+
+        // stores all target nodes of a given node - the list will be modified
+        Map<V, Set<V>> targetNodeMap = CollectionsFactory.createMap();
+
+        // stores those target nodes for a given node which have not been visited
+        Map<V, Set<V>> notVisitedMap = CollectionsFactory.createMap();
+
+        // stores the nodes during the traversal
+        Stack<V> nodeStack = new Stack<V>();
+
+        // stores the nodes which belong to an scc (there can be many sccs in the stack at the same time)
+        Stack<V> sccStack = new Stack<V>();
+
+        boolean sink = false, finishedTraversal = true;
+
+        // initialize all nodes with 0 index and 0 lowlink
+        Set<V> allNodes = g.getAllNodes();
+        for (V n : allNodes) {
+            nodeMap.put(n, new SCCProperty(0, 0));
+        }
+
+        for (V n : allNodes) {
+            // if the node has not been visited yet
+            if (nodeMap.get(n).getIndex() == 0) {
+                nodeStack.push(n);
+
+                while (!nodeStack.isEmpty()) {
+                    V currentNode = nodeStack.peek();
+                    sink = false;
+                    finishedTraversal = false;
+                    SCCProperty prop = nodeMap.get(currentNode);
+
+                    if (nodeMap.get(currentNode).getIndex() == 0) {
+                        index++;
+                        sccStack.push(currentNode);
+                        prop.setIndex(index);
+                        prop.setLowlink(index);
+
+                        notVisitedMap.put(currentNode, new HashSet<V>());
+
+                        // storing the target nodes of the actual node
+                        if (g.getTargetNodes(currentNode) != null) {
+                            Set<V> targets = g.getTargetNodes(currentNode).distinctValues();
+                            targetNodeMap.put(currentNode, CollectionsFactory.createSet(targets));
+                        }
+                    }
+
+                    if (targetNodeMap.get(currentNode) != null) {
+
+                        // remove node from stack, the exploration of its children has finished
+                        if (targetNodeMap.get(currentNode).size() == 0) {
+                            targetNodeMap.remove(currentNode);
+
+                            nodeStack.pop();
+
+                            for (V targetNode : g.getTargetNodes(currentNode).distinctValues()) {
+                                if (notVisitedMap.get(currentNode).contains(targetNode)) {
+                                    prop.setLowlink(Math.min(prop.getLowlink(), nodeMap.get(targetNode).getLowlink()));
+                                } else if (sccStack.contains(targetNode)) {
+                                    prop.setLowlink(Math.min(prop.getLowlink(), nodeMap.get(targetNode).getIndex()));
+                                }
+                            }
+
+                            finishedTraversal = true;
+                        } else {
+                            V targetNode = targetNodeMap.get(currentNode).iterator().next();
+                            targetNodeMap.get(currentNode).remove(targetNode);
+                            // if the targetNode has not yet been visited push it to the stack
+                            // and mark it in the notVisitedMap
+                            if (nodeMap.get(targetNode).getIndex() == 0) {
+                                notVisitedMap.get(currentNode).add(targetNode);
+                                nodeStack.add(targetNode);
+                            }
+                        }
+                    }
+                    // if currentNode has no target nodes
+                    else {
+                        nodeStack.pop();
+                        sink = true;
+                    }
+
+                    // create scc if node is a sink or an scc has been found
+                    if ((sink || finishedTraversal) && (prop.getLowlink() == prop.getIndex())) {
+                        Set<V> sc = new HashSet<V>();
+                        V targetNode = null;
+
+                        do {
+                            targetNode = sccStack.pop();
+                            sc.add(targetNode);
+                        } while (!targetNode.equals(currentNode));
+
+                        ret.add(sc);
+                    }
+                }
+            }
+        }
+
+        return new SCCResult<V>(ret, g);
+    }
+}
diff --git a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/misc/scc/SCCProperty.java b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/misc/scc/SCCProperty.java
new file mode 100644
index 00000000..b26e3d37
--- /dev/null
+++ b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/misc/scc/SCCProperty.java
@@ -0,0 +1,37 @@
+/*******************************************************************************
+ * 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.base.itc.alg.misc.scc;
+
+public class SCCProperty {
+    private int index;
+    private int lowlink;
+
+    public SCCProperty(int index, int lowlink) {
+        super();
+        this.index = index;
+        this.lowlink = lowlink;
+    }
+
+    public int getIndex() {
+        return index;
+    }
+
+    public void setIndex(int index) {
+        this.index = index;
+    }
+
+    public int getLowlink() {
+        return lowlink;
+    }
+
+    public void setLowlink(int lowlink) {
+        this.lowlink = lowlink;
+    }
+}
diff --git a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/misc/scc/SCCResult.java b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/misc/scc/SCCResult.java
new file mode 100644
index 00000000..fde59d3b
--- /dev/null
+++ b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/misc/scc/SCCResult.java
@@ -0,0 +1,81 @@
+/*******************************************************************************
+ * 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.base.itc.alg.misc.scc;
+
+import java.util.Map.Entry;
+import java.util.Set;
+
+import tools.refinery.viatra.runtime.base.itc.igraph.IGraphDataSource;
+
+public class SCCResult<V> {
+
+    private Set<Set<V>> sccs;
+    private IGraphDataSource<V> gds;
+
+    public SCCResult(Set<Set<V>> sccs, IGraphDataSource<V> gds) {
+        this.sccs = sccs;
+        this.gds = gds;
+    }
+
+    public Set<Set<V>> getSccs() {
+        return sccs;
+    }
+
+    public int getSCCCount() {
+        return sccs.size();
+    }
+
+    public double getAverageNodeCount() {
+        double a = 0;
+
+        for (Set<V> s : sccs) {
+            a += s.size();
+        }
+
+        return a / sccs.size();
+    }
+
+    public double getAverageEdgeCount() {
+        long edgeSum = 0;
+
+        for (Set<V> scc : sccs) {
+            for (V source : scc) {
+                for (Entry<V, Integer> entry : gds.getTargetNodes(source).entriesWithMultiplicities()) {
+                    if (scc.contains(entry.getKey())) {
+                        edgeSum += entry.getValue();
+                    }
+                }
+            }
+        }
+
+        return (double) edgeSum / (double) sccs.size();
+    }
+
+    public int getBiggestSCCSize() {
+        int max = 0;
+
+        for (Set<V> scc : sccs) {
+            if (scc.size() > max)
+                max = scc.size();
+        }
+
+        return max;
+    }
+
+    public long getSumOfSquares() {
+        long sum = 0;
+
+        for (Set<V> scc : sccs) {
+            sum += scc.size() * scc.size();
+        }
+
+        return sum;
+    }
+}
diff --git a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/misc/topsort/TopologicalSorting.java b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/misc/topsort/TopologicalSorting.java
new file mode 100644
index 00000000..dd18e6c8
--- /dev/null
+++ b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/misc/topsort/TopologicalSorting.java
@@ -0,0 +1,77 @@
+/*******************************************************************************
+ * 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.base.itc.alg.misc.topsort;
+
+import java.util.HashSet;
+import java.util.LinkedList;
+import java.util.List;
+import java.util.Set;
+import java.util.Stack;
+
+import tools.refinery.viatra.runtime.base.itc.igraph.IGraphDataSource;
+
+/**
+ * @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 Stack<Pair<T>> dfsStack = new Stack<Pair<T>>();
+
+        for (final T node : gds.getAllNodes()) {
+            if (!visited.contains(node)) {
+                dfsStack.push(new Pair<T>(node, false));                
+            }
+            
+            while (!dfsStack.isEmpty()) {
+                final Pair<T> head = dfsStack.pop();
+                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.push(new Pair<T>(source, true));
+                    
+                    for (final T target : gds.getTargetNodes(source).distinctValues()) {
+                        if (!visited.contains(target)) {
+                            dfsStack.push(new Pair<T>(target, false));
+                        }
+                    }
+                }
+            }
+        }
+
+        return result;
+    }
+}