uint32_t visit()

in include/WeakTopologicalOrdering.h [267:305]

• 36 lines of code
• 8 McCabe index (conditional complexity)

  uint32_t visit(const NodeId& vertex, int32_t* partition) {
    m_stack.push(vertex);
    uint32_t head = set_dfn(vertex, ++m_num);
    bool loop = false;
    for (const NodeId& succ : m_successors(vertex)) {
      uint32_t succ_dfn = get_dfn(succ);
      uint32_t min;
      if (succ_dfn == 0) {
        min = visit(succ, partition);
      } else {
        min = succ_dfn;
      };
      if (min <= head) {
        head = min;
        loop = true;
      }
    }
    if (head == get_dfn(vertex)) {
      // We encode the special value +oo used in the paper with UINT32_MAX.
      set_dfn(vertex, std::numeric_limits<uint32_t>::max());
      NodeId element = m_stack.top();
      m_stack.pop();
      if (loop) {
        // Nodes are required to be comparable using `operator==()`. We don't
        // assume `operator!=()` to be defined on nodes.
        while (!(element == vertex)) {
          set_dfn(element, 0);
          element = m_stack.top();
          m_stack.pop();
        }
        push_component(vertex, *partition);
      }
      auto kind = loop ? WtoComponent<NodeId>::Kind::Scc
                       : WtoComponent<NodeId>::Kind::Vertex;
      m_wto_space->emplace_back(vertex, kind, m_free_position, *partition);
      *partition = m_free_position++;
    }
    return head;
  }