1 package org.testng.internal; 2 3 import org.testng.collections.Lists; 4 import org.testng.collections.Maps; 5 6 import java.util.List; 7 import java.util.Map; 8 import java.util.Objects; 9 import java.util.Stack; 10 11 /** 12 * Implementation of the Tarjan algorithm to find and display a cycle in a graph. 13 * @author cbeust 14 */ 15 public class Tarjan<T> { 16 int m_index = 0; 17 private Stack<T> m_s; 18 Map<T, Integer> m_indices = Maps.newHashMap(); 19 Map<T, Integer> m_lowlinks = Maps.newHashMap(); 20 private List<T> m_cycle; 21 22 public Tarjan(Graph<T> graph, T start) { 23 m_s = new Stack<>(); 24 run(graph, start); 25 } 26 27 private void run(Graph<T> graph, T v) { 28 m_indices.put(v, m_index); 29 m_lowlinks.put(v, m_index); 30 m_index++; 31 m_s.push(v); 32 33 for (T vprime : graph.getPredecessors(v)) { 34 if (! m_indices.containsKey(vprime)) { 35 run(graph, vprime); 36 int min = Math.min(m_lowlinks.get(v), m_lowlinks.get(vprime)); 37 m_lowlinks.put(v, min); 38 } 39 else if (m_s.contains(vprime)) { 40 m_lowlinks.put(v, Math.min(m_lowlinks.get(v), m_indices.get(vprime))); 41 } 42 } 43 44 if (Objects.equals(m_lowlinks.get(v), m_indices.get(v))) { 45 m_cycle = Lists.newArrayList(); 46 T n; 47 do { 48 n = m_s.pop(); 49 m_cycle.add(n); 50 } while (! n.equals(v)); 51 } 52 53 } 54 55 public static void main(String[] args) { 56 Graph<String> g = new Graph<>(); 57 g.addNode("a"); 58 g.addNode("b"); 59 g.addNode("c"); 60 g.addNode("d"); 61 62 String[] edges = new String[] { 63 "a", "b", 64 "b", "a", 65 "c", "d", 66 "d", "a", 67 "a", "c", 68 }; 69 70 for (int i = 0; i < edges.length; i += 2) { 71 g.addPredecessor(edges[i], edges[i+1]); 72 } 73 74 new Tarjan<>(g, "a"); 75 } 76 77 public List<T> getCycle() { 78 return m_cycle; 79 } 80 81 } 82
