diff options
author | Kristóf Marussy <marussy@mit.bme.hu> | 2023-09-14 19:29:36 +0200 |
---|---|---|
committer | GitHub <noreply@github.com> | 2023-09-14 19:29:36 +0200 |
commit | 98ed3b6db5f4e51961a161050cc31c66015116e8 (patch) | |
tree | 8bfd6d9bc8d6ed23b9eb0f889dd40b6c24fe8f92 /subprojects/viatra-runtime-rete/src/main/java/tools/refinery/viatra/runtime/rete/itc/alg/misc/topsort/TopologicalSorting.java | |
parent | Merge pull request #38 from nagilooh/design-space-exploration (diff) | |
parent | Merge remote-tracking branch 'upstream/main' into partial-interpretation (diff) | |
download | refinery-98ed3b6db5f4e51961a161050cc31c66015116e8.tar.gz refinery-98ed3b6db5f4e51961a161050cc31c66015116e8.tar.zst refinery-98ed3b6db5f4e51961a161050cc31c66015116e8.zip |
Merge pull request #39 from kris7t/partial-interpretation
Implement partial interpretation based model generation
Diffstat (limited to 'subprojects/viatra-runtime-rete/src/main/java/tools/refinery/viatra/runtime/rete/itc/alg/misc/topsort/TopologicalSorting.java')
-rw-r--r-- | subprojects/viatra-runtime-rete/src/main/java/tools/refinery/viatra/runtime/rete/itc/alg/misc/topsort/TopologicalSorting.java | 73 |
1 files changed, 73 insertions, 0 deletions
diff --git a/subprojects/viatra-runtime-rete/src/main/java/tools/refinery/viatra/runtime/rete/itc/alg/misc/topsort/TopologicalSorting.java b/subprojects/viatra-runtime-rete/src/main/java/tools/refinery/viatra/runtime/rete/itc/alg/misc/topsort/TopologicalSorting.java new file mode 100644 index 00000000..89be6804 --- /dev/null +++ b/subprojects/viatra-runtime-rete/src/main/java/tools/refinery/viatra/runtime/rete/itc/alg/misc/topsort/TopologicalSorting.java | |||
@@ -0,0 +1,73 @@ | |||
1 | /******************************************************************************* | ||
2 | * Copyright (c) 2010-2012, Tamas Szabo, Istvan Rath and Daniel Varro | ||
3 | * This program and the accompanying materials are made available under the | ||
4 | * terms of the Eclipse Public License v. 2.0 which is available at | ||
5 | * http://www.eclipse.org/legal/epl-v20.html. | ||
6 | * | ||
7 | * SPDX-License-Identifier: EPL-2.0 | ||
8 | *******************************************************************************/ | ||
9 | |||
10 | package tools.refinery.viatra.runtime.rete.itc.alg.misc.topsort; | ||
11 | |||
12 | import tools.refinery.viatra.runtime.rete.itc.igraph.IGraphDataSource; | ||
13 | |||
14 | import java.util.*; | ||
15 | |||
16 | /** | ||
17 | * @since 1.6 | ||
18 | */ | ||
19 | public class TopologicalSorting { | ||
20 | |||
21 | private TopologicalSorting() {/*Utility class constructor*/} | ||
22 | |||
23 | private static final class Pair<T> { | ||
24 | public T element; | ||
25 | public boolean isParent; | ||
26 | |||
27 | public Pair(final T element, final boolean isParent) { | ||
28 | this.element = element; | ||
29 | this.isParent = isParent; | ||
30 | } | ||
31 | } | ||
32 | |||
33 | /** | ||
34 | * Returns a topological ordering for the given graph data source. | ||
35 | * Output format: if there is an a -> b (transitive) reachability, then node <code>a</code> will come before node <code>b</code> in the resulting list. | ||
36 | * | ||
37 | * @param gds the graph data source | ||
38 | * @return a topological ordering | ||
39 | */ | ||
40 | public static <T> List<T> compute(final IGraphDataSource<T> gds) { | ||
41 | final Set<T> visited = new HashSet<T>(); | ||
42 | final LinkedList<T> result = new LinkedList<T>(); | ||
43 | final Deque<Pair<T>> dfsStack = new ArrayDeque<Pair<T>>(); | ||
44 | |||
45 | for (final T node : gds.getAllNodes()) { | ||
46 | if (!visited.contains(node)) { | ||
47 | dfsStack.addLast(new Pair<T>(node, false)); | ||
48 | } | ||
49 | |||
50 | while (!dfsStack.isEmpty()) { | ||
51 | final Pair<T> head = dfsStack.removeLast(); | ||
52 | final T source = head.element; | ||
53 | |||
54 | if (head.isParent) { | ||
55 | // we have already seen source, push it to the resulting stack | ||
56 | result.addFirst(source); | ||
57 | } else { | ||
58 | // first time we see source, continue with its children | ||
59 | visited.add(source); | ||
60 | dfsStack.addLast(new Pair<T>(source, true)); | ||
61 | |||
62 | for (final T target : gds.getTargetNodes(source).distinctValues()) { | ||
63 | if (!visited.contains(target)) { | ||
64 | dfsStack.addLast(new Pair<T>(target, false)); | ||
65 | } | ||
66 | } | ||
67 | } | ||
68 | } | ||
69 | } | ||
70 | |||
71 | return result; | ||
72 | } | ||
73 | } | ||