Review

finding-4

org/testng/internal/Tarjan.java

run(Graph, Object)

class Tarjan<T> {
  private void run(Graph<T> graph, T v) {
    m_indices.put(v, m_index);
    m_lowlinks.put(v, m_index);
    m_index++;
    m_s.push(v);

    for (T vprime : graph.getPredecessors(v)) {
      if (! m_indices.containsKey(vprime)) {
        run(graph, vprime);
        int min = Math.min(m_lowlinks.get(v), m_lowlinks.get(vprime));
        m_lowlinks.put(v, min);
      }
      else if (m_s.contains(vprime)) {
        m_lowlinks.put(v, Math.min(m_lowlinks.get(v), m_indices.get(vprime)));
      }
    }

    if (Objects.equals(m_lowlinks.get(v), m_indices.get(v))) {
      m_cycle = Lists.newArrayList();
      T n;
      do {
        n = m_s.pop();
        m_cycle.add(n);
      } while (! n.equals(v));
    }

  }
}