33 files changed, 4191 insertions, 0 deletions

diff --git a/subprojects/viatra-runtime-base-itc/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/counting/CountingAlg.java b/subprojects/viatra-runtime-base-itc/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/counting/CountingAlg.java
new file mode 100644
index 00000000..d0367cde
--- /dev/null
+++ b/subprojects/viatra-runtime-base-itc/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/counting/CountingAlg.java
@@ -0,0 +1,226 @@
+/*******************************************************************************
+ * 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.counting;
+
+import java.util.List;
+import java.util.Set;
+
+import tools.refinery.viatra.runtime.base.itc.alg.misc.DFSPathFinder;
+import tools.refinery.viatra.runtime.base.itc.alg.misc.IGraphPathFinder;
+import tools.refinery.viatra.runtime.base.itc.alg.misc.ITcRelation;
+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;
+import tools.refinery.viatra.runtime.base.itc.igraph.ITcDataSource;
+import tools.refinery.viatra.runtime.base.itc.igraph.ITcObserver;
+import tools.refinery.viatra.runtime.matchers.util.CollectionsFactory;
+import tools.refinery.viatra.runtime.matchers.util.IMemoryView;
+
+/**
+ * This class is the optimized implementation of the Counting algorithm.
+ * 
+ * @author Tamas Szabo
+ * 
+ * @param <V>
+ *            the type parameter of the nodes in the graph data source
+ */
+public class CountingAlg<V> implements IGraphObserver<V>, ITcDataSource<V> {
+
+    private CountingTcRelation<V> tc = null;
+    private IBiDirectionalGraphDataSource<V> gds = null;
+    private List<ITcObserver<V>> observers;
+
+    /**
+     * Constructs a new Counting algorithm and initializes the transitive closure relation with the given graph data
+     * source. Attach itself on the graph data source as an observer.
+     * 
+     * @param gds
+     *            the graph data source instance
+     */
+    public CountingAlg(IGraphDataSource<V> gds) {
+
+        if (gds instanceof IBiDirectionalGraphDataSource<?>) {
+            this.gds = (IBiDirectionalGraphDataSource<V>) gds;
+        } else {
+            this.gds = new IBiDirectionalWrapper<V>(gds);
+        }
+
+        observers = CollectionsFactory.<ITcObserver<V>>createObserverList();
+        tc = new CountingTcRelation<V>(true);
+
+        initTc();
+        gds.attachObserver(this);
+    }
+
+    /**
+     * Initializes the transitive closure relation.
+     */
+    private void initTc() {
+        this.setTcRelation(CountingTcRelation.createFrom(gds));
+    }
+
+    @Override
+    public void edgeInserted(V source, V target) {
+        if (!source.equals(target)) {
+            deriveTc(source, target, true);
+        }
+    }
+
+    @Override
+    public void edgeDeleted(V source, V target) {
+        if (!source.equals(target)) {
+            deriveTc(source, target, false);
+        }
+    }
+
+    @Override
+    public void nodeInserted(V n) {
+
+    }
+
+    @Override
+    public void nodeDeleted(V n) {
+        this.tc.deleteTupleEnd(n);
+    }
+
+    /**
+     * Derives the transitive closure relation when an edge is inserted or deleted.
+     * 
+     * @param source
+     *            the source of the edge
+     * @param target
+     *            the target of the edge
+     * @param dCount
+     *            the value is -1 if an edge was deleted and +1 if an edge was inserted
+     */
+    private void deriveTc(V source, V target, boolean isInsertion) {
+
+        // if (dCount == 1 && isReachable(target, source)) {
+        // System.out.println("The graph contains cycle with (" + source + ","+ target + ") edge!");
+        // }
+
+        CountingTcRelation<V> dtc = new CountingTcRelation<V>(false);
+        Set<V> tupEnds = null;
+
+        // 1. d(tc(x,y)) :- d(l(x,y))
+        if (tc.updateTuple(source, target, isInsertion)) {
+            dtc.updateTuple(source, target, true /* deltas implicitly have the same sign as isInsertion*/);
+            notifyTcObservers(source, target, isInsertion);
+        }
+
+        // 2. d(tc(x,y)) :- d(l(x,z)) & tc(z,y)
+        tupEnds = tc.getTupleEnds(target);
+        if (tupEnds != null) {
+            for (V tupEnd : tupEnds) {
+                if (!tupEnd.equals(source)) {
+                    if (tc.updateTuple(source, tupEnd, isInsertion)) {
+                        dtc.updateTuple(source, tupEnd, true /* deltas implicitly have the same sign as isInsertion*/);
+                        notifyTcObservers(source, tupEnd, isInsertion);
+                    }
+                }
+            }
+        }
+
+        // 3. d(tc(x,y)) :- lv(x,z) & d(tc(z,y))
+        CountingTcRelation<V> newTuples = dtc;
+        CountingTcRelation<V> tmp = null;
+        dtc = new CountingTcRelation<V>(false);
+        
+        IMemoryView<V> nodes = null;
+
+        while (!newTuples.isEmpty()) {
+
+            tmp = dtc;
+            dtc = newTuples;
+            newTuples = tmp;
+            newTuples.clear();
+
+            for (V tS : dtc.getTupleStarts()) {
+                nodes = gds.getSourceNodes(tS);
+                for (V nS : nodes.distinctValues()) {
+                    int count = nodes.getCount(nS);
+                    for (int i = 0; i < count; i++) {
+                        tupEnds = dtc.getTupleEnds(tS);
+                        if (tupEnds != null) {
+                            for (V tT : tupEnds) {
+                                if (!nS.equals(tT)) {
+                                    if (tc.updateTuple(nS, tT, isInsertion)) {
+                                        newTuples.updateTuple(nS, tT, true /* deltas implicitly have the same sign as isInsertion*/);
+                                        notifyTcObservers(nS, tT, isInsertion);
+                                    }
+                                }
+                            }
+                        }
+                    }
+                }
+            }
+        }
+
+        // System.out.println(tc);
+    }
+
+    public ITcRelation<V> getTcRelation() {
+        return this.tc;
+    }
+
+    public void setTcRelation(CountingTcRelation<V> tc) {
+        this.tc = tc;
+    }
+
+    @Override
+    public boolean isReachable(V source, V target) {
+        return tc.containsTuple(source, target);
+    }
+
+    @Override
+    public void attachObserver(ITcObserver<V> to) {
+        this.observers.add(to);
+
+    }
+
+    @Override
+    public void detachObserver(ITcObserver<V> to) {
+        this.observers.remove(to);
+    }
+
+    @Override
+    public Set<V> getAllReachableTargets(V source) {
+        return tc.getTupleEnds(source);
+    }
+
+    @Override
+    public Set<V> getAllReachableSources(V target) {
+        return tc.getTupleStarts(target);
+    }
+
+    private void notifyTcObservers(V source, V target, boolean isInsertion) {
+        if (isInsertion) {
+            for (ITcObserver<V> o : observers) {
+                o.tupleInserted(source, target);
+            }
+        } else {
+            for (ITcObserver<V> o : observers) {
+                o.tupleDeleted(source, target);
+            }
+        }
+    }
+
+    @Override
+    public void dispose() {
+        tc.clear();
+        this.gds.detachObserver(this);
+    }
+
+    @Override
+    public IGraphPathFinder<V> getPathFinder() {
+        return new DFSPathFinder<V>(gds, this);
+    }
+}
\ No newline at end of file
diff --git a/subprojects/viatra-runtime-base-itc/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/counting/CountingTcRelation.java b/subprojects/viatra-runtime-base-itc/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/counting/CountingTcRelation.java
new file mode 100644
index 00000000..8f804dfd
--- /dev/null
+++ b/subprojects/viatra-runtime-base-itc/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/counting/CountingTcRelation.java
@@ -0,0 +1,259 @@
+/*******************************************************************************
+ * 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.counting;
+
+import java.util.Collections;
+import java.util.List;
+import java.util.Set;
+
+import tools.refinery.viatra.runtime.base.itc.alg.misc.ITcRelation;
+import tools.refinery.viatra.runtime.base.itc.alg.misc.topsort.TopologicalSorting;
+import tools.refinery.viatra.runtime.base.itc.igraph.IBiDirectionalGraphDataSource;
+import tools.refinery.viatra.runtime.matchers.util.CollectionsFactory;
+import tools.refinery.viatra.runtime.matchers.util.CollectionsFactory.MemoryType;
+import tools.refinery.viatra.runtime.matchers.util.IMemoryView;
+import tools.refinery.viatra.runtime.matchers.util.IMultiLookup;
+import tools.refinery.viatra.runtime.matchers.util.IMultiLookup.ChangeGranularity;
+
+/**
+ * Transitive closure relation implementation for the Counting algorithm.
+ * 
+ * @author Tamas Szabo
+ * 
+ * @param <V>
+ */
+public class CountingTcRelation<V> implements ITcRelation<V> {
+
+    private IMultiLookup<V, V> tuplesForward = null;
+    private IMultiLookup<V, V> tuplesBackward = null;
+
+    protected CountingTcRelation(boolean backwardIndexing) {
+        tuplesForward = CollectionsFactory.createMultiLookup(Object.class, MemoryType.MULTISETS, Object.class);
+        if (backwardIndexing)
+            tuplesBackward = CollectionsFactory.createMultiLookup(Object.class, MemoryType.MULTISETS, Object.class);
+    }
+    
+    protected boolean isEmpty() {
+        return 0 == this.tuplesForward.countKeys();
+    }
+
+    protected void clear() {
+        this.tuplesForward.clear();
+
+        if (tuplesBackward != null) {
+            this.tuplesBackward.clear();
+        }
+    }
+
+    protected void union(CountingTcRelation<V> rA) {
+        IMultiLookup<V, V> rForward = rA.tuplesForward;
+        for (V source : rForward.distinctKeys()) {
+            IMemoryView<V> targetBag = rForward.lookup(source);
+            for (V target : targetBag.distinctValues()) {
+                this.addTuple(source, target, targetBag.getCount(target));
+            }
+        }
+    }
+
+    public int getCount(V source, V target) {
+        IMemoryView<V> bucket = tuplesForward.lookup(source);
+        return bucket == null ? 0 : bucket.getCount(target);
+    }
+
+    /**
+     * Returns true if the tc relation did not contain previously such a tuple that is defined by (source,target), false
+     * otherwise (in this case count is incremented with the given count parameter).
+     * 
+     * @param source
+     *            the source of the tuple
+     * @param target
+     *            the target of the tuple
+     * @param count
+     *            the count of the tuple, must be positive
+     * @return true if the relation did not contain previously the tuple
+     */
+    public boolean addTuple(V source, V target, int count) {
+        if (tuplesBackward != null) {
+            tuplesBackward.addPairPositiveMultiplicity(target, source, count);
+        }
+        
+        ChangeGranularity change = 
+                tuplesForward.addPairPositiveMultiplicity(source, target, count);
+        
+        return change != ChangeGranularity.DUPLICATE;
+    }
+    
+    /**
+     * Derivation count of the tuple  (source,target) is incremented or decremented.
+     * Returns true iff updated to / from zero derivation count.
+     * @since 1.7
+     */
+    public boolean updateTuple(V source, V target, boolean isInsertion) {
+        if (isInsertion) {
+            if (tuplesBackward != null) {
+                tuplesBackward.addPair(target, source);
+            }
+            ChangeGranularity change = 
+                    tuplesForward.addPair(source, target);
+            return change != ChangeGranularity.DUPLICATE;
+        } else {
+            if (tuplesBackward != null) {
+                tuplesBackward.removePair(target, source);
+            }
+            ChangeGranularity change = 
+                    tuplesForward.removePair(source, target);
+            return change != ChangeGranularity.DUPLICATE;
+        }
+    }
+
+    public void deleteTupleEnd(V deleted) {
+        Set<V> sourcesToDelete = CollectionsFactory.createSet();
+        Set<V> targetsToDelete = CollectionsFactory.createSet();
+        
+        for (V target : tuplesForward.lookupOrEmpty(deleted).distinctValues()) {
+            targetsToDelete.add(target);
+        }
+        if (tuplesBackward != null) {
+            for (V source : tuplesBackward.lookupOrEmpty(deleted).distinctValues()) {
+                sourcesToDelete.add(source);
+            }
+        } else {
+            for (V sourceCandidate : tuplesForward.distinctKeys()) {
+                if (tuplesForward.lookupOrEmpty(sourceCandidate).containsNonZero(deleted))
+                    sourcesToDelete.add(sourceCandidate);
+            }
+        }
+        
+        for (V source : sourcesToDelete) {
+            int count = tuplesForward.lookupOrEmpty(source).getCount(deleted);
+            for (int i=0; i< count; ++i) tuplesForward.removePair(source, deleted);
+        }
+        for (V target : targetsToDelete) {
+            int count = tuplesForward.lookupOrEmpty(deleted).getCount(target);
+            for (int i=0; i< count; ++i) tuplesForward.removePair(deleted, target);
+        }
+        
+        if (tuplesBackward != null) {
+            for (V source : sourcesToDelete) {
+                int count = tuplesBackward.lookupOrEmpty(deleted).getCount(source);
+                for (int i=0; i< count; ++i) tuplesBackward.removePair(deleted, source);
+            }
+            for (V target : targetsToDelete) {
+                int count = tuplesBackward.lookupOrEmpty(target).getCount(deleted);
+                for (int i=0; i< count; ++i) tuplesBackward.removePair(target, deleted);
+            }
+        }
+    }
+
+    @Override
+    public String toString() {
+        StringBuilder sb = new StringBuilder("TcRelation = ");
+
+        for (V source : tuplesForward.distinctKeys()) {
+            IMemoryView<V> targets = tuplesForward.lookup(source);
+            for (V target : targets.distinctValues()) {
+                sb.append("{(" + source + "," + target + ")," + targets.getCount(target) + "} ");
+            }
+        }
+        
+        return sb.toString();
+    }
+
+    @Override
+    public Set<V> getTupleEnds(V source) {
+        IMemoryView<V> tupEnds = tuplesForward.lookup(source);
+        if (tupEnds == null)
+            return null;
+        return tupEnds.distinctValues();
+    }
+
+    /**
+     * Returns the set of nodes from which the target node is reachable, if already computed.
+     * 
+     * @param target
+     *            the target node
+     * @return the set of source nodes
+     * @throws UnsupportedOperationException if backwards index not computed
+     */
+    public Set<V> getTupleStarts(V target) {
+        if (tuplesBackward != null) {
+            IMemoryView<V> tupStarts = tuplesBackward.lookup(target);
+            if (tupStarts == null)
+                return null;
+            return tupStarts.distinctValues();
+        } else {
+            throw new UnsupportedOperationException("built without backward indexing");
+        }
+    }
+
+    @Override
+    public Set<V> getTupleStarts() {
+        Set<V> nodes = CollectionsFactory.createSet();
+        for (V s : tuplesForward.distinctKeys()) {
+            nodes.add(s);
+        }
+        return nodes;
+    }
+
+    /**
+     * Returns true if a (source, target) node is present in the transitive closure relation, false otherwise.
+     * 
+     * @param source
+     *            the source node
+     * @param target
+     *            the target node
+     * @return true if tuple is present, false otherwise
+     */
+    public boolean containsTuple(V source, V target) {
+        return tuplesForward.lookupOrEmpty(source).containsNonZero(target);
+    }
+
+    @SuppressWarnings("unchecked")
+    @Override
+    public boolean equals(Object obj) {
+        if (this == obj) {
+            return true;
+        } else if (obj == null || this.getClass() != obj.getClass()) {
+            return false;
+        } else {
+            CountingTcRelation<V> aTR = (CountingTcRelation<V>) obj;
+
+            return tuplesForward.equals(aTR.tuplesForward);
+        }
+    }
+
+    @Override
+    public int hashCode() {
+        return tuplesForward.hashCode();
+    }
+
+    public static <V> CountingTcRelation<V> createFrom(IBiDirectionalGraphDataSource<V> gds) {
+        List<V> topologicalSorting = TopologicalSorting.compute(gds);
+        CountingTcRelation<V> tc = new CountingTcRelation<V>(true);
+        Collections.reverse(topologicalSorting);
+        for (V n : topologicalSorting) {
+            IMemoryView<V> sourceNodes = gds.getSourceNodes(n);
+            Set<V> tupEnds = tc.getTupleEnds(n);
+            for (V s : sourceNodes.distinctValues()) {
+                int count = sourceNodes.getCount(s);
+                for (int i = 0; i < count; i++) {
+                    tc.updateTuple(s, n, true);
+                    if (tupEnds != null) {
+                        for (V t : tupEnds) {
+                            tc.updateTuple(s, t, true);
+                        }
+                    }
+                }
+            }
+        }
+
+        return tc;
+    }
+}
diff --git a/subprojects/viatra-runtime-base-itc/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/dred/DRedAlg.java b/subprojects/viatra-runtime-base-itc/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/dred/DRedAlg.java
new file mode 100644
index 00000000..b92d08bf
--- /dev/null
+++ b/subprojects/viatra-runtime-base-itc/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/dred/DRedAlg.java
@@ -0,0 +1,308 @@
+/*******************************************************************************
+ * 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.dred;
+
+import java.util.ArrayList;
+import java.util.HashMap;
+import java.util.HashSet;
+import java.util.List;
+import java.util.Map;
+import java.util.Map.Entry;
+import java.util.Set;
+
+import tools.refinery.viatra.runtime.base.itc.alg.misc.DFSPathFinder;
+import tools.refinery.viatra.runtime.base.itc.alg.misc.IGraphPathFinder;
+import tools.refinery.viatra.runtime.base.itc.alg.misc.Tuple;
+import tools.refinery.viatra.runtime.base.itc.alg.misc.dfs.DFSAlg;
+import tools.refinery.viatra.runtime.base.itc.igraph.IGraphDataSource;
+import tools.refinery.viatra.runtime.base.itc.igraph.IGraphObserver;
+import tools.refinery.viatra.runtime.base.itc.igraph.ITcDataSource;
+import tools.refinery.viatra.runtime.base.itc.igraph.ITcObserver;
+import tools.refinery.viatra.runtime.matchers.util.IMemoryView;
+
+/**
+ * This class is the optimized implementation of the DRED algorithm.
+ * 
+ * @author Tamas Szabo
+ * 
+ * @param <V>
+ *            the type parameter of the nodes in the graph data source
+ */
+public class DRedAlg<V> implements IGraphObserver<V>, ITcDataSource<V> {
+
+    private IGraphDataSource<V> graphDataSource = null;
+    private DRedTcRelation<V> tc = null;
+    private DRedTcRelation<V> dtc = null;
+    private List<ITcObserver<V>> observers;
+
+    /**
+     * Constructs a new DRED algorithm and initializes the transitive closure relation with the given graph data source.
+     * Attach itself on the graph data source as an observer.
+     * 
+     * @param gds
+     *            the graph data source instance
+     */
+    public DRedAlg(IGraphDataSource<V> gds) {
+        this.observers = new ArrayList<ITcObserver<V>>();
+        this.graphDataSource = gds;
+        this.tc = new DRedTcRelation<V>();
+        this.dtc = new DRedTcRelation<V>();
+        initTc();
+        graphDataSource.attachObserver(this);
+    }
+
+    /**
+     * Constructs a new DRED algorithm and initializes the transitive closure relation with the given relation. Attach
+     * itself on the graph data source as an observer.
+     * 
+     * @param gds
+     *            the graph data source instance
+     * @param tc
+     *            the transitive closure instance
+     */
+    public DRedAlg(IGraphDataSource<V> gds, DRedTcRelation<V> tc) {
+        this.graphDataSource = gds;
+        this.tc = tc;
+        this.dtc = new DRedTcRelation<V>();
+        graphDataSource.attachObserver(this);
+    }
+
+    /**
+     * Initializes the transitive closure relation.
+     */
+    private void initTc() {
+        DFSAlg<V> dfsa = new DFSAlg<V>(this.graphDataSource);
+        this.setTcRelation(dfsa.getTcRelation());
+        this.graphDataSource.detachObserver(dfsa);
+    }
+
+    @Override
+    public void edgeInserted(V source, V target) {
+        if (!source.equals(target)) {
+            Set<V> tupStarts = null;
+            Set<V> tupEnds = null;
+            Set<Tuple<V>> tuples = new HashSet<Tuple<V>>();
+
+            if (!source.equals(target) && tc.addTuple(source, target)) {
+                tuples.add(new Tuple<V>(source, target));
+            }
+
+            // 2. d+(tc(x,y)) :- d+(tc(x,z)) & lv(z,y) Descartes product
+            tupStarts = tc.getTupleStarts(source);
+            tupEnds = tc.getTupleEnds(target);
+
+            for (V s : tupStarts) {
+                for (V t : tupEnds) {
+                    if (!s.equals(t) && tc.addTuple(s, t)) {
+                        tuples.add(new Tuple<V>(s, t));
+                    }
+                }
+            }
+
+            // (s, source) -> (source, target)
+            // tupStarts = tc.getTupleStarts(source);
+            for (V s : tupStarts) {
+                if (!s.equals(target) && tc.addTuple(s, target)) {
+                    tuples.add(new Tuple<V>(s, target));
+                }
+            }
+
+            // (source, target) -> (target, t)
+            // tupEnds = tc.getTupleEnds(target);
+            for (V t : tupEnds) {
+                if (!source.equals(t) && tc.addTuple(source, t)) {
+                    tuples.add(new Tuple<V>(source, t));
+                }
+            }
+
+            notifyTcObservers(tuples, 1);
+        }
+    }
+
+    @Override
+    public void edgeDeleted(V source, V target) {
+        if (!source.equals(target)) {
+
+            // Computing overestimate, Descartes product of A and B sets, where
+            // A: those nodes from which source is reachable
+            // B: those nodes which is reachable from target
+
+            Map<Tuple<V>, Integer> tuples = new HashMap<Tuple<V>, Integer>();
+            Set<V> sources = tc.getTupleStarts(source);
+            Set<V> targets = tc.getTupleEnds(target);
+
+            tc.removeTuple(source, target);
+            tuples.put(new Tuple<V>(source, target), -1);
+
+            for (V s : sources) {
+                for (V t : targets) {
+                    if (!s.equals(t)) {
+                        tc.removeTuple(s, t);
+                        tuples.put(new Tuple<V>(s, t), -1);
+                    }
+                }
+            }
+
+            for (V s : sources) {
+                if (!s.equals(target)) {
+                    tc.removeTuple(s, target);
+                    tuples.put(new Tuple<V>(s, target), -1);
+                }
+            }
+
+            for (V t : targets) {
+                if (!source.equals(t)) {
+                    tc.removeTuple(source, t);
+                    tuples.put(new Tuple<V>(source, t), -1);
+                }
+            }
+
+            // System.out.println("overestimate: "+dtc);
+
+            // Modify overestimate with those tuples that have alternative derivations
+            // 1. q+(tc(x,y)) :- lv(x,y)
+            for (V s : graphDataSource.getAllNodes()) {
+                IMemoryView<V> targetNodes = graphDataSource.getTargetNodes(s);
+                for (Entry<V, Integer> entry : targetNodes.entriesWithMultiplicities()) {
+                    for (int i = 0; i < entry.getValue(); i++) {
+                        V t = entry.getKey();
+                        if (!s.equals(t)) {
+                            tc.addTuple(s, t);
+                            Tuple<V> tuple = new Tuple<V>(s, t);
+                            Integer count = tuples.get(tuple);
+                            if (count != null && count == -1) {
+                                tuples.remove(tuple);
+                            }
+                        }
+                        
+                    }
+                }
+            }
+
+            // 2. q+(tc(x,y)) :- tcv(x,z) & lv(z,y)
+            DRedTcRelation<V> newTups = new DRedTcRelation<V>();
+            dtc.clear();
+            dtc.union(tc);
+
+            while (!dtc.isEmpty()) {
+
+                newTups.clear();
+                newTups.union(dtc);
+                dtc.clear();
+
+                for (V s : newTups.getTupleStarts()) {
+                    for (V t : newTups.getTupleEnds(s)) {
+                        IMemoryView<V> targetNodes = graphDataSource.getTargetNodes(t);
+                        if (targetNodes != null) {
+                            for (Entry<V, Integer> entry : targetNodes.entriesWithMultiplicities()) {
+                                for (int i = 0; i < entry.getValue(); i++) {
+                                    V tn = entry.getKey();
+                                    if (!s.equals(tn) && tc.addTuple(s, tn)) {
+                                        dtc.addTuple(s, tn);
+                                        tuples.remove(new Tuple<V>(s, tn));
+                                    }
+                                }
+                            }
+                        }
+                    }
+                }
+            }
+
+            notifyTcObservers(tuples.keySet(), -1);
+        }
+    }
+
+    @Override
+    public void nodeInserted(V n) {
+        // Node inserted does not result new tc tuple.
+    }
+
+    @Override
+    public void nodeDeleted(V n) {
+        // FIXME node deletion may involve the deletion of incoming and outgoing edges too
+        Set<V> set = tc.getTupleEnds(n);
+        Set<V> modSet = null;
+
+        // n -> target
+        modSet = new HashSet<V>(set);
+
+        for (V tn : modSet) {
+            this.tc.removeTuple(n, tn);
+        }
+
+        // source -> n
+        set = tc.getTupleStarts(n);
+
+        modSet = new HashSet<V>(set);
+
+        for (V sn : modSet) {
+            this.tc.removeTuple(sn, n);
+        }
+    }
+
+    public DRedTcRelation<V> getTcRelation() {
+        return this.tc;
+    }
+
+    public void setTcRelation(DRedTcRelation<V> tc) {
+        this.tc = tc;
+    }
+
+    @Override
+    public boolean isReachable(V source, V target) {
+        return tc.containsTuple(source, target);
+    }
+
+    @Override
+    public void attachObserver(ITcObserver<V> to) {
+        this.observers.add(to);
+    }
+
+    @Override
+    public void detachObserver(ITcObserver<V> to) {
+        this.observers.remove(to);
+    }
+
+    @Override
+    public Set<V> getAllReachableTargets(V source) {
+        return tc.getTupleEnds(source);
+    }
+
+    @Override
+    public Set<V> getAllReachableSources(V target) {
+        return tc.getTupleStarts(target);
+    }
+
+    protected void notifyTcObservers(Set<Tuple<V>> tuples, int dir) {
+        for (ITcObserver<V> o : observers) {
+            for (Tuple<V> t : tuples) {
+                if (!t.getSource().equals(t.getTarget())) {
+                    if (dir == 1) {
+                        o.tupleInserted(t.getSource(), t.getTarget());
+                    }
+                    if (dir == -1) {
+                        o.tupleDeleted(t.getSource(), t.getTarget());
+                    }
+                }
+            }
+        }
+    }
+
+    @Override
+    public void dispose() {
+        tc = null;
+        dtc = null;
+    }
+
+    @Override
+    public IGraphPathFinder<V> getPathFinder() {
+        return new DFSPathFinder<V>(graphDataSource, this);
+    }
+}
diff --git a/subprojects/viatra-runtime-base-itc/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/dred/DRedTcRelation.java b/subprojects/viatra-runtime-base-itc/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/dred/DRedTcRelation.java
new file mode 100644
index 00000000..8543b79c
--- /dev/null
+++ b/subprojects/viatra-runtime-base-itc/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/dred/DRedTcRelation.java
@@ -0,0 +1,223 @@
+/*******************************************************************************
+ * 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.dred;
+
+import java.util.HashMap;
+import java.util.HashSet;
+import java.util.Map;
+import java.util.Map.Entry;
+import java.util.Set;
+
+import tools.refinery.viatra.runtime.base.itc.alg.misc.ITcRelation;
+
+public class DRedTcRelation<V> implements ITcRelation<V> {
+
+    // tc(a,b) means that b is transitively reachable from a
+    private Map<V, Set<V>> tuplesForward;
+
+    // data structure to efficiently get those nodes from which a given node is reachable
+    // symmetric to tuplesForward
+    private Map<V, Set<V>> tuplesBackward;
+
+    public DRedTcRelation() {
+        this.tuplesForward = new HashMap<V, Set<V>>();
+        this.tuplesBackward = new HashMap<V, Set<V>>();
+    }
+
+    public void clear() {
+        this.tuplesForward.clear();
+        this.tuplesBackward.clear();
+    }
+
+    public boolean isEmpty() {
+        return tuplesForward.isEmpty();
+    }
+
+    public void removeTuple(V source, V target) {
+
+        // removing tuple from 'forward' tc relation
+        Set<V> sSet = tuplesForward.get(source);
+        if (sSet != null) {
+            sSet.remove(target);
+            if (sSet.size() == 0)
+                tuplesForward.remove(source);
+        }
+
+        // removing tuple from 'backward' tc relation
+        Set<V> tSet = tuplesBackward.get(target);
+        if (tSet != null) {
+            tSet.remove(source);
+            if (tSet.size() == 0)
+                tuplesBackward.remove(target);
+        }
+    }
+
+    /**
+     * Returns true if the tc relation did not contain previously such a tuple that is defined by (source,target), false
+     * otherwise.
+     * 
+     * @param source
+     *            the source of the tuple
+     * @param target
+     *            the target of the tuple
+     * @return true if the relation did not contain previously the tuple
+     */
+    public boolean addTuple(V source, V target) {
+
+        // symmetric modification, it is sufficient to check the return value in one collection
+        // adding tuple to 'forward' tc relation
+        Set<V> sSet = tuplesForward.get(source);
+        if (sSet == null) {
+            Set<V> newSet = new HashSet<V>();
+            newSet.add(target);
+            tuplesForward.put(source, newSet);
+        } else {
+            sSet.add(target);
+        }
+
+        // adding tuple to 'backward' tc relation
+        Set<V> tSet = tuplesBackward.get(target);
+        if (tSet == null) {
+            Set<V> newSet = new HashSet<V>();
+            newSet.add(source);
+            tuplesBackward.put(target, newSet);
+            return true;
+        } else {
+            boolean ret = tSet.add(source);
+            return ret;
+        }
+
+    }
+
+    /**
+     * Union operation of two tc realtions.
+     * 
+     * @param rA
+     *            the other tc relation
+     */
+    public void union(DRedTcRelation<V> rA) {
+        for (V source : rA.tuplesForward.keySet()) {
+            for (V target : rA.tuplesForward.get(source)) {
+                this.addTuple(source, target);
+            }
+        }
+    }
+
+    /**
+     * Computes the difference of this tc relation and the given rA parameter.
+     * 
+     * @param rA
+     *            the subtrahend relation
+     */
+    public void difference(DRedTcRelation<V> rA) {
+        for (V source : rA.tuplesForward.keySet()) {
+            for (V target : rA.tuplesForward.get(source)) {
+                this.removeTuple(source, target);
+            }
+        }
+    }
+
+    @Override
+    public Set<V> getTupleEnds(V source) {
+        Set<V> t = tuplesForward.get(source);
+        return (t == null) ? new HashSet<V>() : new HashSet<V>(t);
+    }
+
+    /**
+     * Returns the set of nodes from which the target node is reachable.
+     * 
+     * @param target
+     *            the target node
+     * @return the set of source nodes
+     */
+    public Set<V> getTupleStarts(V target) {
+        Set<V> t = tuplesBackward.get(target);
+        return (t == null) ? new HashSet<V>() : new HashSet<V>(t);
+    }
+
+    @Override
+    public Set<V> getTupleStarts() {
+        Set<V> t = tuplesForward.keySet();
+        return new HashSet<V>(t);
+    }
+
+    @Override
+    public String toString() {
+        StringBuilder sb = new StringBuilder("TcRelation = ");
+
+        for (Entry<V, Set<V>> entry : this.tuplesForward.entrySet()) {
+            V source = entry.getKey();
+            for (V target : entry.getValue()) {
+                sb.append("(" + source + "," + target + ") ");
+            }
+        }
+        return sb.toString();
+    }
+
+    /**
+     * Returns true if a (source, target) node is present in the transitive closure relation, false otherwise.
+     * 
+     * @param source
+     *            the source node
+     * @param target
+     *            the target node
+     * @return true if tuple is present, false otherwise
+     */
+    public boolean containsTuple(V source, V target) {
+        if (tuplesForward.containsKey(source)) {
+            if (tuplesForward.get(source).contains(target))
+                return true;
+        }
+        return false;
+    }
+
+    @SuppressWarnings("unchecked")
+    @Override
+    public boolean equals(Object obj) {
+        if (this == obj) {
+            return true;
+        }
+        if ((obj == null) || (obj.getClass() != this.getClass())) {
+            return false;
+        }
+
+        DRedTcRelation<V> aTR = (DRedTcRelation<V>) obj;
+
+        for (Entry<V, Set<V>> entry : aTR.tuplesForward.entrySet()) {
+            V source = entry.getKey();
+            for (V target : entry.getValue()) {
+                if (!this.containsTuple(source, target))
+                    return false;
+            }
+        }
+
+        for (Entry<V, Set<V>> entry : this.tuplesForward.entrySet()) {
+            V source = entry.getKey();
+            for (V target : entry.getValue()) {
+                if (!aTR.containsTuple(source, target))
+                    return false;
+            }
+        }
+
+        return true;
+    }
+
+    @Override
+    public int hashCode() {
+        int hash = 7;
+        hash = 31 * hash + tuplesForward.hashCode();
+        hash = 31 * hash + tuplesBackward.hashCode();
+        return hash;
+    }
+
+    public Map<V, Set<V>> getTuplesForward() {
+        return tuplesForward;
+    }
+}
diff --git a/subprojects/viatra-runtime-base-itc/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/fw/FloydWarshallAlg.java b/subprojects/viatra-runtime-base-itc/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/fw/FloydWarshallAlg.java
new file mode 100644
index 00000000..b369f1a1
--- /dev/null
+++ b/subprojects/viatra-runtime-base-itc/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/fw/FloydWarshallAlg.java
@@ -0,0 +1,110 @@
+/*******************************************************************************
+ * 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.fw;
+
+import java.util.HashMap;
+import java.util.Map;
+
+import tools.refinery.viatra.runtime.base.itc.alg.dred.DRedTcRelation;
+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;
+import tools.refinery.viatra.runtime.matchers.util.IMemoryView;
+
+public class FloydWarshallAlg<V> implements IGraphObserver<V> {
+
+    private DRedTcRelation<V> tc = null;
+    private IBiDirectionalGraphDataSource<V> gds = null;
+
+    public FloydWarshallAlg(IGraphDataSource<V> gds) {
+        if (gds instanceof IBiDirectionalGraphDataSource<?>) {
+            this.gds = (IBiDirectionalGraphDataSource<V>) gds;
+        } else {
+            this.gds = new IBiDirectionalWrapper<V>(gds);
+        }
+
+        this.tc = new DRedTcRelation<V>();
+        gds.attachObserver(this);
+        generateTc();
+    }
+
+    private void generateTc() {
+
+        tc.clear();
+
+        int n = gds.getAllNodes().size();
+        Map<V, Integer> mapForw = new HashMap<V, Integer>();
+        Map<Integer, V> mapBackw = new HashMap<Integer, V>();
+        int[][] P = new int[n][n];
+
+        int i, j, k;
+
+        // initialize adjacent matrix
+        for (i = 0; i < n; i++) {
+            for (j = 0; j < n; j++) {
+                P[i][j] = 0;
+            }
+        }
+
+        i = 0;
+        for (V node : gds.getAllNodes()) {
+            mapForw.put(node, i);
+            mapBackw.put(i, node);
+            i++;
+        }
+
+        for (V source : gds.getAllNodes()) {
+            IMemoryView<V> targets = gds.getTargetNodes(source);
+            for (V target : targets.distinctValues()) {
+                P[mapForw.get(source)][mapForw.get(target)] = 1;
+            }
+        }
+
+        for (k = 0; k < n; k++) {
+            for (i = 0; i < n; i++) {
+                for (j = 0; j < n; j++) {
+                    P[i][j] = P[i][j] | (P[i][k] & P[k][j]);
+                }
+            }
+        }
+
+        for (i = 0; i < n; i++) {
+            for (j = 0; j < n; j++) {
+                if (P[i][j] == 1 && i != j)
+                    tc.addTuple(mapBackw.get(i), mapBackw.get(j));
+            }
+        }
+    }
+
+    @Override
+    public void edgeInserted(V source, V target) {
+        generateTc();
+    }
+
+    @Override
+    public void edgeDeleted(V source, V target) {
+        generateTc();
+    }
+
+    @Override
+    public void nodeInserted(V n) {
+        generateTc();
+    }
+
+    @Override
+    public void nodeDeleted(V n) {
+        generateTc();
+    }
+
+    public DRedTcRelation<V> getTcRelation() {
+        return this.tc;
+    }
+}
diff --git a/subprojects/viatra-runtime-base-itc/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/incscc/CountingListener.java b/subprojects/viatra-runtime-base-itc/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/incscc/CountingListener.java
new file mode 100644
index 00000000..fdf64f77
--- /dev/null
+++ b/subprojects/viatra-runtime-base-itc/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/incscc/CountingListener.java
@@ -0,0 +1,36 @@
+/*******************************************************************************
+ * 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.incscc;
+
+import tools.refinery.viatra.runtime.base.itc.igraph.ITcObserver;
+import tools.refinery.viatra.runtime.matchers.util.Direction;
+
+/**
+ * @author Tamas Szabo
+ * 
+ */
+public class CountingListener<V> implements ITcObserver<V> {
+
+    private IncSCCAlg<V> alg;
+
+    public CountingListener(IncSCCAlg<V> alg) {
+        this.alg = alg;
+    }
+
+    @Override
+    public void tupleInserted(V source, V target) {
+        alg.notifyTcObservers(alg.sccs.getPartition(source), alg.sccs.getPartition(target), Direction.INSERT);
+    }
+
+    @Override
+    public void tupleDeleted(V source, V target) {
+        alg.notifyTcObservers(alg.sccs.getPartition(source), alg.sccs.getPartition(target), Direction.DELETE);
+    }
+
+}
\ No newline at end of file
diff --git a/subprojects/viatra-runtime-base-itc/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/incscc/IncSCCAlg.java b/subprojects/viatra-runtime-base-itc/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/incscc/IncSCCAlg.java
new file mode 100644
index 00000000..f1e0ad44
--- /dev/null
+++ b/subprojects/viatra-runtime-base-itc/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/incscc/IncSCCAlg.java
@@ -0,0 +1,645 @@
+/*******************************************************************************
+ * 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.incscc;
+
+import java.util.ArrayList;
+import java.util.HashSet;
+import java.util.Iterator;
+import java.util.List;
+import java.util.Map;
+import java.util.Map.Entry;
+import java.util.Objects;
+import java.util.Set;
+
+import tools.refinery.viatra.runtime.base.itc.alg.counting.CountingAlg;
+import tools.refinery.viatra.runtime.base.itc.alg.dred.DRedTcRelation;
+import tools.refinery.viatra.runtime.base.itc.alg.misc.DFSPathFinder;
+import tools.refinery.viatra.runtime.base.itc.alg.misc.GraphHelper;
+import tools.refinery.viatra.runtime.base.itc.alg.misc.IGraphPathFinder;
+import tools.refinery.viatra.runtime.base.itc.alg.misc.Tuple;
+import tools.refinery.viatra.runtime.base.itc.alg.misc.bfs.BFS;
+import tools.refinery.viatra.runtime.base.itc.alg.misc.scc.SCC;
+import tools.refinery.viatra.runtime.base.itc.alg.misc.scc.SCCResult;
+import tools.refinery.viatra.runtime.base.itc.alg.util.CollectionHelper;
+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.IBiDirectionalWrapper;
+import tools.refinery.viatra.runtime.base.itc.igraph.IGraphDataSource;
+import tools.refinery.viatra.runtime.base.itc.igraph.IGraphObserver;
+import tools.refinery.viatra.runtime.base.itc.igraph.ITcDataSource;
+import tools.refinery.viatra.runtime.base.itc.igraph.ITcObserver;
+import tools.refinery.viatra.runtime.matchers.algorithms.UnionFind;
+import tools.refinery.viatra.runtime.matchers.util.CollectionsFactory;
+import tools.refinery.viatra.runtime.matchers.util.Direction;
+import tools.refinery.viatra.runtime.matchers.util.IMemoryView;
+
+/**
+ * Incremental SCC maintenance + counting algorithm.
+ * 
+ * @author Tamas Szabo
+ * 
+ * @param <V>
+ *            the type parameter of the nodes in the graph data source
+ */
+public class IncSCCAlg<V> implements IGraphObserver<V>, ITcDataSource<V> {
+
+    public UnionFind<V> sccs;
+    public IBiDirectionalGraphDataSource<V> gds;
+    private CountingAlg<V> counting;
+    private Graph<V> reducedGraph;
+    private IBiDirectionalGraphDataSource<V> reducedGraphIndexer;
+    private List<ITcObserver<V>> observers;
+    private CountingListener<V> countingListener;
+
+    public IncSCCAlg(IGraphDataSource<V> graphDataSource) {
+
+        if (graphDataSource instanceof IBiDirectionalGraphDataSource<?>) {
+            gds = (IBiDirectionalGraphDataSource<V>) graphDataSource;
+        } else {
+            gds = new IBiDirectionalWrapper<V>(graphDataSource);
+        }
+        observers = CollectionsFactory.createObserverList();
+        sccs = new UnionFind<V>();
+        reducedGraph = new Graph<V>();
+        reducedGraphIndexer = new IBiDirectionalWrapper<V>(reducedGraph);
+        countingListener = new CountingListener<V>(this);
+        initalizeInternalDataStructures();
+        gds.attachObserver(this);
+    }
+
+    private void initalizeInternalDataStructures() {
+        SCCResult<V> _sccres = SCC.computeSCC(gds);
+        Set<Set<V>> _sccs = _sccres.getSccs();
+
+        for (Set<V> _set : _sccs) {
+            sccs.makeSet(_set);
+        }
+
+        // Initalization of the reduced graph
+        for (V n : sccs.getPartitionHeads()) {
+            reducedGraph.insertNode(n);
+        }
+
+        for (V source : gds.getAllNodes()) {
+            final IMemoryView<V> targetNodes = gds.getTargetNodes(source);
+            for (Entry<V, Integer> entry : targetNodes.entriesWithMultiplicities()) {
+                for (int i = 0; i < entry.getValue(); i++) {
+                    V target = entry.getKey();
+                    V sourceRoot = sccs.find(source);
+                    V targetRoot = sccs.find(target);
+
+                    if (!sourceRoot.equals(targetRoot)) {
+                        reducedGraph.insertEdge(sourceRoot, targetRoot);
+                    }
+                }
+            }
+        }
+
+        counting = new CountingAlg<V>(reducedGraph);
+    }
+
+    @Override
+    public void edgeInserted(V source, V target) {
+        V sourceRoot = sccs.find(source);
+        V targetRoot = sccs.find(target);
+
+        // Different SCC
+        if (!sourceRoot.equals(targetRoot)) {
+
+            // source is reachable from target?
+            if (counting.isReachable(targetRoot, sourceRoot)) {
+
+                Set<V> predecessorRoots = counting.getAllReachableSources(sourceRoot);
+                Set<V> successorRoots = counting.getAllReachableTargets(targetRoot);
+
+                // 1. intersection of source and target roots, these will be in the merged SCC
+                Set<V> isectRoots = CollectionHelper.intersection(predecessorRoots, successorRoots);
+                isectRoots.add(sourceRoot);
+                isectRoots.add(targetRoot);
+
+                // notifications must be issued before Union-Find modifications
+                if (observers.size() > 0) {
+                    Set<V> sourceSCCs = createSetNullTolerant(predecessorRoots);
+                    sourceSCCs.add(sourceRoot);
+                    Set<V> targetSCCs = createSetNullTolerant(successorRoots);
+                    targetSCCs.add(targetRoot);
+
+                    // tracing back to actual nodes
+                    for (V sourceSCC : sourceSCCs) {
+                        targetLoop: for (V targetSCC : targetSCCs) {
+                            if (counting.isReachable(sourceSCC, targetSCC)) continue targetLoop;
+                            
+                            boolean needsNotification = 
+                                // Case 1. sourceSCC and targetSCC are the same and it is a one sized scc.
+                                // Issue notifications only if there is no self-loop present at the moment
+                                (sourceSCC.equals(targetSCC) && sccs.getPartition(sourceSCC).size() == 1 && GraphHelper
+                                        .getEdgeCount(sccs.getPartition(sourceSCC).iterator().next(), gds) == 0)
+                                ||
+                                // Case 2. sourceSCC and targetSCC are different sccs.
+                                (!sourceSCC.equals(targetSCC));
+                            // if self loop is already present omit the notification
+                            if (needsNotification) {
+                                notifyTcObservers(sccs.getPartition(sourceSCC), sccs.getPartition(targetSCC),
+                                        Direction.INSERT);
+                            }
+                        }
+                    }
+                }
+
+                // 2. delete edges, nodes
+                List<V> sourceSCCs = new ArrayList<V>();
+                List<V> targetSCCs = new ArrayList<V>();
+
+                for (V r : isectRoots) {
+                    List<V> sourceSCCsOfSCC = getSourceSCCsOfSCC(r);
+                    List<V> targetSCCsOfSCC = getTargetSCCsOfSCC(r);
+
+                    for (V sourceSCC : sourceSCCsOfSCC) {
+                        if (!sourceSCC.equals(r)) {
+                            reducedGraph.deleteEdgeIfExists(sourceSCC, r);
+                        }
+                    }
+
+                    for (V targetSCC : targetSCCsOfSCC) {
+                        if (!isectRoots.contains(targetSCC) && !r.equals(targetSCC)) {
+                            reducedGraph.deleteEdgeIfExists(r, targetSCC);
+                        }
+                    }
+
+                    sourceSCCs.addAll(sourceSCCsOfSCC);
+                    targetSCCs.addAll(targetSCCsOfSCC);
+                }
+
+                for (V r : isectRoots) {
+                    reducedGraph.deleteNode(r);
+                }
+
+                // 3. union
+                Iterator<V> iterator = isectRoots.iterator();
+                V newRoot = iterator.next();
+                while (iterator.hasNext()) {
+                    newRoot = sccs.union(newRoot, iterator.next());
+                }
+
+                // 4. add new node
+                reducedGraph.insertNode(newRoot);
+
+                // 5. add edges
+                Set<V> containedNodes = sccs.getPartition(newRoot);
+
+                for (V sourceSCC : sourceSCCs) {
+                    if (!containedNodes.contains(sourceSCC) && !sourceSCC.equals(newRoot)) {
+                        reducedGraph.insertEdge(sourceSCC, newRoot);
+                    }
+                }
+                for (V targetSCC : targetSCCs) {
+                    if (!containedNodes.contains(targetSCC) && !targetSCC.equals(newRoot)) {
+                        reducedGraph.insertEdge(newRoot, targetSCC);
+                    }
+                }
+            } else {
+                if (observers.size() > 0 && GraphHelper.getEdgeCount(source, target, gds) == 1) {
+                    counting.attachObserver(countingListener);
+                }
+                reducedGraph.insertEdge(sourceRoot, targetRoot);
+                counting.detachObserver(countingListener);
+            }
+        } else {
+            // Notifications about self-loops
+            if (observers.size() > 0 && sccs.getPartition(sourceRoot).size() == 1
+                    && GraphHelper.getEdgeCount(source, target, gds) == 1) {
+                notifyTcObservers(source, source, Direction.INSERT);
+            }
+        }
+    }
+    
+    @Override
+    public void edgeDeleted(V source, V target) {
+        V sourceRoot = sccs.find(source);
+        V targetRoot = sccs.find(target);
+
+        if (!sourceRoot.equals(targetRoot)) {
+            if (observers.size() > 0 && GraphHelper.getEdgeCount(source, target, gds) == 0) {
+                counting.attachObserver(countingListener);
+            }
+            reducedGraph.deleteEdgeIfExists(sourceRoot, targetRoot);
+            counting.detachObserver(countingListener);
+        } else {
+            // get the graph for the scc whose root is sourceRoot
+            Graph<V> g = GraphHelper.getSubGraph(sccs.getPartition(sourceRoot), gds);
+
+            // if source is not reachable from target anymore
+            if (!BFS.isReachable(source, target, g)) {
+                // create copies of the current state before destructive manipulation
+                Map<V, Integer> reachableSources = CollectionsFactory.createMap();
+                for (Entry<V, Integer> entry : reducedGraphIndexer.getSourceNodes(sourceRoot).entriesWithMultiplicities()) {
+                    reachableSources.put(entry.getKey(), entry.getValue());
+                }
+                Map<V, Integer> reachableTargets = CollectionsFactory.createMap();
+                for (Entry<V, Integer> entry : reducedGraphIndexer.getTargetNodes(sourceRoot).entriesWithMultiplicities()) {
+                    reachableTargets.put(entry.getKey(), entry.getValue());
+                }
+
+                SCCResult<V> _newSccs = SCC.computeSCC(g);
+
+                // delete scc node (and with its edges too)
+                for (Entry<V, Integer> entry : reachableSources.entrySet()) {
+                    V s = entry.getKey();
+                    for (int i = 0; i < entry.getValue(); i++) {
+                        reducedGraph.deleteEdgeIfExists(s, sourceRoot);
+                    }
+                }
+
+                for (Entry<V, Integer> entry : reachableTargets.entrySet()) {
+                    V t = entry.getKey();
+                    for (int i = 0; i < entry.getValue(); i++) {
+                        reducedGraph.deleteEdgeIfExists(sourceRoot, t);
+                    }
+                }
+
+                sccs.deleteSet(sourceRoot);
+                reducedGraph.deleteNode(sourceRoot);
+
+                Set<Set<V>> newSCCs = _newSccs.getSccs();
+                Set<V> newSCCRoots = CollectionsFactory.createSet();
+
+                // add new nodes and edges to the reduced graph
+                for (Set<V> newSCC : newSCCs) {
+                    V newRoot = sccs.makeSet(newSCC);
+                    reducedGraph.insertNode(newRoot);
+                    newSCCRoots.add(newRoot);
+                }
+                for (V newSCCRoot : newSCCRoots) {
+                    List<V> sourceSCCsOfSCC = getSourceSCCsOfSCC(newSCCRoot);
+                    List<V> targetSCCsOfSCC = getTargetSCCsOfSCC(newSCCRoot);
+
+                    for (V sourceSCC : sourceSCCsOfSCC) {
+                        if (!sourceSCC.equals(newSCCRoot)) {
+                            reducedGraph.insertEdge(sccs.find(sourceSCC), newSCCRoot);
+                        }
+                    }
+                    for (V targetSCC : targetSCCsOfSCC) {
+                        if (!newSCCRoots.contains(targetSCC) && !targetSCC.equals(newSCCRoot))
+                            reducedGraph.insertEdge(newSCCRoot, targetSCC);
+                    }
+                }
+
+                // Must be after the union-find modifications
+                if (observers.size() > 0) {
+                    V newSourceRoot = sccs.find(source);
+                    V newTargetRoot = sccs.find(target);
+
+                    Set<V> sourceSCCs = createSetNullTolerant(counting.getAllReachableSources(newSourceRoot));
+                    sourceSCCs.add(newSourceRoot);
+
+                    Set<V> targetSCCs = createSetNullTolerant(counting.getAllReachableTargets(newTargetRoot));
+                    targetSCCs.add(newTargetRoot);
+                    
+                    for (V sourceSCC : sourceSCCs) {
+                        targetLoop: for (V targetSCC : targetSCCs) {
+                            if (counting.isReachable(sourceSCC, targetSCC)) continue targetLoop;
+                            
+                            boolean needsNotification = 
+                                // Case 1. sourceSCC and targetSCC are the same and it is a one sized scc.
+                                // Issue notifications only if there is no self-loop present at the moment
+                                (sourceSCC.equals(targetSCC) && sccs.getPartition(sourceSCC).size() == 1 && GraphHelper
+                                        .getEdgeCount(sccs.getPartition(sourceSCC).iterator().next(), gds) == 0)
+                                ||
+                                // Case 2. sourceSCC and targetSCC are different sccs.
+                                (!sourceSCC.equals(targetSCC));
+                            // if self loop is already present omit the notification
+                            if (needsNotification) {
+                                notifyTcObservers(sccs.getPartition(sourceSCC), sccs.getPartition(targetSCC),
+                                        Direction.DELETE);
+                            }
+                        }
+                    }
+                }
+            } else {
+                // only handle self-loop notifications - sourceRoot equals to targetRoot
+                if (observers.size() > 0 && sccs.getPartition(sourceRoot).size() == 1
+                        && GraphHelper.getEdgeCount(source, target, gds) == 0) {
+                    notifyTcObservers(source, source, Direction.DELETE);
+                }
+            }
+        }
+    }
+
+    @Override
+    public void nodeInserted(V n) {
+        sccs.makeSet(n);
+        reducedGraph.insertNode(n);
+    }
+
+    @Override
+    public void nodeDeleted(V n) {
+        IMemoryView<V> sources = gds.getSourceNodes(n);
+        IMemoryView<V> targets = gds.getTargetNodes(n);
+
+        for (Entry<V, Integer> entry : sources.entriesWithMultiplicities()) {
+            for (int i = 0; i < entry.getValue(); i++) {
+                V source = entry.getKey();
+                edgeDeleted(source, n);
+            }
+        }
+
+        for (Entry<V, Integer> entry : targets.entriesWithMultiplicities()) {
+            for (int i = 0; i < entry.getValue(); i++) {
+                V target = entry.getKey();
+                edgeDeleted(n, target);
+            }
+        }
+
+        sccs.deleteSet(n);
+    }
+
+    @Override
+    public void attachObserver(ITcObserver<V> to) {
+        observers.add(to);
+    }
+
+    @Override
+    public void detachObserver(ITcObserver<V> to) {
+        observers.remove(to);
+    }
+
+    @Override
+    public Set<V> getAllReachableTargets(V source) {
+        V sourceRoot = sccs.find(source);
+        Set<V> containedNodes = sccs.getPartition(sourceRoot);
+        Set<V> targets = CollectionsFactory.createSet();
+
+        if (containedNodes.size() > 1 || GraphHelper.getEdgeCount(source, gds) == 1) {
+            targets.addAll(containedNodes);
+        }
+
+        Set<V> rootSet = counting.getAllReachableTargets(sourceRoot);
+        if (rootSet != null) {
+            for (V _root : rootSet) {
+                targets.addAll(sccs.getPartition(_root));
+            }
+        }
+
+        return targets;
+    }
+
+    @Override
+    public Set<V> getAllReachableSources(V target) {
+        V targetRoot = sccs.find(target);
+        Set<V> containedNodes = sccs.getPartition(targetRoot);
+        Set<V> sources = CollectionsFactory.createSet();
+
+        if (containedNodes.size() > 1 || GraphHelper.getEdgeCount(target, gds) == 1) {
+            sources.addAll(containedNodes);
+        }
+
+        Set<V> rootSet = counting.getAllReachableSources(targetRoot);
+        if (rootSet != null) {
+            for (V _root : rootSet) {
+                sources.addAll(sccs.getPartition(_root));
+            }
+        }
+        return sources;
+    }
+
+    @Override
+    public boolean isReachable(V source, V target) {
+        V sourceRoot = sccs.find(source);
+        V targetRoot = sccs.find(target);
+
+        if (sourceRoot.equals(targetRoot))
+            return true;
+        else
+            return counting.isReachable(sourceRoot, targetRoot);
+    }
+
+    public List<V> getReachabilityPath(V source, V target) {
+        if (!isReachable(source, target)) {
+            return null;
+        } else {
+            Set<V> sccsInSubGraph = CollectionHelper.intersection(counting.getAllReachableTargets(source),
+                    counting.getAllReachableSources(target));
+            sccsInSubGraph.add(sccs.find(source));
+            sccsInSubGraph.add(sccs.find(target));
+            Set<V> nodesInSubGraph = CollectionsFactory.createSet();
+
+            for (V sccRoot : sccsInSubGraph) {
+                nodesInSubGraph.addAll(sccs.getPartition(sccRoot));
+            }
+
+            return GraphHelper.constructPath(source, target, nodesInSubGraph, gds);
+        }
+    }
+
+    // for JUnit
+    public boolean checkTcRelation(DRedTcRelation<V> tc) {
+
+        for (V s : tc.getTupleStarts()) {
+            for (V t : tc.getTupleEnds(s)) {
+                if (!isReachable(s, t))
+                    return false;
+            }
+        }
+
+        for (V root : counting.getTcRelation().getTupleStarts()) {
+            for (V end : counting.getTcRelation().getTupleEnds(root)) {
+                for (V s : sccs.getPartition(root)) {
+                    for (V t : sccs.getPartition(end)) {
+                        if (!tc.containsTuple(s, t))
+                            return false;
+                    }
+                }
+            }
+        }
+
+        return true;
+    }
+
+    /**
+     * Return the SCCs from which the SCC represented by the root node is reachable. Note that an SCC can be present
+     * multiple times in the returned list (multiple edges between the two SCCs).
+     * 
+     * @param root
+     * @return the list of reachable target SCCs
+     */
+    private List<V> getSourceSCCsOfSCC(V root) {
+        List<V> sourceSCCs = new ArrayList<V>();
+
+        for (V containedNode : this.sccs.getPartition(root)) {
+            IMemoryView<V> sourceNodes = this.gds.getSourceNodes(containedNode);
+            for (V source : sourceNodes.distinctValues()) {
+                sourceSCCs.add(this.sccs.find(source));
+            }
+        }
+
+        return sourceSCCs;
+    }
+    
+    /**
+     * Returns true if the SCC represented by the given root node has incoming edges in the reduced graph, 
+     * false otherwise (if this SCC is a source in the reduced graph). 
+     * 
+     * @param root the root node of an SCC
+     * @return true if it has incoming edges, false otherwise
+     * @since 1.6
+     */
+    public boolean hasIncomingEdges(final V root) {
+        for (final V containedNode : this.sccs.getPartition(root)) {
+            final IMemoryView<V> sourceNodes = this.gds.getSourceNodes(containedNode);
+            for (final V source : sourceNodes.distinctValues()) {
+                final V otherRoot = this.sccs.find(source);
+                if (!Objects.equals(root, otherRoot)) {
+                    return true;
+                }
+            }
+        }
+        return false;
+    }
+    
+    /**
+     * Return the SCCs which are reachable from the SCC represented by the root node. Note that an SCC can be present
+     * multiple times in the returned list (multiple edges between the two SCCs).
+     * 
+     * @param root
+     * @return the list of reachable target SCCs
+     */
+    private List<V> getTargetSCCsOfSCC(V root) {
+        List<V> targetSCCs = new ArrayList<V>();
+
+        for (V containedNode : this.sccs.getPartition(root)) {
+            IMemoryView<V> targetNodes = this.gds.getTargetNodes(containedNode);
+            for (V target : targetNodes.distinctValues()) {
+                targetSCCs.add(this.sccs.find(target));
+            }
+        }
+
+        return targetSCCs;
+    }
+    
+    /**
+     * Returns true if the SCC represented by the given root node has outgoing edges in the reduced graph, 
+     * false otherwise (if this SCC is a sink in the reduced graph). 
+     * 
+     * @param root the root node of an SCC
+     * @return true if it has outgoing edges, false otherwise
+     * @since 1.6
+     */
+    public boolean hasOutgoingEdges(V root) {
+        for (final V containedNode : this.sccs.getPartition(root)) {
+            final IMemoryView<V> targetNodes = this.gds.getTargetNodes(containedNode);
+            for (final V target : targetNodes.distinctValues()) {
+                final V otherRoot = this.sccs.find(target);
+                if (!Objects.equals(root, otherRoot)) {
+                    return true;
+                }
+            }
+        }
+        return false;
+    }
+
+    @Override
+    public void dispose() {
+        gds.detachObserver(this);
+        counting.dispose();
+    }
+
+    /**
+     * Call this method to notify the observers of the transitive closure relation. The tuples used in the notification
+     * will be the Descartes product of the two sets given.
+     * 
+     * @param sources
+     *            the source nodes
+     * @param targets
+     *            the target nodes
+     * @param direction
+     */
+    protected void notifyTcObservers(Set<V> sources, Set<V> targets, Direction direction) {
+        for (V s : sources) {
+            for (V t : targets) {
+                notifyTcObservers(s, t, direction);
+            }
+        }
+    }
+
+    private void notifyTcObservers(V source, V target, Direction direction) {
+        for (ITcObserver<V> observer : observers) {
+            if (direction == Direction.INSERT) {
+                observer.tupleInserted(source, target);
+            }
+            if (direction == Direction.DELETE) {
+                observer.tupleDeleted(source, target);
+            }
+        }
+    }
+
+    /**
+     * Returns the node that is selected as the representative of the SCC containing the argument.
+     * @since 1.6
+     */
+    public V getRepresentative(V node) {
+        return sccs.find(node);
+    }
+
+    public Set<Tuple<V>> getTcRelation() {
+        Set<Tuple<V>> resultSet = new HashSet<Tuple<V>>();
+
+        for (V sourceRoot : sccs.getPartitionHeads()) {
+            Set<V> sources = sccs.getPartition(sourceRoot);
+            if (sources.size() > 1 || GraphHelper.getEdgeCount(sources.iterator().next(), gds) == 1) {
+                for (V source : sources) {
+                    for (V target : sources) {
+                        resultSet.add(new Tuple<V>(source, target));
+                    }
+                }
+            }
+
+            Set<V> reachableTargets = counting.getAllReachableTargets(sourceRoot);
+            if (reachableTargets != null) {
+                for (V targetRoot : reachableTargets) {
+                    for (V source : sources) {
+                        for (V target : sccs.getPartition(targetRoot)) {
+                            resultSet.add(new Tuple<V>(source, target));
+                        }
+                    }
+                }
+            }
+        }
+
+        return resultSet;
+    }
+
+    public boolean isIsolated(V node) {
+        IMemoryView<V> targets = gds.getTargetNodes(node);
+        IMemoryView<V> sources = gds.getSourceNodes(node);
+        return targets.isEmpty() && sources.isEmpty();
+    }
+
+    @Override
+    public IGraphPathFinder<V> getPathFinder() {
+        return new DFSPathFinder<V>(gds, this);
+    }
+
+    /**
+     * The graph of SCCs; each SCC is represented by its representative node (see {@link #getRepresentative(Object)})
+     * @since 1.6
+     */
+    public Graph<V> getReducedGraph() {
+        return reducedGraph;
+    }
+    
+    private static <V> Set<V> createSetNullTolerant(Set<V> initial) {
+        if (initial != null)
+            return CollectionsFactory.createSet(initial);
+        else 
+            return CollectionsFactory.createSet();
+    }
+
+
+}
diff --git a/subprojects/viatra-runtime-base-itc/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/misc/DFSPathFinder.java b/subprojects/viatra-runtime-base-itc/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-base-itc/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-base-itc/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/misc/Edge.java b/subprojects/viatra-runtime-base-itc/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-base-itc/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-base-itc/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/misc/GraphHelper.java b/subprojects/viatra-runtime-base-itc/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-base-itc/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-base-itc/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/misc/IGraphPathFinder.java b/subprojects/viatra-runtime-base-itc/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-base-itc/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-base-itc/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/misc/ITcRelation.java b/subprojects/viatra-runtime-base-itc/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-base-itc/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-base-itc/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/misc/Tuple.java b/subprojects/viatra-runtime-base-itc/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-base-itc/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-base-itc/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/misc/bfs/BFS.java b/subprojects/viatra-runtime-base-itc/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-base-itc/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-base-itc/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/misc/dfs/DFSAlg.java b/subprojects/viatra-runtime-base-itc/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-base-itc/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-base-itc/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/misc/scc/PKAlg.java b/subprojects/viatra-runtime-base-itc/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-base-itc/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-base-itc/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/misc/scc/SCC.java b/subprojects/viatra-runtime-base-itc/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-base-itc/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-base-itc/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/misc/scc/SCCProperty.java b/subprojects/viatra-runtime-base-itc/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-base-itc/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-base-itc/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/misc/scc/SCCResult.java b/subprojects/viatra-runtime-base-itc/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-base-itc/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-base-itc/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/misc/topsort/TopologicalSorting.java b/subprojects/viatra-runtime-base-itc/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-base-itc/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;
+    }
+}
diff --git a/subprojects/viatra-runtime-base-itc/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/representative/RepresentativeElectionAlgorithm.java b/subprojects/viatra-runtime-base-itc/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/representative/RepresentativeElectionAlgorithm.java
new file mode 100644
index 00000000..51015404
--- /dev/null
+++ b/subprojects/viatra-runtime-base-itc/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/representative/RepresentativeElectionAlgorithm.java
@@ -0,0 +1,140 @@
+/*
+ * SPDX-FileCopyrightText: 2023 The Refinery Authors <https://refinery.tools/>
+ *
+ * SPDX-License-Identifier: EPL-2.0
+ */
+package tools.refinery.viatra.runtime.base.itc.alg.representative;
+
+import tools.refinery.viatra.runtime.base.itc.graphimpl.Graph;
+import tools.refinery.viatra.runtime.base.itc.igraph.IGraphObserver;
+import tools.refinery.viatra.runtime.matchers.util.Direction;
+
+import java.util.HashMap;
+import java.util.HashSet;
+import java.util.Map;
+import java.util.Set;
+
+public abstract class RepresentativeElectionAlgorithm implements IGraphObserver<Object> {
+        protected final Graph<Object> graph;
+        protected final Map<Object, Object> representatives = new HashMap<>();
+        protected final Map<Object, Set<Object>> components = new HashMap<>();
+        private RepresentativeObserver observer;
+
+        protected RepresentativeElectionAlgorithm(Graph<Object> graph) {
+                this.graph = graph;
+                initializeComponents();
+                graph.attachObserver(this);
+        }
+
+        protected abstract void initializeComponents();
+
+        protected void initializeSet(Set<Object> set) {
+                var iterator = set.iterator();
+                if (!iterator.hasNext()) {
+                        // Set is empty.
+                        return;
+                }
+                var representative = iterator.next();
+                for (var node : set) {
+                        var oldRepresentative = representatives.put(node, representative);
+                        if (oldRepresentative != null && !representative.equals(oldRepresentative)) {
+                                throw new IllegalStateException("Node %s is already in a set represented by %s, cannot add it to %s"
+                                                .formatted(node, oldRepresentative, set));
+                        }
+                }
+                components.put(representative, set);
+        }
+
+        protected void merge(Object leftRepresentative, Object rightRepresentative) {
+                if (leftRepresentative.equals(rightRepresentative)) {
+                        return;
+                }
+                var leftSet = getComponent(leftRepresentative);
+                var rightSet = getComponent(rightRepresentative);
+                if (leftSet.size() < rightSet.size()) {
+                        merge(rightRepresentative, rightSet, leftRepresentative, leftSet);
+                } else {
+                        merge(leftRepresentative, leftSet, rightRepresentative, rightSet);
+                }
+        }
+
+        private void merge(Object preservedRepresentative, Set<Object> preservedSet, Object removedRepresentative,
+                                           Set<Object> removedSet) {
+                components.remove(removedRepresentative);
+                for (var node : removedSet) {
+                        representatives.put(node, preservedRepresentative);
+                        preservedSet.add(node);
+                        notifyToObservers(node, removedRepresentative, preservedRepresentative);
+                }
+        }
+
+        protected void assignNewRepresentative(Object oldRepresentative, Set<Object> set) {
+                var iterator = set.iterator();
+                if (!iterator.hasNext()) {
+                        return;
+                }
+                var newRepresentative = iterator.next();
+                components.put(newRepresentative, set);
+                for (var node : set) {
+                        var oldRepresentativeOfNode = representatives.put(node, newRepresentative);
+                        if (!oldRepresentative.equals(oldRepresentativeOfNode)) {
+                                throw new IllegalArgumentException("Node %s was not represented by %s but by %s"
+                                                .formatted(node, oldRepresentative, oldRepresentativeOfNode));
+                        }
+                        notifyToObservers(node, oldRepresentative, newRepresentative);
+                }
+        }
+
+        public void setObserver(RepresentativeObserver observer) {
+                this.observer = observer;
+        }
+
+        public Map<Object, Set<Object>> getComponents() {
+                return components;
+        }
+
+        public Object getRepresentative(Object node) {
+                return representatives.get(node);
+        }
+
+        public Set<Object> getComponent(Object representative) {
+                return components.get(representative);
+        }
+
+        public void dispose() {
+                graph.detachObserver(this);
+        }
+
+        @Override
+        public void nodeInserted(Object n) {
+                var component = new HashSet<>(1);
+                component.add(n);
+                initializeSet(component);
+                notifyToObservers(n, n, Direction.INSERT);
+        }
+
+        @Override
+        public void nodeDeleted(Object n) {
+                var representative = representatives.remove(n);
+                if (!representative.equals(n)) {
+                        throw new IllegalStateException("Trying to delete node with dangling edges");
+                }
+                components.remove(representative);
+                notifyToObservers(n, representative, Direction.DELETE);
+        }
+
+        protected void notifyToObservers(Object node, Object oldRepresentative, Object newRepresentative) {
+                notifyToObservers(node, oldRepresentative, Direction.DELETE);
+                notifyToObservers(node, newRepresentative, Direction.INSERT);
+        }
+
+        protected void notifyToObservers(Object node, Object representative, Direction direction) {
+                if (observer != null) {
+                        observer.tupleChanged(node, representative, direction);
+                }
+        }
+
+        public interface Factory {
+                RepresentativeElectionAlgorithm create(Graph<Object> graph);
+        }
+}
diff --git a/subprojects/viatra-runtime-base-itc/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/representative/RepresentativeObserver.java b/subprojects/viatra-runtime-base-itc/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/representative/RepresentativeObserver.java
new file mode 100644
index 00000000..93cce1ea
--- /dev/null
+++ b/subprojects/viatra-runtime-base-itc/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/representative/RepresentativeObserver.java
@@ -0,0 +1,12 @@
+/*
+ * SPDX-FileCopyrightText: 2023 The Refinery Authors <https://refinery.tools/>
+ *
+ * SPDX-License-Identifier: EPL-2.0
+ */
+package tools.refinery.viatra.runtime.base.itc.alg.representative;
+
+import tools.refinery.viatra.runtime.matchers.util.Direction;
+
+public interface RepresentativeObserver {
+        void tupleChanged(Object node, Object representative, Direction direction);
+}
diff --git a/subprojects/viatra-runtime-base-itc/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/representative/StronglyConnectedComponentAlgorithm.java b/subprojects/viatra-runtime-base-itc/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/representative/StronglyConnectedComponentAlgorithm.java
new file mode 100644
index 00000000..ba42bb13
--- /dev/null
+++ b/subprojects/viatra-runtime-base-itc/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/representative/StronglyConnectedComponentAlgorithm.java
@@ -0,0 +1,66 @@
+/*
+ * SPDX-FileCopyrightText: 2023 The Refinery Authors <https://refinery.tools/>
+ *
+ * SPDX-License-Identifier: EPL-2.0
+ */
+package tools.refinery.viatra.runtime.base.itc.alg.representative;
+
+import tools.refinery.viatra.runtime.base.itc.alg.misc.GraphHelper;
+import tools.refinery.viatra.runtime.base.itc.alg.misc.bfs.BFS;
+import tools.refinery.viatra.runtime.base.itc.alg.misc.scc.SCC;
+import tools.refinery.viatra.runtime.base.itc.graphimpl.Graph;
+
+import java.util.Collection;
+import java.util.Set;
+
+public class StronglyConnectedComponentAlgorithm extends RepresentativeElectionAlgorithm {
+        public StronglyConnectedComponentAlgorithm(Graph<Object> graph) {
+                super(graph);
+        }
+
+        @Override
+        protected void initializeComponents() {
+                var computedSCCs = SCC.computeSCC(graph).getSccs();
+                for (var computedSCC : computedSCCs) {
+                        initializeSet(computedSCC);
+                }
+        }
+
+        @Override
+        public void edgeInserted(Object source, Object target) {
+                var sourceRoot = getRepresentative(source);
+                var targetRoot = getRepresentative(target);
+                if (sourceRoot.equals(targetRoot)) {
+                        // New edge does not change strongly connected components.
+                        return;
+                }
+                if (BFS.isReachable(target, source, graph)) {
+                        merge(sourceRoot, targetRoot);
+                }
+        }
+
+        @Override
+        public void edgeDeleted(Object source, Object target) {
+                var sourceRoot = getRepresentative(source);
+                var targetRoot = getRepresentative(target);
+                if (!sourceRoot.equals(targetRoot)) {
+                        // New edge does not change strongly connected components.
+                        return;
+                }
+                var component = GraphHelper.getSubGraph(getComponent(sourceRoot), graph);
+                if (!BFS.isReachable(source, target, component)) {
+                        var newSCCs = SCC.computeSCC(component).getSccs();
+                        split(sourceRoot, newSCCs);
+                }
+        }
+
+        private void split(Object preservedRepresentative, Collection<? extends Set<Object>> sets) {
+                for (var set : sets) {
+                        if (set.contains(preservedRepresentative)) {
+                                components.put(preservedRepresentative, set);
+                        } else {
+                                assignNewRepresentative(preservedRepresentative, set);
+                        }
+                }
+        }
+}
diff --git a/subprojects/viatra-runtime-base-itc/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/representative/WeaklyConnectedComponentAlgorithm.java b/subprojects/viatra-runtime-base-itc/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/representative/WeaklyConnectedComponentAlgorithm.java
new file mode 100644
index 00000000..22159499
--- /dev/null
+++ b/subprojects/viatra-runtime-base-itc/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/representative/WeaklyConnectedComponentAlgorithm.java
@@ -0,0 +1,85 @@
+/*
+ * SPDX-FileCopyrightText: 2023 The Refinery Authors <https://refinery.tools/>
+ *
+ * SPDX-License-Identifier: EPL-2.0
+ */
+package tools.refinery.viatra.runtime.base.itc.alg.representative;
+
+import tools.refinery.viatra.runtime.base.itc.graphimpl.Graph;
+
+import java.util.ArrayDeque;
+import java.util.HashSet;
+import java.util.Set;
+
+public class WeaklyConnectedComponentAlgorithm extends RepresentativeElectionAlgorithm {
+        public WeaklyConnectedComponentAlgorithm(Graph<Object> graph) {
+                super(graph);
+        }
+
+        @Override
+        protected void initializeComponents() {
+                for (var node : graph.getAllNodes()) {
+                        if (representatives.containsKey(node)) {
+                                continue;
+                        }
+                        var reachable = getReachableNodes(node);
+                        initializeSet(reachable);
+                }
+        }
+
+        @Override
+        public void edgeInserted(Object source, Object target) {
+                var sourceRoot = getRepresentative(source);
+                var targetRoot = getRepresentative(target);
+                merge(sourceRoot, targetRoot);
+        }
+
+        @Override
+        public void edgeDeleted(Object source, Object target) {
+                var sourceRoot = getRepresentative(source);
+                var targetRoot = getRepresentative(target);
+                if (!sourceRoot.equals(targetRoot)) {
+                        throw new IllegalArgumentException("Trying to remove edge not in graph");
+                }
+                var targetReachable = getReachableNodes(target);
+                if (!targetReachable.contains(source)) {
+                        split(sourceRoot, targetReachable);
+                }
+        }
+
+        private void split(Object sourceRepresentative, Set<Object> targetReachable) {
+                var sourceComponent = getComponent(sourceRepresentative);
+                sourceComponent.removeAll(targetReachable);
+                if (targetReachable.contains(sourceRepresentative)) {
+                        components.put(sourceRepresentative, targetReachable);
+                        assignNewRepresentative(sourceRepresentative, sourceComponent);
+                } else {
+                        assignNewRepresentative(sourceRepresentative, targetReachable);
+                }
+        }
+
+        private Set<Object> getReachableNodes(Object source) {
+                var retSet = new HashSet<>();
+                retSet.add(source);
+                var nodeQueue = new ArrayDeque<>();
+                nodeQueue.addLast(source);
+
+                while (!nodeQueue.isEmpty()) {
+                        var node = nodeQueue.removeFirst();
+                        for (var neighbor : graph.getTargetNodes(node).distinctValues()) {
+                                if (!retSet.contains(neighbor)) {
+                                        retSet.add(neighbor);
+                                        nodeQueue.addLast(neighbor);
+                                }
+                        }
+                        for (var neighbor : graph.getSourceNodes(node).distinctValues()) {
+                                if (!retSet.contains(neighbor)) {
+                                        retSet.add(neighbor);
+                                        nodeQueue.addLast(neighbor);
+                                }
+                        }
+                }
+
+                return retSet;
+        }
+}
diff --git a/subprojects/viatra-runtime-base-itc/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/util/CollectionHelper.java b/subprojects/viatra-runtime-base-itc/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/util/CollectionHelper.java
new file mode 100644
index 00000000..c9b3cafa
--- /dev/null
+++ b/subprojects/viatra-runtime-base-itc/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/util/CollectionHelper.java
@@ -0,0 +1,64 @@
+/*******************************************************************************
+ * 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.util;
+
+import java.util.Set;
+
+import tools.refinery.viatra.runtime.matchers.util.CollectionsFactory;
+
+/**
+ * @author Tamas Szabo
+ * 
+ */
+public class CollectionHelper {
+
+    private CollectionHelper() {/*Utility class constructor*/}
+    
+    /**
+     * Returns the intersection of two sets. It calls {@link Set#retainAll(java.util.Collection)} but returns a new set
+     * containing the elements of the intersection.
+     * 
+     * @param set1
+     *            the first set (can be null, interpreted as empty)
+     * @param set2
+     *            the second set (can be null, interpreted as empty)
+     * @return the intersection of the sets
+     * @since 1.7
+     */
+    public static <V> Set<V> intersection(Set<V> set1, Set<V> set2) {
+        if (set1 == null || set2 == null) 
+            return CollectionsFactory.createSet();
+        
+        Set<V> intersection = CollectionsFactory.createSet(set1);
+        intersection.retainAll(set2);
+        return intersection;
+    }
+
+    
+    /**
+     * Returns the difference of two sets (S1\S2). It calls {@link Set#removeAll(java.util.Collection)} but returns a
+     * new set containing the elements of the difference.
+     * 
+     * @param set1
+     *            the first set (can be null, interpreted as empty)
+     * @param set2
+     *            the second set (can be null, interpreted as empty)
+     * @return the difference of the sets
+     * @since 1.7
+     */
+    public static <V> Set<V> difference(Set<V> set1, Set<V> set2) {
+        if (set1 == null)
+            return CollectionsFactory.createSet();
+        
+        Set<V> difference = CollectionsFactory.createSet(set1);
+        if (set2 != null) difference.removeAll(set2);
+        return difference;
+    }
+    
+}
diff --git a/subprojects/viatra-runtime-base-itc/src/main/java/tools/refinery/viatra/runtime/base/itc/graphimpl/DotGenerator.java b/subprojects/viatra-runtime-base-itc/src/main/java/tools/refinery/viatra/runtime/base/itc/graphimpl/DotGenerator.java
new file mode 100644
index 00000000..0e21f323
--- /dev/null
+++ b/subprojects/viatra-runtime-base-itc/src/main/java/tools/refinery/viatra/runtime/base/itc/graphimpl/DotGenerator.java
@@ -0,0 +1,160 @@
+/*******************************************************************************
+ * Copyright (c) 2010-2019, 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.graphimpl;
+
+import tools.refinery.viatra.runtime.base.itc.alg.misc.scc.SCC;
+import tools.refinery.viatra.runtime.base.itc.alg.misc.scc.SCCResult;
+import tools.refinery.viatra.runtime.matchers.util.IMemoryView;
+
+import java.util.HashMap;
+import java.util.Map;
+import java.util.Set;
+import java.util.function.Function;
+
+/**
+ * This class contains utility methods to generate dot representations for {@link Graph} instances.
+ *
+ * @author Tamas Szabo
+ * @since 2.3
+ */
+public class DotGenerator {
+
+    private static final String[] colors = new String[] { "yellow", "blue", "red", "green", "gray", "cyan" };
+
+    private DotGenerator() {
+
+    }
+
+    /**
+     * Generates the dot representation for the given graph.
+     *
+     * @param graph
+     *            the graph
+     * @param colorSCCs
+     *            specifies if the strongly connected components with size greater than shall be colored
+     * @param nameFunction
+     *            use this function to provide custom names to nodes, null if the default toString shall be used
+     * @param colorFunction
+     *            use this function to provide custom color to nodes, null if the default white color shall be used
+     * @param edgeFunction
+     *            use this function to provide custom edge labels, null if no edge label shall be printed
+     * @return the dot representation as a string
+     */
+    public static <V> String generateDot(final Graph<V> graph, final boolean colorSCCs,
+            final Function<V, String> nameFunction, final Function<V, String> colorFunction,
+            final Function<V, Function<V, String>> edgeFunction) {
+        final Map<V, String> colorMap = new HashMap<V, String>();
+
+        if (colorSCCs) {
+            final SCCResult<V> result = SCC.computeSCC(graph);
+            final Set<Set<V>> sccs = result.getSccs();
+
+            int i = 0;
+            for (final Set<V> scc : sccs) {
+                if (scc.size() > 1) {
+                    for (final V node : scc) {
+                        final String color = colorMap.get(node);
+                        if (color == null) {
+                            colorMap.put(node, colors[i % colors.length]);
+                        } else {
+                            colorMap.put(node, colorMap.get(node) + ":" + colors[i % colors.length]);
+                        }
+                    }
+                    i++;
+                }
+            }
+
+            // if a node has no color yet, then make it white
+            for (final V node : graph.getAllNodes()) {
+                if (!colorMap.containsKey(node)) {
+                    colorMap.put(node, "white");
+                }
+            }
+        } else {
+            for (final V node : graph.getAllNodes()) {
+                colorMap.put(node, "white");
+            }
+        }
+
+        if (colorFunction != null) {
+            for (final V node : graph.getAllNodes()) {
+                colorMap.put(node, colorFunction.apply(node));
+            }
+        }
+
+        final StringBuilder builder = new StringBuilder();
+        builder.append("digraph g {\n");
+
+        for (final V node : graph.getAllNodes()) {
+            final String nodePresentation = nameFunction == null ? node.toString() : nameFunction.apply(node);
+            builder.append("\"" + nodePresentation + "\"");
+            builder.append("[style=filled,fillcolor=" + colorMap.get(node) + "]");
+            builder.append(";\n");
+        }
+
+        for (final V source : graph.getAllNodes()) {
+            final IMemoryView<V> targets = graph.getTargetNodes(source);
+            if (!targets.isEmpty()) {
+                final String sourcePresentation = nameFunction == null ? source.toString() : nameFunction.apply(source);
+                for (final V target : targets.distinctValues()) {
+                    String edgeLabel = null;
+                    if (edgeFunction != null) {
+                        final Function<V, String> v1 = edgeFunction.apply(source);
+                        if (v1 != null) {
+                            edgeLabel = v1.apply(target);
+                        }
+                    }
+
+                    final String targetPresentation = nameFunction == null ? target.toString()
+                            : nameFunction.apply(target);
+
+                    builder.append("\"" + sourcePresentation + "\" -> \"" + targetPresentation + "\"");
+                    if (edgeLabel != null) {
+                        builder.append("[label=\"" + edgeLabel + "\"]");
+                    }
+                    builder.append(";\n");
+                }
+            }
+        }
+
+        builder.append("}");
+        return builder.toString();
+    }
+
+    /**
+     * Generates the dot representation for the given graph. No special pretty printing customization will be applied.
+     *
+     * @param graph
+     *            the graph
+     * @return the dot representation as a string
+     */
+    public static <V> String generateDot(final Graph<V> graph) {
+        return generateDot(graph, false, null, null, null);
+    }
+
+    /**
+     * Returns a simple name shortener function that can be used in the graphviz visualization to help with readability.
+     * WARNING: if you shorten the name of the {@link Node}s too much, the visualization may become incorrect because
+     * grahpviz will treat different nodes as the same if their shortened names are the same.
+     *
+     * @param maxLength
+     *            the maximum length of the text that is kept from the toString of the objects in the graph
+     * @return the shrunk toString value
+     */
+    public static <V> Function<V, String> getNameShortener(final int maxLength) {
+        return new Function<V, String>() {
+            @Override
+            public String apply(final V obj) {
+                final String value = obj.toString();
+                return value.substring(0, Math.min(value.length(), maxLength));
+            }
+        };
+    }
+
+}
diff --git a/subprojects/viatra-runtime-base-itc/src/main/java/tools/refinery/viatra/runtime/base/itc/graphimpl/Graph.java b/subprojects/viatra-runtime-base-itc/src/main/java/tools/refinery/viatra/runtime/base/itc/graphimpl/Graph.java
new file mode 100644
index 00000000..70cbc77e
--- /dev/null
+++ b/subprojects/viatra-runtime-base-itc/src/main/java/tools/refinery/viatra/runtime/base/itc/graphimpl/Graph.java
@@ -0,0 +1,185 @@
+/*******************************************************************************
+ * 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.graphimpl;
+
+import tools.refinery.viatra.runtime.base.itc.igraph.IBiDirectionalGraphDataSource;
+import tools.refinery.viatra.runtime.base.itc.igraph.IGraphDataSource;
+import tools.refinery.viatra.runtime.base.itc.igraph.IGraphObserver;
+import tools.refinery.viatra.runtime.matchers.util.CollectionsFactory;
+import tools.refinery.viatra.runtime.matchers.util.CollectionsFactory.MemoryType;
+import tools.refinery.viatra.runtime.matchers.util.IMemoryView;
+import tools.refinery.viatra.runtime.matchers.util.IMultiLookup;
+
+import java.util.List;
+import java.util.Map;
+import java.util.Map.Entry;
+import java.util.Set;
+
+public class Graph<V> implements IGraphDataSource<V>, IBiDirectionalGraphDataSource<V> {
+
+    // source -> target -> count
+    private IMultiLookup<V, V> outgoingEdges;
+    // target -> source -> count
+    private IMultiLookup<V, V> incomingEdges;
+
+    private Set<V> nodes;
+
+    private List<IGraphObserver<V>> observers;
+
+    public Graph() {
+        outgoingEdges = CollectionsFactory.createMultiLookup(Object.class, MemoryType.MULTISETS, Object.class);
+        incomingEdges = CollectionsFactory.createMultiLookup(Object.class, MemoryType.MULTISETS, Object.class);
+        nodes = CollectionsFactory.createSet();
+        observers = CollectionsFactory.createObserverList();
+    }
+
+    public void insertEdge(V source, V target) {
+        outgoingEdges.addPair(source, target);
+        incomingEdges.addPair(target, source);
+
+        for (IGraphObserver<V> go : observers) {
+            go.edgeInserted(source, target);
+        }
+    }
+
+    /**
+     * No-op if trying to delete edge that does not exist
+     *
+     * @since 2.0
+     * @see #deleteEdgeIfExists(Object, Object)
+     */
+    public void deleteEdgeIfExists(V source, V target) {
+        boolean containedEdge = outgoingEdges.lookupOrEmpty(source).containsNonZero(target);
+        if (containedEdge) {
+            deleteEdgeThatExists(source, target);
+        }
+    }
+
+    /**
+     * @throws IllegalStateException
+     *             if trying to delete edge that does not exist
+     * @since 2.0
+     * @see #deleteEdgeIfExists(Object, Object)
+     */
+    public void deleteEdgeThatExists(V source, V target) {
+        outgoingEdges.removePair(source, target);
+        incomingEdges.removePair(target, source);
+        for (IGraphObserver<V> go : observers) {
+            go.edgeDeleted(source, target);
+        }
+    }
+
+    /**
+     * @deprecated use explicitly {@link #deleteEdgeThatExists(Object, Object)} or
+     *             {@link #deleteEdgeIfExists(Object, Object)} instead. To preserve backwards compatibility, this method
+     *             delegates to the latter.
+     *
+     */
+    @Deprecated
+    public void deleteEdge(V source, V target) {
+        deleteEdgeIfExists(source, target);
+    }
+
+    /**
+     * Insert the given node into the graph.
+     */
+    public void insertNode(V node) {
+        if (nodes.add(node)) {
+            for (IGraphObserver<V> go : observers) {
+                go.nodeInserted(node);
+            }
+        }
+    }
+
+    /**
+     * Deletes the given node AND all of the edges going in and out from the node.
+     */
+    public void deleteNode(V node) {
+        if (nodes.remove(node)) {
+            IMemoryView<V> incomingView = incomingEdges.lookup(node);
+            if (incomingView != null) {
+                Map<V, Integer> incoming = CollectionsFactory.createMap(incomingView.asMap());
+
+                for (Entry<V, Integer> entry : incoming.entrySet()) {
+                    for (int i = 0; i < entry.getValue(); i++) {
+                        deleteEdgeThatExists(entry.getKey(), node);
+                    }
+                }
+            }
+
+            IMemoryView<V> outgoingView = outgoingEdges.lookup(node);
+            if (outgoingView != null) {
+                Map<V, Integer> outgoing = CollectionsFactory.createMap(outgoingView.asMap());
+
+                for (Entry<V, Integer> entry : outgoing.entrySet()) {
+                    for (int i = 0; i < entry.getValue(); i++) {
+                        deleteEdgeThatExists(node, entry.getKey());
+                    }
+                }
+            }
+
+            for (IGraphObserver<V> go : observers) {
+                go.nodeDeleted(node);
+            }
+        }
+    }
+
+    @Override
+    public void attachObserver(IGraphObserver<V> go) {
+        observers.add(go);
+    }
+
+    @Override
+    public void attachAsFirstObserver(IGraphObserver<V> observer) {
+        observers.add(0, observer);
+    }
+
+    @Override
+    public void detachObserver(IGraphObserver<V> go) {
+        observers.remove(go);
+    }
+
+    @Override
+    public Set<V> getAllNodes() {
+        return nodes;
+    }
+
+    @Override
+    public IMemoryView<V> getTargetNodes(V source) {
+        return outgoingEdges.lookupOrEmpty(source);
+    }
+
+    @Override
+    public IMemoryView<V> getSourceNodes(V target) {
+        return incomingEdges.lookupOrEmpty(target);
+    }
+
+    @Override
+    public String toString() {
+        StringBuilder sb = new StringBuilder();
+        sb.append("nodes = ");
+        for (V n : getAllNodes()) {
+            sb.append(n.toString());
+            sb.append(" ");
+        }
+        sb.append(" edges = ");
+        for (V source : outgoingEdges.distinctKeys()) {
+            IMemoryView<V> targets = outgoingEdges.lookup(source);
+            for (V target : targets.distinctValues()) {
+                int count = targets.getCount(target);
+                for (int i = 0; i < count; i++) {
+                    sb.append("(" + source + "," + target + ") ");
+                }
+            }
+        }
+        return sb.toString();
+    }
+
+}
diff --git a/subprojects/viatra-runtime-base-itc/src/main/java/tools/refinery/viatra/runtime/base/itc/igraph/IBiDirectionalGraphDataSource.java b/subprojects/viatra-runtime-base-itc/src/main/java/tools/refinery/viatra/runtime/base/itc/igraph/IBiDirectionalGraphDataSource.java
new file mode 100644
index 00000000..64659447
--- /dev/null
+++ b/subprojects/viatra-runtime-base-itc/src/main/java/tools/refinery/viatra/runtime/base/itc/igraph/IBiDirectionalGraphDataSource.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.igraph;
+
+import tools.refinery.viatra.runtime.matchers.util.IMemoryView;
+import tools.refinery.viatra.runtime.matchers.util.IMultiset;
+
+/**
+ * A bi-directional graph data source supports all operations that an {@link IGraphDataSource} does, but it 
+ * also makes it possible to query the incoming edges of nodes, not only the outgoing edges. 
+ * 
+ * @author Tamas Szabo
+ * 
+ * @param <V> the type of the nodes in the graph
+ */
+public interface IBiDirectionalGraphDataSource<V> extends IGraphDataSource<V> {
+
+    /**
+     * Returns the source nodes for the given target node.  
+     * The returned data structure is an {@link IMultiset} because of potential parallel edges in the graph data source.
+     * 
+     * The method must not return null.
+     * 
+     * @param target the target node
+     * @return the multiset of source nodes
+     * @since 2.0
+     */
+    public IMemoryView<V> getSourceNodes(V target);
+    
+}
diff --git a/subprojects/viatra-runtime-base-itc/src/main/java/tools/refinery/viatra/runtime/base/itc/igraph/IBiDirectionalWrapper.java b/subprojects/viatra-runtime-base-itc/src/main/java/tools/refinery/viatra/runtime/base/itc/igraph/IBiDirectionalWrapper.java
new file mode 100644
index 00000000..becab0eb
--- /dev/null
+++ b/subprojects/viatra-runtime-base-itc/src/main/java/tools/refinery/viatra/runtime/base/itc/igraph/IBiDirectionalWrapper.java
@@ -0,0 +1,110 @@
+/*******************************************************************************
+ * 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.igraph;
+
+import java.util.Set;
+
+import tools.refinery.viatra.runtime.matchers.util.CollectionsFactory;
+import tools.refinery.viatra.runtime.matchers.util.CollectionsFactory.MemoryType;
+import tools.refinery.viatra.runtime.matchers.util.IMemoryView;
+import tools.refinery.viatra.runtime.matchers.util.IMultiLookup;
+
+/**
+ * This class can be used to wrap an {@link IGraphDataSource} into an {@link IBiDirectionalGraphDataSource}. This class
+ * provides support for the retrieval of source nodes for a given target which is not supported by standard
+ * {@link IGraphDataSource} implementations.
+ * 
+ * @author Tamas Szabo
+ *
+ * @param <V>
+ *            the type parameter of the nodes in the graph data source
+ */
+public class IBiDirectionalWrapper<V> implements IBiDirectionalGraphDataSource<V>, IGraphObserver<V> {
+
+    private IGraphDataSource<V> wrappedDataSource;
+    // target -> source -> count
+    private IMultiLookup<V, V> incomingEdges;
+
+    public IBiDirectionalWrapper(IGraphDataSource<V> gds) {
+        this.wrappedDataSource = gds;
+
+        this.incomingEdges = CollectionsFactory.createMultiLookup(
+                Object.class, MemoryType.MULTISETS, Object.class);
+
+        if (gds.getAllNodes() != null) {
+            for (V source : gds.getAllNodes()) {
+                IMemoryView<V> targets = gds.getTargetNodes(source);
+                for (V target : targets.distinctValues()) {
+                    int count = targets.getCount(target);
+                    for (int i = 0; i < count; i++) {
+                        edgeInserted(source, target);
+                    }
+                }
+            }
+        }
+
+        gds.attachAsFirstObserver(this);
+    }
+
+    @Override
+    public void attachObserver(IGraphObserver<V> observer) {
+        wrappedDataSource.attachObserver(observer);
+    }
+
+    @Override
+    public void attachAsFirstObserver(IGraphObserver<V> observer) {
+        wrappedDataSource.attachAsFirstObserver(observer);
+    }
+
+    @Override
+    public void detachObserver(IGraphObserver<V> observer) {
+        wrappedDataSource.detachObserver(observer);
+    }
+
+    @Override
+    public Set<V> getAllNodes() {
+        return wrappedDataSource.getAllNodes();
+    }
+
+    @Override
+    public IMemoryView<V> getTargetNodes(V source) {
+        return wrappedDataSource.getTargetNodes(source);
+    }
+
+    @Override
+    public IMemoryView<V> getSourceNodes(V target) {
+        return incomingEdges.lookupOrEmpty(target);
+    }
+
+    @Override
+    public void edgeInserted(V source, V target) {
+        incomingEdges.addPair(target, source);
+    }
+
+    @Override
+    public void edgeDeleted(V source, V target) {
+        incomingEdges.removePair(target, source);
+    }
+
+    @Override
+    public void nodeInserted(V n) {
+
+    }
+
+    @Override
+    public void nodeDeleted(V node) {
+
+    }
+
+    @Override
+    public String toString() {
+        return wrappedDataSource.toString();
+    }
+}
diff --git a/subprojects/viatra-runtime-base-itc/src/main/java/tools/refinery/viatra/runtime/base/itc/igraph/IGraphDataSource.java b/subprojects/viatra-runtime-base-itc/src/main/java/tools/refinery/viatra/runtime/base/itc/igraph/IGraphDataSource.java
new file mode 100644
index 00000000..3fa65936
--- /dev/null
+++ b/subprojects/viatra-runtime-base-itc/src/main/java/tools/refinery/viatra/runtime/base/itc/igraph/IGraphDataSource.java
@@ -0,0 +1,70 @@
+/*******************************************************************************
+ * 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.igraph;
+
+import tools.refinery.viatra.runtime.matchers.util.IMemoryView;
+import tools.refinery.viatra.runtime.matchers.util.IMultiset;
+
+import java.util.Set;
+
+/**
+ * The interface prescribes the set of operations that a graph data source must support.
+ * <p> Note that the old version of the interface is broken at version 1.6;
+ *  MultiSets are now presented as Maps instead of Lists.
+ *
+ * @author Tamas Szabo
+ *
+ * @param <V>
+ *            the type of the nodes in the graph
+ */
+public interface IGraphDataSource<V> {
+
+    /**
+     * Attaches a new graph observer to this graph data source. Observers will be notified in the order they have been registered.
+     *
+     * @param observer the graph observer
+     */
+    public void attachObserver(IGraphObserver<V> observer);
+
+    /**
+     * Attaches a new graph observer to this graph data source as the first one.
+     * In the notification order this observer will be the first one as long as another call to this method happens.
+     *
+     * @param observer the graph observer
+     * @since 1.6
+     */
+    public void attachAsFirstObserver(IGraphObserver<V> observer);
+
+    /**
+     * Detaches an already registered graph observer from this graph data source.
+     *
+     * @param observer the graph observer
+     */
+    public void detachObserver(IGraphObserver<V> observer);
+
+    /**
+     * Returns the complete set of nodes in the graph data source.
+     *
+     * @return the set of all nodes
+     */
+    public Set<V> getAllNodes();
+
+    /**
+     * Returns the target nodes for the given source node.
+     * The returned data structure is an {@link IMultiset} because of potential parallel edges in the graph data source.
+     *
+     * The method must not return null.
+     *
+     * @param source the source node
+     * @return the multiset of target nodes
+     * @since 2.0
+     */
+    public IMemoryView<V> getTargetNodes(V source);
+}
diff --git a/subprojects/viatra-runtime-base-itc/src/main/java/tools/refinery/viatra/runtime/base/itc/igraph/IGraphObserver.java b/subprojects/viatra-runtime-base-itc/src/main/java/tools/refinery/viatra/runtime/base/itc/igraph/IGraphObserver.java
new file mode 100644
index 00000000..5cb2d9fa
--- /dev/null
+++ b/subprojects/viatra-runtime-base-itc/src/main/java/tools/refinery/viatra/runtime/base/itc/igraph/IGraphObserver.java
@@ -0,0 +1,55 @@
+/*******************************************************************************
+ * 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.igraph;
+
+/**
+ * Interface GraphObserver is used to observ the changes in a graph; edge and node insertion/deleteion.
+ * 
+ * @author Tamas Szabo
+ * 
+ */
+public interface IGraphObserver<V> {
+
+    /**
+     * Used to notify when an edge is inserted into the graph.
+     * 
+     * @param source
+     *            the source of the edge
+     * @param target
+     *            the target of the edge
+     */
+    public void edgeInserted(V source, V target);
+
+    /**
+     * Used to notify when an edge is deleted from the graph.
+     * 
+     * @param source
+     *            the source of the edge
+     * @param target
+     *            the target of the edge
+     */
+    public void edgeDeleted(V source, V target);
+
+    /**
+     * Used to notify when a node is inserted into the graph.
+     * 
+     * @param n
+     *            the node
+     */
+    public void nodeInserted(V n);
+
+    /**
+     * Used to notify when a node is deleted from the graph.
+     * 
+     * @param n
+     *            the node
+     */
+    public void nodeDeleted(V n);
+}
diff --git a/subprojects/viatra-runtime-base-itc/src/main/java/tools/refinery/viatra/runtime/base/itc/igraph/ITcDataSource.java b/subprojects/viatra-runtime-base-itc/src/main/java/tools/refinery/viatra/runtime/base/itc/igraph/ITcDataSource.java
new file mode 100644
index 00000000..5924b723
--- /dev/null
+++ b/subprojects/viatra-runtime-base-itc/src/main/java/tools/refinery/viatra/runtime/base/itc/igraph/ITcDataSource.java
@@ -0,0 +1,82 @@
+/*******************************************************************************
+ * 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.igraph;
+
+import java.util.Set;
+
+import tools.refinery.viatra.runtime.base.itc.alg.misc.IGraphPathFinder;
+
+/**
+ * This interface defines those methods that a transitive reachability data source should provide. 
+ * 
+ * @author Tamas Szabo
+ * 
+ * @param <V>
+ *            the type parameter of the node
+ */
+public interface ITcDataSource<V> {
+
+    /**
+     * Attach a transitive closure relation observer.
+     * 
+     * @param to
+     *            the observer object
+     */
+    public void attachObserver(ITcObserver<V> to);
+
+    /**
+     * Detach a transitive closure relation observer.
+     * 
+     * @param to
+     *            the observer object
+     */
+    public void detachObserver(ITcObserver<V> to);
+
+    /**
+     * Returns all nodes which are reachable from the source node.
+     * 
+     * @param source
+     *            the source node
+     * @return the set of target nodes
+     */
+    public Set<V> getAllReachableTargets(V source);
+
+    /**
+     * Returns all nodes from which the target node is reachable.
+     * 
+     * @param target
+     *            the target node
+     * @return the set of source nodes
+     */
+    public Set<V> getAllReachableSources(V target);
+
+    /**
+     * Returns true if the target node is reachable from the source node.
+     * 
+     * @param source
+     *            the source node
+     * @param target
+     *            the target node
+     * @return true if target is reachable from source, false otherwise
+     */
+    public boolean isReachable(V source, V target);
+    
+    /**
+     * The returned {@link IGraphPathFinder} can be used to retrieve paths between nodes using transitive reachability.
+     * 
+     * @return a path finder for the graph.
+     */
+    public IGraphPathFinder<V> getPathFinder();
+    
+    /**
+     * Call this method to properly dispose the data structures of a transitive closure algorithm.
+     */
+    public void dispose();
+}
diff --git a/subprojects/viatra-runtime-base-itc/src/main/java/tools/refinery/viatra/runtime/base/itc/igraph/ITcObserver.java b/subprojects/viatra-runtime-base-itc/src/main/java/tools/refinery/viatra/runtime/base/itc/igraph/ITcObserver.java
new file mode 100644
index 00000000..fded53f1
--- /dev/null
+++ b/subprojects/viatra-runtime-base-itc/src/main/java/tools/refinery/viatra/runtime/base/itc/igraph/ITcObserver.java
@@ -0,0 +1,39 @@
+/*******************************************************************************
+ * 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.igraph;
+
+/**
+ * Interface ITcObserver is used to observe the changes in a transitive closure relation; tuple insertion/deletion.
+ * 
+ * @author Szabo Tamas
+ * 
+ */
+public interface ITcObserver<V> {
+
+    /**
+     * Used to notify when a tuple is inserted into the transitive closure relation.
+     * 
+     * @param source
+     *            the source of the tuple
+     * @param target
+     *            the target of the tuple
+     */
+    public void tupleInserted(V source, V target);
+
+    /**
+     * Used to notify when a tuple is deleted from the transitive closure relation.
+     * 
+     * @param source
+     *            the source of the tuple
+     * @param target
+     *            the target of the tuple
+     */
+    public void tupleDeleted(V source, V target);
+}