Temporarily include bndlib 1.47 for testing purposes (not yet on central)
git-svn-id: https://svn.apache.org/repos/asf/felix/trunk@1185095 13f79535-47bb-0310-9956-ffa450edef68
diff --git a/bundleplugin/src/main/java/aQute/libg/tarjan/Tarjan.java b/bundleplugin/src/main/java/aQute/libg/tarjan/Tarjan.java
new file mode 100644
index 0000000..063006e
--- /dev/null
+++ b/bundleplugin/src/main/java/aQute/libg/tarjan/Tarjan.java
@@ -0,0 +1,108 @@
+package aQute.libg.tarjan;
+
+import static java.lang.Math.*;
+
+import java.util.*;
+
+public class Tarjan<T> {
+
+ public class Node {
+ final T name;
+ final List<Node> adjacent = new ArrayList<Node>();
+ int low = -1;
+ int index = -1;
+
+ public Node(T name) {
+ this.name = name;
+ }
+
+ public String toString() {
+ return name + "{" + index + "," + low + "}";
+ }
+ }
+
+ private int index = 0;
+ private List<Node> stack = new ArrayList<Node>();
+ private Set<Set<T>> scc = new HashSet<Set<T>>();
+ private Node root = new Node(null);
+
+
+// public ArrayList<ArrayList<Node>> tarjan(Node v, AdjacencyList list){
+// v.index = index;
+// v.lowlink = index;
+// index++;
+// stack.add(0, v);
+// for(Edge e : list.getAdjacent(v)){
+// Node n = e.to;
+// if(n.index == -1){
+// tarjan(n, list);
+// v.lowlink = Math.min(v.lowlink, n.lowlink);
+// }else if(stack.contains(n)){
+// v.lowlink = Math.min(v.lowlink, n.index);
+// }
+// }
+// if(v.lowlink == v.index){
+// Node n;
+// ArrayList<Node> component = new ArrayList<Node>();
+// do{
+// n = stack.remove(0);
+// component.add(n);
+// }while(n != v);
+// SCC.add(component);
+// }
+// return SCC;
+// }
+
+ void tarjan(Node v) {
+ v.index = index;
+ v.low = index;
+ index++;
+ stack.add(0, v);
+ for (Node n : v.adjacent) {
+ if (n.index == -1) {
+ // first time visit
+ tarjan(n);
+ v.low = min(v.low, n.low);
+ } else if (stack.contains(n)) {
+ v.low = min(v.low, n.index);
+ }
+ }
+
+ if (v!=root && v.low == v.index) {
+ Set<T> component = new HashSet<T>();
+ Node n;
+ do {
+ n = stack.remove(0);
+ component.add(n.name);
+ } while (n != v);
+ scc.add(component);
+ }
+ }
+
+ Set<Set<T>> getResult(Map<T, ? extends Collection<T>> graph) {
+ Map<T, Node> index = new HashMap<T, Node>();
+
+ for (Map.Entry<T, ? extends Collection<T>> entry : graph.entrySet()) {
+ Node node = getNode(index, entry.getKey());
+ root.adjacent.add(node);
+ for (T adj : entry.getValue())
+ node.adjacent.add(getNode(index, adj));
+ }
+ tarjan(root);
+ return scc;
+ }
+
+ private Node getNode(Map<T, Node> index, T key) {
+ Node node = index.get(key);
+ if (node == null) {
+ node = new Node(key);
+ index.put(key, node);
+ }
+ return node;
+ }
+
+ public static <T> Set<Set<T>> tarjan(Map<T, Set<T>> graph) {
+ Tarjan<T> tarjan = new Tarjan<T>();
+ return tarjan.getResult(graph);
+ }
+}