From 6e11ebab0aa0dca1de5475761978073dd849aa36 Mon Sep 17 00:00:00 2001 From: Kristóf Marussy Date: Sat, 19 Aug 2023 03:56:39 +0200 Subject: refactor: move ITC algorithms Since only RETE uses ITC, we may move ITC into the RETE project. Also removes unused ITC algorithms. --- .../runtime/base/itc/alg/counting/CountingAlg.java | 226 -------- .../base/itc/alg/counting/CountingTcRelation.java | 259 --------- .../viatra/runtime/base/itc/alg/dred/DRedAlg.java | 308 ---------- .../runtime/base/itc/alg/dred/DRedTcRelation.java | 223 ------- .../runtime/base/itc/alg/fw/FloydWarshallAlg.java | 110 ---- .../base/itc/alg/incscc/CountingListener.java | 36 -- .../runtime/base/itc/alg/incscc/IncSCCAlg.java | 645 --------------------- .../runtime/base/itc/alg/misc/DFSPathFinder.java | 146 ----- .../viatra/runtime/base/itc/alg/misc/Edge.java | 38 -- .../runtime/base/itc/alg/misc/GraphHelper.java | 173 ------ .../base/itc/alg/misc/IGraphPathFinder.java | 67 --- .../runtime/base/itc/alg/misc/ITcRelation.java | 31 - .../viatra/runtime/base/itc/alg/misc/Tuple.java | 60 -- .../viatra/runtime/base/itc/alg/misc/bfs/BFS.java | 151 ----- .../runtime/base/itc/alg/misc/dfs/DFSAlg.java | 93 --- .../runtime/base/itc/alg/misc/scc/PKAlg.java | 179 ------ .../viatra/runtime/base/itc/alg/misc/scc/SCC.java | 146 ----- .../runtime/base/itc/alg/misc/scc/SCCProperty.java | 37 -- .../runtime/base/itc/alg/misc/scc/SCCResult.java | 81 --- .../itc/alg/misc/topsort/TopologicalSorting.java | 77 --- .../RepresentativeElectionAlgorithm.java | 140 ----- .../alg/representative/RepresentativeObserver.java | 12 - .../StronglyConnectedComponentAlgorithm.java | 66 --- .../WeaklyConnectedComponentAlgorithm.java | 85 --- .../base/itc/alg/util/CollectionHelper.java | 64 -- .../runtime/base/itc/graphimpl/DotGenerator.java | 160 ----- .../viatra/runtime/base/itc/graphimpl/Graph.java | 185 ------ .../itc/igraph/IBiDirectionalGraphDataSource.java | 37 -- .../base/itc/igraph/IBiDirectionalWrapper.java | 110 ---- .../runtime/base/itc/igraph/IGraphDataSource.java | 70 --- .../runtime/base/itc/igraph/IGraphObserver.java | 55 -- .../runtime/base/itc/igraph/ITcDataSource.java | 82 --- .../runtime/base/itc/igraph/ITcObserver.java | 39 -- 33 files changed, 4191 deletions(-) delete mode 100644 subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/counting/CountingAlg.java delete mode 100644 subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/counting/CountingTcRelation.java delete mode 100644 subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/dred/DRedAlg.java delete mode 100644 subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/dred/DRedTcRelation.java delete mode 100644 subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/fw/FloydWarshallAlg.java delete mode 100644 subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/incscc/CountingListener.java delete mode 100644 subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/incscc/IncSCCAlg.java delete mode 100644 subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/misc/DFSPathFinder.java delete mode 100644 subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/misc/Edge.java delete mode 100644 subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/misc/GraphHelper.java delete mode 100644 subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/misc/IGraphPathFinder.java delete mode 100644 subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/misc/ITcRelation.java delete mode 100644 subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/misc/Tuple.java delete mode 100644 subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/misc/bfs/BFS.java delete mode 100644 subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/misc/dfs/DFSAlg.java delete mode 100644 subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/misc/scc/PKAlg.java delete mode 100644 subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/misc/scc/SCC.java delete mode 100644 subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/misc/scc/SCCProperty.java delete mode 100644 subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/misc/scc/SCCResult.java delete mode 100644 subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/misc/topsort/TopologicalSorting.java delete mode 100644 subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/representative/RepresentativeElectionAlgorithm.java delete mode 100644 subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/representative/RepresentativeObserver.java delete mode 100644 subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/representative/StronglyConnectedComponentAlgorithm.java delete mode 100644 subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/representative/WeaklyConnectedComponentAlgorithm.java delete mode 100644 subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/util/CollectionHelper.java delete mode 100644 subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/graphimpl/DotGenerator.java delete mode 100644 subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/graphimpl/Graph.java delete mode 100644 subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/igraph/IBiDirectionalGraphDataSource.java delete mode 100644 subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/igraph/IBiDirectionalWrapper.java delete mode 100644 subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/igraph/IGraphDataSource.java delete mode 100644 subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/igraph/IGraphObserver.java delete mode 100644 subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/igraph/ITcDataSource.java delete mode 100644 subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/igraph/ITcObserver.java (limited to 'subprojects/viatra-runtime/src') diff --git a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/counting/CountingAlg.java b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/counting/CountingAlg.java deleted file mode 100644 index d0367cde..00000000 --- a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/counting/CountingAlg.java +++ /dev/null @@ -1,226 +0,0 @@ -/******************************************************************************* - * 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 - * the type parameter of the nodes in the graph data source - */ -public class CountingAlg implements IGraphObserver, ITcDataSource { - - private CountingTcRelation tc = null; - private IBiDirectionalGraphDataSource gds = null; - private List> 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 gds) { - - if (gds instanceof IBiDirectionalGraphDataSource) { - this.gds = (IBiDirectionalGraphDataSource) gds; - } else { - this.gds = new IBiDirectionalWrapper(gds); - } - - observers = CollectionsFactory.>createObserverList(); - tc = new CountingTcRelation(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 dtc = new CountingTcRelation(false); - Set 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 newTuples = dtc; - CountingTcRelation tmp = null; - dtc = new CountingTcRelation(false); - - IMemoryView 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 getTcRelation() { - return this.tc; - } - - public void setTcRelation(CountingTcRelation tc) { - this.tc = tc; - } - - @Override - public boolean isReachable(V source, V target) { - return tc.containsTuple(source, target); - } - - @Override - public void attachObserver(ITcObserver to) { - this.observers.add(to); - - } - - @Override - public void detachObserver(ITcObserver to) { - this.observers.remove(to); - } - - @Override - public Set getAllReachableTargets(V source) { - return tc.getTupleEnds(source); - } - - @Override - public Set getAllReachableSources(V target) { - return tc.getTupleStarts(target); - } - - private void notifyTcObservers(V source, V target, boolean isInsertion) { - if (isInsertion) { - for (ITcObserver o : observers) { - o.tupleInserted(source, target); - } - } else { - for (ITcObserver o : observers) { - o.tupleDeleted(source, target); - } - } - } - - @Override - public void dispose() { - tc.clear(); - this.gds.detachObserver(this); - } - - @Override - public IGraphPathFinder getPathFinder() { - return new DFSPathFinder(gds, this); - } -} \ No newline at end of file diff --git a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/counting/CountingTcRelation.java b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/counting/CountingTcRelation.java deleted file mode 100644 index 44abbc3d..00000000 --- a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/counting/CountingTcRelation.java +++ /dev/null @@ -1,259 +0,0 @@ -/******************************************************************************* - * 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.topsort.TopologicalSorting; -import tools.refinery.viatra.runtime.base.itc.alg.misc.ITcRelation; -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 - */ -public class CountingTcRelation implements ITcRelation { - - private IMultiLookup tuplesForward = null; - private IMultiLookup 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 rA) { - IMultiLookup rForward = rA.tuplesForward; - for (V source : rForward.distinctKeys()) { - IMemoryView targetBag = rForward.lookup(source); - for (V target : targetBag.distinctValues()) { - this.addTuple(source, target, targetBag.getCount(target)); - } - } - } - - public int getCount(V source, V target) { - IMemoryView 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 sourcesToDelete = CollectionsFactory.createSet(); - Set 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 targets = tuplesForward.lookup(source); - for (V target : targets.distinctValues()) { - sb.append("{(" + source + "," + target + ")," + targets.getCount(target) + "} "); - } - } - - return sb.toString(); - } - - @Override - public Set getTupleEnds(V source) { - IMemoryView 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 getTupleStarts(V target) { - if (tuplesBackward != null) { - IMemoryView tupStarts = tuplesBackward.lookup(target); - if (tupStarts == null) - return null; - return tupStarts.distinctValues(); - } else { - throw new UnsupportedOperationException("built without backward indexing"); - } - } - - @Override - public Set getTupleStarts() { - Set 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 aTR = (CountingTcRelation) obj; - - return tuplesForward.equals(aTR.tuplesForward); - } - } - - @Override - public int hashCode() { - return tuplesForward.hashCode(); - } - - public static CountingTcRelation createFrom(IBiDirectionalGraphDataSource gds) { - List topologicalSorting = TopologicalSorting.compute(gds); - CountingTcRelation tc = new CountingTcRelation(true); - Collections.reverse(topologicalSorting); - for (V n : topologicalSorting) { - IMemoryView sourceNodes = gds.getSourceNodes(n); - Set 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/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/dred/DRedAlg.java b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/dred/DRedAlg.java deleted file mode 100644 index b92d08bf..00000000 --- a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/dred/DRedAlg.java +++ /dev/null @@ -1,308 +0,0 @@ -/******************************************************************************* - * 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 - * the type parameter of the nodes in the graph data source - */ -public class DRedAlg implements IGraphObserver, ITcDataSource { - - private IGraphDataSource graphDataSource = null; - private DRedTcRelation tc = null; - private DRedTcRelation dtc = null; - private List> 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 gds) { - this.observers = new ArrayList>(); - this.graphDataSource = gds; - this.tc = new DRedTcRelation(); - this.dtc = new DRedTcRelation(); - 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 gds, DRedTcRelation tc) { - this.graphDataSource = gds; - this.tc = tc; - this.dtc = new DRedTcRelation(); - graphDataSource.attachObserver(this); - } - - /** - * Initializes the transitive closure relation. - */ - private void initTc() { - DFSAlg dfsa = new DFSAlg(this.graphDataSource); - this.setTcRelation(dfsa.getTcRelation()); - this.graphDataSource.detachObserver(dfsa); - } - - @Override - public void edgeInserted(V source, V target) { - if (!source.equals(target)) { - Set tupStarts = null; - Set tupEnds = null; - Set> tuples = new HashSet>(); - - if (!source.equals(target) && tc.addTuple(source, target)) { - tuples.add(new Tuple(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(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(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(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, Integer> tuples = new HashMap, Integer>(); - Set sources = tc.getTupleStarts(source); - Set targets = tc.getTupleEnds(target); - - tc.removeTuple(source, target); - tuples.put(new Tuple(source, target), -1); - - for (V s : sources) { - for (V t : targets) { - if (!s.equals(t)) { - tc.removeTuple(s, t); - tuples.put(new Tuple(s, t), -1); - } - } - } - - for (V s : sources) { - if (!s.equals(target)) { - tc.removeTuple(s, target); - tuples.put(new Tuple(s, target), -1); - } - } - - for (V t : targets) { - if (!source.equals(t)) { - tc.removeTuple(source, t); - tuples.put(new Tuple(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 targetNodes = graphDataSource.getTargetNodes(s); - for (Entry entry : targetNodes.entriesWithMultiplicities()) { - for (int i = 0; i < entry.getValue(); i++) { - V t = entry.getKey(); - if (!s.equals(t)) { - tc.addTuple(s, t); - Tuple tuple = new Tuple(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 newTups = new DRedTcRelation(); - 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 targetNodes = graphDataSource.getTargetNodes(t); - if (targetNodes != null) { - for (Entry 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(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 set = tc.getTupleEnds(n); - Set modSet = null; - - // n -> target - modSet = new HashSet(set); - - for (V tn : modSet) { - this.tc.removeTuple(n, tn); - } - - // source -> n - set = tc.getTupleStarts(n); - - modSet = new HashSet(set); - - for (V sn : modSet) { - this.tc.removeTuple(sn, n); - } - } - - public DRedTcRelation getTcRelation() { - return this.tc; - } - - public void setTcRelation(DRedTcRelation tc) { - this.tc = tc; - } - - @Override - public boolean isReachable(V source, V target) { - return tc.containsTuple(source, target); - } - - @Override - public void attachObserver(ITcObserver to) { - this.observers.add(to); - } - - @Override - public void detachObserver(ITcObserver to) { - this.observers.remove(to); - } - - @Override - public Set getAllReachableTargets(V source) { - return tc.getTupleEnds(source); - } - - @Override - public Set getAllReachableSources(V target) { - return tc.getTupleStarts(target); - } - - protected void notifyTcObservers(Set> tuples, int dir) { - for (ITcObserver o : observers) { - for (Tuple 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 getPathFinder() { - return new DFSPathFinder(graphDataSource, this); - } -} diff --git a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/dred/DRedTcRelation.java b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/dred/DRedTcRelation.java deleted file mode 100644 index 8543b79c..00000000 --- a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/dred/DRedTcRelation.java +++ /dev/null @@ -1,223 +0,0 @@ -/******************************************************************************* - * 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 implements ITcRelation { - - // tc(a,b) means that b is transitively reachable from a - private Map> tuplesForward; - - // data structure to efficiently get those nodes from which a given node is reachable - // symmetric to tuplesForward - private Map> tuplesBackward; - - public DRedTcRelation() { - this.tuplesForward = new HashMap>(); - this.tuplesBackward = new HashMap>(); - } - - 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 sSet = tuplesForward.get(source); - if (sSet != null) { - sSet.remove(target); - if (sSet.size() == 0) - tuplesForward.remove(source); - } - - // removing tuple from 'backward' tc relation - Set 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 sSet = tuplesForward.get(source); - if (sSet == null) { - Set newSet = new HashSet(); - newSet.add(target); - tuplesForward.put(source, newSet); - } else { - sSet.add(target); - } - - // adding tuple to 'backward' tc relation - Set tSet = tuplesBackward.get(target); - if (tSet == null) { - Set newSet = new HashSet(); - 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 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 rA) { - for (V source : rA.tuplesForward.keySet()) { - for (V target : rA.tuplesForward.get(source)) { - this.removeTuple(source, target); - } - } - } - - @Override - public Set getTupleEnds(V source) { - Set t = tuplesForward.get(source); - return (t == null) ? new HashSet() : new HashSet(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 getTupleStarts(V target) { - Set t = tuplesBackward.get(target); - return (t == null) ? new HashSet() : new HashSet(t); - } - - @Override - public Set getTupleStarts() { - Set t = tuplesForward.keySet(); - return new HashSet(t); - } - - @Override - public String toString() { - StringBuilder sb = new StringBuilder("TcRelation = "); - - for (Entry> 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 aTR = (DRedTcRelation) obj; - - for (Entry> entry : aTR.tuplesForward.entrySet()) { - V source = entry.getKey(); - for (V target : entry.getValue()) { - if (!this.containsTuple(source, target)) - return false; - } - } - - for (Entry> 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> getTuplesForward() { - return tuplesForward; - } -} diff --git a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/fw/FloydWarshallAlg.java b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/fw/FloydWarshallAlg.java deleted file mode 100644 index 8b8908b1..00000000 --- a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/fw/FloydWarshallAlg.java +++ /dev/null @@ -1,110 +0,0 @@ -/******************************************************************************* - * 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.IGraphDataSource; -import tools.refinery.viatra.runtime.base.itc.igraph.IGraphObserver; -import tools.refinery.viatra.runtime.base.itc.igraph.IBiDirectionalGraphDataSource; -import tools.refinery.viatra.runtime.base.itc.igraph.IBiDirectionalWrapper; -import tools.refinery.viatra.runtime.matchers.util.IMemoryView; - -public class FloydWarshallAlg implements IGraphObserver { - - private DRedTcRelation tc = null; - private IBiDirectionalGraphDataSource gds = null; - - public FloydWarshallAlg(IGraphDataSource gds) { - if (gds instanceof IBiDirectionalGraphDataSource) { - this.gds = (IBiDirectionalGraphDataSource) gds; - } else { - this.gds = new IBiDirectionalWrapper(gds); - } - - this.tc = new DRedTcRelation(); - gds.attachObserver(this); - generateTc(); - } - - private void generateTc() { - - tc.clear(); - - int n = gds.getAllNodes().size(); - Map mapForw = new HashMap(); - Map mapBackw = new HashMap(); - 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 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 getTcRelation() { - return this.tc; - } -} diff --git a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/incscc/CountingListener.java b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/incscc/CountingListener.java deleted file mode 100644 index fdf64f77..00000000 --- a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/incscc/CountingListener.java +++ /dev/null @@ -1,36 +0,0 @@ -/******************************************************************************* - * 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 implements ITcObserver { - - private IncSCCAlg alg; - - public CountingListener(IncSCCAlg 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/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/incscc/IncSCCAlg.java b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/incscc/IncSCCAlg.java deleted file mode 100644 index 5d720e75..00000000 --- a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/incscc/IncSCCAlg.java +++ /dev/null @@ -1,645 +0,0 @@ -/******************************************************************************* - * 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.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.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.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 - * the type parameter of the nodes in the graph data source - */ -public class IncSCCAlg implements IGraphObserver, ITcDataSource { - - public UnionFind sccs; - public IBiDirectionalGraphDataSource gds; - private CountingAlg counting; - private Graph reducedGraph; - private IBiDirectionalGraphDataSource reducedGraphIndexer; - private List> observers; - private CountingListener countingListener; - - public IncSCCAlg(IGraphDataSource graphDataSource) { - - if (graphDataSource instanceof IBiDirectionalGraphDataSource) { - gds = (IBiDirectionalGraphDataSource) graphDataSource; - } else { - gds = new IBiDirectionalWrapper(graphDataSource); - } - observers = CollectionsFactory.createObserverList(); - sccs = new UnionFind(); - reducedGraph = new Graph(); - reducedGraphIndexer = new IBiDirectionalWrapper(reducedGraph); - countingListener = new CountingListener(this); - initalizeInternalDataStructures(); - gds.attachObserver(this); - } - - private void initalizeInternalDataStructures() { - SCCResult _sccres = SCC.computeSCC(gds); - Set> _sccs = _sccres.getSccs(); - - for (Set _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 targetNodes = gds.getTargetNodes(source); - for (Entry 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(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 predecessorRoots = counting.getAllReachableSources(sourceRoot); - Set successorRoots = counting.getAllReachableTargets(targetRoot); - - // 1. intersection of source and target roots, these will be in the merged SCC - Set isectRoots = CollectionHelper.intersection(predecessorRoots, successorRoots); - isectRoots.add(sourceRoot); - isectRoots.add(targetRoot); - - // notifications must be issued before Union-Find modifications - if (observers.size() > 0) { - Set sourceSCCs = createSetNullTolerant(predecessorRoots); - sourceSCCs.add(sourceRoot); - Set 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 sourceSCCs = new ArrayList(); - List targetSCCs = new ArrayList(); - - for (V r : isectRoots) { - List sourceSCCsOfSCC = getSourceSCCsOfSCC(r); - List 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 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 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 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 reachableSources = CollectionsFactory.createMap(); - for (Entry entry : reducedGraphIndexer.getSourceNodes(sourceRoot).entriesWithMultiplicities()) { - reachableSources.put(entry.getKey(), entry.getValue()); - } - Map reachableTargets = CollectionsFactory.createMap(); - for (Entry entry : reducedGraphIndexer.getTargetNodes(sourceRoot).entriesWithMultiplicities()) { - reachableTargets.put(entry.getKey(), entry.getValue()); - } - - SCCResult _newSccs = SCC.computeSCC(g); - - // delete scc node (and with its edges too) - for (Entry entry : reachableSources.entrySet()) { - V s = entry.getKey(); - for (int i = 0; i < entry.getValue(); i++) { - reducedGraph.deleteEdgeIfExists(s, sourceRoot); - } - } - - for (Entry 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> newSCCs = _newSccs.getSccs(); - Set newSCCRoots = CollectionsFactory.createSet(); - - // add new nodes and edges to the reduced graph - for (Set newSCC : newSCCs) { - V newRoot = sccs.makeSet(newSCC); - reducedGraph.insertNode(newRoot); - newSCCRoots.add(newRoot); - } - for (V newSCCRoot : newSCCRoots) { - List sourceSCCsOfSCC = getSourceSCCsOfSCC(newSCCRoot); - List 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 sourceSCCs = createSetNullTolerant(counting.getAllReachableSources(newSourceRoot)); - sourceSCCs.add(newSourceRoot); - - Set 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 sources = gds.getSourceNodes(n); - IMemoryView targets = gds.getTargetNodes(n); - - for (Entry entry : sources.entriesWithMultiplicities()) { - for (int i = 0; i < entry.getValue(); i++) { - V source = entry.getKey(); - edgeDeleted(source, n); - } - } - - for (Entry 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 to) { - observers.add(to); - } - - @Override - public void detachObserver(ITcObserver to) { - observers.remove(to); - } - - @Override - public Set getAllReachableTargets(V source) { - V sourceRoot = sccs.find(source); - Set containedNodes = sccs.getPartition(sourceRoot); - Set targets = CollectionsFactory.createSet(); - - if (containedNodes.size() > 1 || GraphHelper.getEdgeCount(source, gds) == 1) { - targets.addAll(containedNodes); - } - - Set rootSet = counting.getAllReachableTargets(sourceRoot); - if (rootSet != null) { - for (V _root : rootSet) { - targets.addAll(sccs.getPartition(_root)); - } - } - - return targets; - } - - @Override - public Set getAllReachableSources(V target) { - V targetRoot = sccs.find(target); - Set containedNodes = sccs.getPartition(targetRoot); - Set sources = CollectionsFactory.createSet(); - - if (containedNodes.size() > 1 || GraphHelper.getEdgeCount(target, gds) == 1) { - sources.addAll(containedNodes); - } - - Set 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 getReachabilityPath(V source, V target) { - if (!isReachable(source, target)) { - return null; - } else { - Set sccsInSubGraph = CollectionHelper.intersection(counting.getAllReachableTargets(source), - counting.getAllReachableSources(target)); - sccsInSubGraph.add(sccs.find(source)); - sccsInSubGraph.add(sccs.find(target)); - Set 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 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 getSourceSCCsOfSCC(V root) { - List sourceSCCs = new ArrayList(); - - for (V containedNode : this.sccs.getPartition(root)) { - IMemoryView 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 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 getTargetSCCsOfSCC(V root) { - List targetSCCs = new ArrayList(); - - for (V containedNode : this.sccs.getPartition(root)) { - IMemoryView 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 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 sources, Set 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 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> getTcRelation() { - Set> resultSet = new HashSet>(); - - for (V sourceRoot : sccs.getPartitionHeads()) { - Set 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(source, target)); - } - } - } - - Set 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(source, target)); - } - } - } - } - } - - return resultSet; - } - - public boolean isIsolated(V node) { - IMemoryView targets = gds.getTargetNodes(node); - IMemoryView sources = gds.getSourceNodes(node); - return targets.isEmpty() && sources.isEmpty(); - } - - @Override - public IGraphPathFinder getPathFinder() { - return new DFSPathFinder(gds, this); - } - - /** - * The graph of SCCs; each SCC is represented by its representative node (see {@link #getRepresentative(Object)}) - * @since 1.6 - */ - public Graph getReducedGraph() { - return reducedGraph; - } - - private static Set createSetNullTolerant(Set initial) { - if (initial != null) - return CollectionsFactory.createSet(initial); - else - return CollectionsFactory.createSet(); - } - - -} diff --git a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/misc/DFSPathFinder.java b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/misc/DFSPathFinder.java deleted file mode 100644 index 51017b1a..00000000 --- a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/misc/DFSPathFinder.java +++ /dev/null @@ -1,146 +0,0 @@ -/******************************************************************************* - * 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 - * the node type of the graph - */ -public class DFSPathFinder implements IGraphPathFinder { - - private IGraphDataSource graph; - private ITcDataSource itc; - - public DFSPathFinder(IGraphDataSource graph, ITcDataSource itc) { - this.graph = graph; - this.itc = itc; - } - - @Override - public Iterable> getAllPaths(V sourceNode, V targetNode) { - Set endNodes = new HashSet(); - endNodes.add(targetNode); - return getAllPathsToTargets(sourceNode, endNodes); - } - - @Override - public Iterable> getAllPathsToTargets(V sourceNode, Set targetNodes) { - List> paths = new ArrayList>(); - Deque visited = new LinkedList(); - Set reachableTargets = new HashSet(); - 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> getPaths(List> paths, Deque visited, Set targetNodes) { - IMemoryView 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 visitedClone = new LinkedList(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> paths) { - StringBuilder sb = new StringBuilder(); - for (Deque visited : paths) { - sb.append("Path: "); - for (V node : visited) { - sb.append(node); - sb.append(" --> "); - } - sb.append("\n"); - } - return sb.toString(); - } - - @Override - public Deque getPath(V sourceNode, V targetNode) { - // TODO optimize - Iterable> allPaths = getAllPaths(sourceNode, targetNode); - Iterator> pathIterator = allPaths.iterator(); - return pathIterator.hasNext() ? pathIterator.next() : new LinkedList(); - } - - @Override - public Iterable> getShortestPaths(V sourceNode, V targetNode) { - // TODO optimize - Iterable> allPaths = getAllPaths(sourceNode, targetNode); - List> shortestPaths = new ArrayList>(); - int shortestPathLength = -1; - for (Deque path : allPaths) { - int pathLength = path.size(); - if (shortestPathLength == -1 || pathLength < shortestPathLength) { - shortestPaths.clear(); - shortestPathLength = pathLength; - } - if (pathLength == shortestPathLength) { - shortestPaths.add(path); - } - } - return shortestPaths; - } - -} diff --git a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/misc/Edge.java b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/misc/Edge.java deleted file mode 100644 index cf68d36a..00000000 --- a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/misc/Edge.java +++ /dev/null @@ -1,38 +0,0 @@ -/******************************************************************************* - * 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 { - private V source; - private V target; - - public Edge(V source, V target) { - super(); - this.source = source; - this.target = target; - } - - public V getSource() { - return source; - } - - public void setSource(V source) { - this.source = source; - } - - public V getTarget() { - return target; - } - - public void setTarget(V target) { - this.target = target; - } - -} diff --git a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/misc/GraphHelper.java b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/misc/GraphHelper.java deleted file mode 100644 index 194e979b..00000000 --- a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/misc/GraphHelper.java +++ /dev/null @@ -1,173 +0,0 @@ -/******************************************************************************* - * 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 Graph getSubGraph(Collection nodesInSubGraph, - IBiDirectionalGraphDataSource graphDataSource) { - Graph g = new Graph(); - if (nodesInSubGraph != null) { - for (V node : nodesInSubGraph) { - g.insertNode(node); - } - - for (V node : nodesInSubGraph) { - IMemoryView sources = graphDataSource.getSourceNodes(node); - for (Entry 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 List constructPath(V source, V target, Set nodesInGraph, - IGraphDataSource graphDataSource) { - Set visitedNodes = new HashSet(); - List path = new ArrayList(); - - 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 getNextNodeToVisit(V act, IGraphDataSource graphDataSource, Set nodesInSubGraph, - Set visitedNodes) { - IMemoryView targetNodes = graphDataSource.getTargetNodes(act); - for (Entry 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 int getEdgeCount(V node, IGraphDataSource 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 int getEdgeCount(V source, V target, IGraphDataSource graphDataSource) { - Integer count = graphDataSource.getTargetNodes(source).getCount(target); - if (count == null) { - return 0; - } else { - return count; - } - } -} diff --git a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/misc/IGraphPathFinder.java b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/misc/IGraphPathFinder.java deleted file mode 100644 index cebb09c8..00000000 --- a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/misc/IGraphPathFinder.java +++ /dev/null @@ -1,67 +0,0 @@ -/******************************************************************************* - * 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 the node type of the graph - */ -public interface IGraphPathFinder { - - /** - * 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 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> 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> 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> getAllPathsToTargets(V sourceNode, Set targetNodes); - - -} \ No newline at end of file diff --git a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/misc/ITcRelation.java b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/misc/ITcRelation.java deleted file mode 100644 index a41ff6c7..00000000 --- a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/misc/ITcRelation.java +++ /dev/null @@ -1,31 +0,0 @@ -/******************************************************************************* - * 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 { - - /** - * Returns the starting nodes from a transitive closure relation. - * - * @return the set of starting nodes - */ - public Set 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 getTupleEnds(V start); -} diff --git a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/misc/Tuple.java b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/misc/Tuple.java deleted file mode 100644 index a2d54a59..00000000 --- a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/misc/Tuple.java +++ /dev/null @@ -1,60 +0,0 @@ -/******************************************************************************* - * 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 { - - private V source; - private V target; - - public Tuple(V source, V target) { - super(); - this.source = source; - this.target = target; - } - - public V getSource() { - return source; - } - - public void setSource(V source) { - this.source = source; - } - - public V getTarget() { - return target; - } - - public void setTarget(V target) { - this.target = target; - } - - @Override - public String toString() { - return "(" + source.toString() + "," + target.toString() + ")"; - } - - @Override - public boolean equals(Object o) { - if (o instanceof Tuple) { - Tuple t = (Tuple) o; - - if (t.getSource().equals(this.source) && t.getTarget().equals(this.target)) { - return true; - } - } - return false; - } - - @Override - public int hashCode() { - return source.hashCode() + target.hashCode(); - } -} diff --git a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/misc/bfs/BFS.java b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/misc/bfs/BFS.java deleted file mode 100644 index 798f31d2..00000000 --- a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/misc/bfs/BFS.java +++ /dev/null @@ -1,151 +0,0 @@ -/******************************************************************************* - * 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 { - - private BFS() {/*Utility class constructor*/} - - /** - * Performs a breadth first search on the given graph to determine whether source is reachable from target. - * - * @param - * 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 boolean isReachable(V source, V target, IGraphDataSource graph) { - List nodeQueue = new ArrayList(); - Set visited = new HashSet(); - - nodeQueue.add(source); - visited.add(source); - - boolean ret = _isReachable(target, graph, nodeQueue, visited); - return ret; - } - - private static boolean _isReachable(V target, IGraphDataSource graph, List nodeQueue, Set 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 Set reachableSources(IBiDirectionalGraphDataSource graph, V target) { - Set retSet = new HashSet(); - retSet.add(target); - List nodeQueue = new ArrayList(); - nodeQueue.add(target); - - _reachableSources(graph, nodeQueue, retSet); - - return retSet; - } - - private static void _reachableSources(IBiDirectionalGraphDataSource graph, List nodeQueue, - Set 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 Set reachableTargets(IGraphDataSource graph, V source) { - Set retSet = new HashSet(); - retSet.add(source); - List nodeQueue = new ArrayList(); - nodeQueue.add(source); - - _reachableTargets(graph, nodeQueue, retSet); - - return retSet; - } - - private static void _reachableTargets(IGraphDataSource graph, List nodeQueue, Set 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 - * 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 Set collectNodesAlongPath(V source, V target, IGraphDataSource graph) { - Set path = new HashSet(); - _collectNodesAlongPath(source, target, graph, path); - return path; - } - - private static boolean _collectNodesAlongPath(V node, V target, IGraphDataSource graph, Set path) { - - boolean res = false; - - // end recursion - if (node.equals(target)) { - path.add(node); - return true; - } else { - for (V _nodeT : graph.getTargetNodes(node).distinctValues()) { - res = (_collectNodesAlongPath(_nodeT, target, graph, path)) || res; - } - if (res) - path.add(node); - return res; - } - } -} diff --git a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/misc/dfs/DFSAlg.java b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/misc/dfs/DFSAlg.java deleted file mode 100644 index c8d25c4e..00000000 --- a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/misc/dfs/DFSAlg.java +++ /dev/null @@ -1,93 +0,0 @@ -/******************************************************************************* - * 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 implements IGraphObserver { - - private IGraphDataSource gds; - private DRedTcRelation tc; - private int[] visited; - private HashMap nodeMap; - - public DFSAlg(IGraphDataSource gds) { - this.gds = gds; - this.tc = new DRedTcRelation(); - gds.attachObserver(this); - deriveTc(); - } - - private void deriveTc() { - tc.clear(); - - this.visited = new int[gds.getAllNodes().size()]; - nodeMap = new HashMap(); - - 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 getTcRelation() { - return this.tc; - } - - @Override - public void edgeInserted(V source, V target) { - deriveTc(); - } - - @Override - public void edgeDeleted(V source, V target) { - deriveTc(); - } - - @Override - public void nodeInserted(V n) { - deriveTc(); - } - - @Override - public void nodeDeleted(V n) { - deriveTc(); - } -} diff --git a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/misc/scc/PKAlg.java b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/misc/scc/PKAlg.java deleted file mode 100644 index c99a48ab..00000000 --- a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/misc/scc/PKAlg.java +++ /dev/null @@ -1,179 +0,0 @@ -/******************************************************************************* - * 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 implements IGraphObserver { - - /** - * Maps the nodes to their indicies. - */ - private Map node2index; - private Map index2node; - private Map node2mark; - - /** - * Maps the index of a node to the index in the topsort. - */ - private Map index2topsort; - private Map 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 RF; - private List RB; - private IBiDirectionalGraphDataSource gds; - - public PKAlg(IGraphDataSource gds) { - if (gds instanceof IBiDirectionalGraphDataSource) { - this.gds = (IBiDirectionalGraphDataSource) gds; - } else { - this.gds = new IBiDirectionalWrapper(gds); - } - - node2mark = new HashMap(); - node2index = new HashMap(); - index2node = new HashMap(); - index2topsort = new HashMap(); - topsort2index = new HashMap(); - index = 0; - - gds.attachObserver(this); - } - - @Override - public void edgeInserted(V source, V target) { - - RF = new ArrayList(); - RB = new ArrayList(); - - 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 getIndicies(List list) { - List indicies = new ArrayList(); - - 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 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 getTopSort() { - List topsort = new ArrayList(); - - for (int i : topsort2index.values()) { - topsort.add(index2node.get(i)); - } - - return topsort; - } - - private void dfsBackward(V node) { - node2mark.put(node, true); - RB.add(node); - - for (V sn : gds.getSourceNodes(node).distinctValues()) { - int top_id = index2topsort.get(node2index.get(sn)); - - if (!node2mark.get(sn) && lower_bound < top_id) - dfsBackward(sn); - } - } - - private void dfsForward(V node) { - node2mark.put(node, true); - RF.add(node); - - for (V tn : gds.getTargetNodes(node).distinctValues()) { - int top_id = index2topsort.get(node2index.get(tn)); - - if (top_id == upper_bound) - System.out.println("!!!Cycle detected!!!"); - else if (!node2mark.get(tn) && top_id < upper_bound) - dfsForward(tn); - } - } - - @Override - public void edgeDeleted(V source, V target) { - // Edge deletion does not affect topsort - } - - @Override - public void nodeInserted(V n) { - node2mark.put(n, false); - node2index.put(n, index); - index2node.put(index, n); - index2topsort.put(index, index); - topsort2index.put(index, index); - index++; - } - - @Override - public void nodeDeleted(V n) { - node2mark.remove(n); - int node_id = node2index.remove(n); - index2node.remove(node_id); - int top_id = index2topsort.remove(node_id); - topsort2index.remove(top_id); - } -} diff --git a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/misc/scc/SCC.java b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/misc/scc/SCC.java deleted file mode 100644 index 8915998b..00000000 --- a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/misc/scc/SCC.java +++ /dev/null @@ -1,146 +0,0 @@ -/******************************************************************************* - * 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 - * the type parameter of the nodes in the graph - */ -public class SCC { - - 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 SCCResult computeSCC(IGraphDataSource g) { - int index = 0; - Set> ret = new HashSet>(); - - // stores the lowlink and index information for the given node - Map nodeMap = CollectionsFactory.createMap(); - - // stores all target nodes of a given node - the list will be modified - Map> targetNodeMap = CollectionsFactory.createMap(); - - // stores those target nodes for a given node which have not been visited - Map> notVisitedMap = CollectionsFactory.createMap(); - - // stores the nodes during the traversal - Stack nodeStack = new Stack(); - - // stores the nodes which belong to an scc (there can be many sccs in the stack at the same time) - Stack sccStack = new Stack(); - - boolean sink = false, finishedTraversal = true; - - // initialize all nodes with 0 index and 0 lowlink - Set 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()); - - // storing the target nodes of the actual node - if (g.getTargetNodes(currentNode) != null) { - Set 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 sc = new HashSet(); - V targetNode = null; - - do { - targetNode = sccStack.pop(); - sc.add(targetNode); - } while (!targetNode.equals(currentNode)); - - ret.add(sc); - } - } - } - } - - return new SCCResult(ret, g); - } -} diff --git a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/misc/scc/SCCProperty.java b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/misc/scc/SCCProperty.java deleted file mode 100644 index b26e3d37..00000000 --- a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/misc/scc/SCCProperty.java +++ /dev/null @@ -1,37 +0,0 @@ -/******************************************************************************* - * Copyright (c) 2010-2012, Tamas Szabo, Istvan Rath and Daniel Varro - * This program and the accompanying materials are made available under the - * terms of the Eclipse Public License v. 2.0 which is available at - * http://www.eclipse.org/legal/epl-v20.html. - * - * SPDX-License-Identifier: EPL-2.0 - *******************************************************************************/ - -package tools.refinery.viatra.runtime.base.itc.alg.misc.scc; - -public class SCCProperty { - private int index; - private int lowlink; - - public SCCProperty(int index, int lowlink) { - super(); - this.index = index; - this.lowlink = lowlink; - } - - public int getIndex() { - return index; - } - - public void setIndex(int index) { - this.index = index; - } - - public int getLowlink() { - return lowlink; - } - - public void setLowlink(int lowlink) { - this.lowlink = lowlink; - } -} diff --git a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/misc/scc/SCCResult.java b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/misc/scc/SCCResult.java deleted file mode 100644 index fde59d3b..00000000 --- a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/misc/scc/SCCResult.java +++ /dev/null @@ -1,81 +0,0 @@ -/******************************************************************************* - * 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 { - - private Set> sccs; - private IGraphDataSource gds; - - public SCCResult(Set> sccs, IGraphDataSource gds) { - this.sccs = sccs; - this.gds = gds; - } - - public Set> getSccs() { - return sccs; - } - - public int getSCCCount() { - return sccs.size(); - } - - public double getAverageNodeCount() { - double a = 0; - - for (Set s : sccs) { - a += s.size(); - } - - return a / sccs.size(); - } - - public double getAverageEdgeCount() { - long edgeSum = 0; - - for (Set scc : sccs) { - for (V source : scc) { - for (Entry 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 scc : sccs) { - if (scc.size() > max) - max = scc.size(); - } - - return max; - } - - public long getSumOfSquares() { - long sum = 0; - - for (Set scc : sccs) { - sum += scc.size() * scc.size(); - } - - return sum; - } -} diff --git a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/misc/topsort/TopologicalSorting.java b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/misc/topsort/TopologicalSorting.java deleted file mode 100644 index dd18e6c8..00000000 --- a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/misc/topsort/TopologicalSorting.java +++ /dev/null @@ -1,77 +0,0 @@ -/******************************************************************************* - * 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 { - 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 a will come before node b in the resulting list. - * - * @param gds the graph data source - * @return a topological ordering - */ - public static List compute(final IGraphDataSource gds) { - final Set visited = new HashSet(); - final LinkedList result = new LinkedList(); - final Stack> dfsStack = new Stack>(); - - for (final T node : gds.getAllNodes()) { - if (!visited.contains(node)) { - dfsStack.push(new Pair(node, false)); - } - - while (!dfsStack.isEmpty()) { - final Pair 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(source, true)); - - for (final T target : gds.getTargetNodes(source).distinctValues()) { - if (!visited.contains(target)) { - dfsStack.push(new Pair(target, false)); - } - } - } - } - } - - return result; - } -} diff --git a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/representative/RepresentativeElectionAlgorithm.java b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/representative/RepresentativeElectionAlgorithm.java deleted file mode 100644 index 51015404..00000000 --- a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/representative/RepresentativeElectionAlgorithm.java +++ /dev/null @@ -1,140 +0,0 @@ -/* - * SPDX-FileCopyrightText: 2023 The Refinery Authors - * - * 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 { - protected final Graph graph; - protected final Map representatives = new HashMap<>(); - protected final Map> components = new HashMap<>(); - private RepresentativeObserver observer; - - protected RepresentativeElectionAlgorithm(Graph graph) { - this.graph = graph; - initializeComponents(); - graph.attachObserver(this); - } - - protected abstract void initializeComponents(); - - protected void initializeSet(Set 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 preservedSet, Object removedRepresentative, - Set 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 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> getComponents() { - return components; - } - - public Object getRepresentative(Object node) { - return representatives.get(node); - } - - public Set 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 graph); - } -} diff --git a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/representative/RepresentativeObserver.java b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/representative/RepresentativeObserver.java deleted file mode 100644 index 93cce1ea..00000000 --- a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/representative/RepresentativeObserver.java +++ /dev/null @@ -1,12 +0,0 @@ -/* - * SPDX-FileCopyrightText: 2023 The Refinery Authors - * - * 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/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/representative/StronglyConnectedComponentAlgorithm.java b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/representative/StronglyConnectedComponentAlgorithm.java deleted file mode 100644 index ba42bb13..00000000 --- a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/representative/StronglyConnectedComponentAlgorithm.java +++ /dev/null @@ -1,66 +0,0 @@ -/* - * SPDX-FileCopyrightText: 2023 The Refinery Authors - * - * 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 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> sets) { - for (var set : sets) { - if (set.contains(preservedRepresentative)) { - components.put(preservedRepresentative, set); - } else { - assignNewRepresentative(preservedRepresentative, set); - } - } - } -} diff --git a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/representative/WeaklyConnectedComponentAlgorithm.java b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/representative/WeaklyConnectedComponentAlgorithm.java deleted file mode 100644 index 22159499..00000000 --- a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/representative/WeaklyConnectedComponentAlgorithm.java +++ /dev/null @@ -1,85 +0,0 @@ -/* - * SPDX-FileCopyrightText: 2023 The Refinery Authors - * - * 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 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 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 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/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/util/CollectionHelper.java b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/util/CollectionHelper.java deleted file mode 100644 index c9b3cafa..00000000 --- a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/alg/util/CollectionHelper.java +++ /dev/null @@ -1,64 +0,0 @@ -/******************************************************************************* - * 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 Set intersection(Set set1, Set set2) { - if (set1 == null || set2 == null) - return CollectionsFactory.createSet(); - - Set 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 Set difference(Set set1, Set set2) { - if (set1 == null) - return CollectionsFactory.createSet(); - - Set difference = CollectionsFactory.createSet(set1); - if (set2 != null) difference.removeAll(set2); - return difference; - } - -} diff --git a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/graphimpl/DotGenerator.java b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/graphimpl/DotGenerator.java deleted file mode 100644 index 0e21f323..00000000 --- a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/graphimpl/DotGenerator.java +++ /dev/null @@ -1,160 +0,0 @@ -/******************************************************************************* - * 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 String generateDot(final Graph graph, final boolean colorSCCs, - final Function nameFunction, final Function colorFunction, - final Function> edgeFunction) { - final Map colorMap = new HashMap(); - - if (colorSCCs) { - final SCCResult result = SCC.computeSCC(graph); - final Set> sccs = result.getSccs(); - - int i = 0; - for (final Set 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 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 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 String generateDot(final Graph 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 Function getNameShortener(final int maxLength) { - return new Function() { - @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/src/main/java/tools/refinery/viatra/runtime/base/itc/graphimpl/Graph.java b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/graphimpl/Graph.java deleted file mode 100644 index 4267579c..00000000 --- a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/graphimpl/Graph.java +++ /dev/null @@ -1,185 +0,0 @@ -/******************************************************************************* - * 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.IGraphDataSource; -import tools.refinery.viatra.runtime.base.itc.igraph.IGraphObserver; -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 java.util.List; -import java.util.Map; -import java.util.Map.Entry; -import java.util.Set; - -public class Graph implements IGraphDataSource, IBiDirectionalGraphDataSource { - - // source -> target -> count - private IMultiLookup outgoingEdges; - // target -> source -> count - private IMultiLookup incomingEdges; - - private Set nodes; - - private List> 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 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 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 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 incomingView = incomingEdges.lookup(node); - if (incomingView != null) { - Map incoming = CollectionsFactory.createMap(incomingView.asMap()); - - for (Entry entry : incoming.entrySet()) { - for (int i = 0; i < entry.getValue(); i++) { - deleteEdgeThatExists(entry.getKey(), node); - } - } - } - - IMemoryView outgoingView = outgoingEdges.lookup(node); - if (outgoingView != null) { - Map outgoing = CollectionsFactory.createMap(outgoingView.asMap()); - - for (Entry entry : outgoing.entrySet()) { - for (int i = 0; i < entry.getValue(); i++) { - deleteEdgeThatExists(node, entry.getKey()); - } - } - } - - for (IGraphObserver go : observers) { - go.nodeDeleted(node); - } - } - } - - @Override - public void attachObserver(IGraphObserver go) { - observers.add(go); - } - - @Override - public void attachAsFirstObserver(IGraphObserver observer) { - observers.add(0, observer); - } - - @Override - public void detachObserver(IGraphObserver go) { - observers.remove(go); - } - - @Override - public Set getAllNodes() { - return nodes; - } - - @Override - public IMemoryView getTargetNodes(V source) { - return outgoingEdges.lookupOrEmpty(source); - } - - @Override - public IMemoryView 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 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/src/main/java/tools/refinery/viatra/runtime/base/itc/igraph/IBiDirectionalGraphDataSource.java b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/igraph/IBiDirectionalGraphDataSource.java deleted file mode 100644 index 64659447..00000000 --- a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/igraph/IBiDirectionalGraphDataSource.java +++ /dev/null @@ -1,37 +0,0 @@ -/******************************************************************************* - * 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 the type of the nodes in the graph - */ -public interface IBiDirectionalGraphDataSource extends IGraphDataSource { - - /** - * 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 getSourceNodes(V target); - -} diff --git a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/igraph/IBiDirectionalWrapper.java b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/igraph/IBiDirectionalWrapper.java deleted file mode 100644 index becab0eb..00000000 --- a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/igraph/IBiDirectionalWrapper.java +++ /dev/null @@ -1,110 +0,0 @@ -/******************************************************************************* - * 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 - * the type parameter of the nodes in the graph data source - */ -public class IBiDirectionalWrapper implements IBiDirectionalGraphDataSource, IGraphObserver { - - private IGraphDataSource wrappedDataSource; - // target -> source -> count - private IMultiLookup incomingEdges; - - public IBiDirectionalWrapper(IGraphDataSource gds) { - this.wrappedDataSource = gds; - - this.incomingEdges = CollectionsFactory.createMultiLookup( - Object.class, MemoryType.MULTISETS, Object.class); - - if (gds.getAllNodes() != null) { - for (V source : gds.getAllNodes()) { - IMemoryView 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 observer) { - wrappedDataSource.attachObserver(observer); - } - - @Override - public void attachAsFirstObserver(IGraphObserver observer) { - wrappedDataSource.attachAsFirstObserver(observer); - } - - @Override - public void detachObserver(IGraphObserver observer) { - wrappedDataSource.detachObserver(observer); - } - - @Override - public Set getAllNodes() { - return wrappedDataSource.getAllNodes(); - } - - @Override - public IMemoryView getTargetNodes(V source) { - return wrappedDataSource.getTargetNodes(source); - } - - @Override - public IMemoryView 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/src/main/java/tools/refinery/viatra/runtime/base/itc/igraph/IGraphDataSource.java b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/igraph/IGraphDataSource.java deleted file mode 100644 index 3fa65936..00000000 --- a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/igraph/IGraphDataSource.java +++ /dev/null @@ -1,70 +0,0 @@ -/******************************************************************************* - * 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. - *

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 - * the type of the nodes in the graph - */ -public interface IGraphDataSource { - - /** - * 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 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 observer); - - /** - * Detaches an already registered graph observer from this graph data source. - * - * @param observer the graph observer - */ - public void detachObserver(IGraphObserver observer); - - /** - * Returns the complete set of nodes in the graph data source. - * - * @return the set of all nodes - */ - public Set 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 getTargetNodes(V source); -} diff --git a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/igraph/IGraphObserver.java b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/igraph/IGraphObserver.java deleted file mode 100644 index 5cb2d9fa..00000000 --- a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/igraph/IGraphObserver.java +++ /dev/null @@ -1,55 +0,0 @@ -/******************************************************************************* - * 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 { - - /** - * 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/src/main/java/tools/refinery/viatra/runtime/base/itc/igraph/ITcDataSource.java b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/igraph/ITcDataSource.java deleted file mode 100644 index 5924b723..00000000 --- a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/igraph/ITcDataSource.java +++ /dev/null @@ -1,82 +0,0 @@ -/******************************************************************************* - * 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 - * the type parameter of the node - */ -public interface ITcDataSource { - - /** - * Attach a transitive closure relation observer. - * - * @param to - * the observer object - */ - public void attachObserver(ITcObserver to); - - /** - * Detach a transitive closure relation observer. - * - * @param to - * the observer object - */ - public void detachObserver(ITcObserver to); - - /** - * Returns all nodes which are reachable from the source node. - * - * @param source - * the source node - * @return the set of target nodes - */ - public Set 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 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 getPathFinder(); - - /** - * Call this method to properly dispose the data structures of a transitive closure algorithm. - */ - public void dispose(); -} diff --git a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/igraph/ITcObserver.java b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/igraph/ITcObserver.java deleted file mode 100644 index fded53f1..00000000 --- a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/base/itc/igraph/ITcObserver.java +++ /dev/null @@ -1,39 +0,0 @@ -/******************************************************************************* - * 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 { - - /** - * 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); -} -- cgit v1.2.3-70-g09d2