Stuart McCulloch | f317322 | 2012-06-07 21:57:32 +0000 | [diff] [blame] | 1 | package aQute.libg.tarjan; |
| 2 | |
| 3 | import static java.lang.Math.*; |
| 4 | |
| 5 | import java.util.*; |
| 6 | |
| 7 | public class Tarjan<T> { |
| 8 | |
| 9 | public class Node { |
| 10 | final T name; |
| 11 | final List<Node> adjacent = new ArrayList<Node>(); |
| 12 | int low = -1; |
| 13 | int index = -1; |
| 14 | |
| 15 | public Node(T name) { |
| 16 | this.name = name; |
| 17 | } |
Stuart McCulloch | 4482c70 | 2012-06-15 13:27:53 +0000 | [diff] [blame^] | 18 | |
Stuart McCulloch | f317322 | 2012-06-07 21:57:32 +0000 | [diff] [blame] | 19 | public String toString() { |
| 20 | return name + "{" + index + "," + low + "}"; |
| 21 | } |
| 22 | } |
| 23 | |
Stuart McCulloch | 4482c70 | 2012-06-15 13:27:53 +0000 | [diff] [blame^] | 24 | private int index = 0; |
| 25 | private List<Node> stack = new ArrayList<Node>(); |
Stuart McCulloch | f317322 | 2012-06-07 21:57:32 +0000 | [diff] [blame] | 26 | private Set<Set<T>> scc = new HashSet<Set<T>>(); |
Stuart McCulloch | 4482c70 | 2012-06-15 13:27:53 +0000 | [diff] [blame^] | 27 | private Node root = new Node(null); |
Stuart McCulloch | f317322 | 2012-06-07 21:57:32 +0000 | [diff] [blame] | 28 | |
Stuart McCulloch | 4482c70 | 2012-06-15 13:27:53 +0000 | [diff] [blame^] | 29 | // public ArrayList<ArrayList<Node>> tarjan(Node v, AdjacencyList list){ |
| 30 | // v.index = index; |
| 31 | // v.lowlink = index; |
| 32 | // index++; |
| 33 | // stack.add(0, v); |
| 34 | // for(Edge e : list.getAdjacent(v)){ |
| 35 | // Node n = e.to; |
| 36 | // if(n.index == -1){ |
| 37 | // tarjan(n, list); |
| 38 | // v.lowlink = Math.min(v.lowlink, n.lowlink); |
| 39 | // }else if(stack.contains(n)){ |
| 40 | // v.lowlink = Math.min(v.lowlink, n.index); |
| 41 | // } |
| 42 | // } |
| 43 | // if(v.lowlink == v.index){ |
| 44 | // Node n; |
| 45 | // ArrayList<Node> component = new ArrayList<Node>(); |
| 46 | // do{ |
| 47 | // n = stack.remove(0); |
| 48 | // component.add(n); |
| 49 | // }while(n != v); |
| 50 | // SCC.add(component); |
| 51 | // } |
| 52 | // return SCC; |
| 53 | // } |
Stuart McCulloch | f317322 | 2012-06-07 21:57:32 +0000 | [diff] [blame] | 54 | |
| 55 | void tarjan(Node v) { |
| 56 | v.index = index; |
| 57 | v.low = index; |
| 58 | index++; |
| 59 | stack.add(0, v); |
| 60 | for (Node n : v.adjacent) { |
| 61 | if (n.index == -1) { |
| 62 | // first time visit |
| 63 | tarjan(n); |
| 64 | v.low = min(v.low, n.low); |
| 65 | } else if (stack.contains(n)) { |
| 66 | v.low = min(v.low, n.index); |
| 67 | } |
| 68 | } |
| 69 | |
Stuart McCulloch | 4482c70 | 2012-06-15 13:27:53 +0000 | [diff] [blame^] | 70 | if (v != root && v.low == v.index) { |
Stuart McCulloch | f317322 | 2012-06-07 21:57:32 +0000 | [diff] [blame] | 71 | Set<T> component = new HashSet<T>(); |
| 72 | Node n; |
| 73 | do { |
| 74 | n = stack.remove(0); |
| 75 | component.add(n.name); |
| 76 | } while (n != v); |
| 77 | scc.add(component); |
| 78 | } |
| 79 | } |
| 80 | |
| 81 | Set<Set<T>> getResult(Map<T, ? extends Collection<T>> graph) { |
Stuart McCulloch | 4482c70 | 2012-06-15 13:27:53 +0000 | [diff] [blame^] | 82 | Map<T,Node> index = new HashMap<T,Node>(); |
Stuart McCulloch | f317322 | 2012-06-07 21:57:32 +0000 | [diff] [blame] | 83 | |
| 84 | for (Map.Entry<T, ? extends Collection<T>> entry : graph.entrySet()) { |
| 85 | Node node = getNode(index, entry.getKey()); |
| 86 | root.adjacent.add(node); |
| 87 | for (T adj : entry.getValue()) |
| 88 | node.adjacent.add(getNode(index, adj)); |
| 89 | } |
| 90 | tarjan(root); |
| 91 | return scc; |
| 92 | } |
| 93 | |
Stuart McCulloch | 4482c70 | 2012-06-15 13:27:53 +0000 | [diff] [blame^] | 94 | private Node getNode(Map<T,Node> index, T key) { |
Stuart McCulloch | f317322 | 2012-06-07 21:57:32 +0000 | [diff] [blame] | 95 | Node node = index.get(key); |
| 96 | if (node == null) { |
| 97 | node = new Node(key); |
| 98 | index.put(key, node); |
| 99 | } |
| 100 | return node; |
| 101 | } |
| 102 | |
Stuart McCulloch | 4482c70 | 2012-06-15 13:27:53 +0000 | [diff] [blame^] | 103 | public static <T> Collection< ? extends Collection<T>> tarjan(Map<T, ? extends Collection<T>> graph) { |
Stuart McCulloch | f317322 | 2012-06-07 21:57:32 +0000 | [diff] [blame] | 104 | Tarjan<T> tarjan = new Tarjan<T>(); |
| 105 | return tarjan.getResult(graph); |
| 106 | } |
| 107 | } |