blob: 89be6804e2a98e5f9d393a350b11b9f5e44e8197 (
plain) (
blame)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
|
/*******************************************************************************
* Copyright (c) 2010-2012, Tamas Szabo, Istvan Rath and Daniel Varro
* This program and the accompanying materials are made available under the
* terms of the Eclipse Public License v. 2.0 which is available at
* http://www.eclipse.org/legal/epl-v20.html.
*
* SPDX-License-Identifier: EPL-2.0
*******************************************************************************/
package tools.refinery.viatra.runtime.rete.itc.alg.misc.topsort;
import tools.refinery.viatra.runtime.rete.itc.igraph.IGraphDataSource;
import java.util.*;
/**
* @since 1.6
*/
public class TopologicalSorting {
private TopologicalSorting() {/*Utility class constructor*/}
private static final class Pair<T> {
public T element;
public boolean isParent;
public Pair(final T element, final boolean isParent) {
this.element = element;
this.isParent = isParent;
}
}
/**
* Returns a topological ordering for the given graph data source.
* Output format: if there is an a -> b (transitive) reachability, then node <code>a</code> will come before node <code>b</code> in the resulting list.
*
* @param gds the graph data source
* @return a topological ordering
*/
public static <T> List<T> compute(final IGraphDataSource<T> gds) {
final Set<T> visited = new HashSet<T>();
final LinkedList<T> result = new LinkedList<T>();
final Deque<Pair<T>> dfsStack = new ArrayDeque<Pair<T>>();
for (final T node : gds.getAllNodes()) {
if (!visited.contains(node)) {
dfsStack.addLast(new Pair<T>(node, false));
}
while (!dfsStack.isEmpty()) {
final Pair<T> head = dfsStack.removeLast();
final T source = head.element;
if (head.isParent) {
// we have already seen source, push it to the resulting stack
result.addFirst(source);
} else {
// first time we see source, continue with its children
visited.add(source);
dfsStack.addLast(new Pair<T>(source, true));
for (final T target : gds.getTargetNodes(source).distinctValues()) {
if (!visited.contains(target)) {
dfsStack.addLast(new Pair<T>(target, false));
}
}
}
}
}
return result;
}
}
|
