void construct_auxilary()

in include/WeakPartialOrdering.h [299:374]

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

  void construct_auxilary(const NodeId& root) {
    // It uses disjoint-sets data structure.
    typedef std::unordered_map<uint32_t, std::size_t> rank_t;
    typedef std::unordered_map<uint32_t, uint32_t> parent_t;
    rank_t rank_map;
    parent_t parent_map;
    typedef boost::associative_property_map<rank_t> r_pmap_t;
    r_pmap_t r_pmap(rank_map);
    typedef boost::associative_property_map<parent_t> p_pmap_t;
    p_pmap_t p_pmap(parent_map);
    boost::disjoint_sets<r_pmap_t, p_pmap_t> dsets(r_pmap, p_pmap);

    std::unordered_map<uint32_t, uint32_t> ancestor;
    std::stack<std::tuple<NodeId, bool, uint32_t>> stack;
    std::unordered_map<uint32_t, bool> black;

    stack.push(std::make_tuple(root, false, 0));
    while (!stack.empty()) {
      // Iterative DFS.
      auto& stack_top = stack.top();
      auto vertex_ref = std::get<0>(stack_top);
      auto finished = std::get<1>(stack_top);
      auto pred = std::get<2>(stack_top);
      stack.pop();

      if (finished) {
        // DFS is done with this vertex.
        // Set the post DFN.
        m_post_dfn[vertex_ref] = m_next_post_dfn++;

        auto vertex = get_dfn(vertex_ref);
        // Mark visited.
        black[vertex] = true;

        dsets.union_set(vertex, pred);
        ancestor[dsets.find_set(pred)] = pred;
      } else {
        if (get_dfn(vertex_ref) !=
            0 /* means that the vertex is already discovered. */) {
          // A forward edge.
          // Forward edges can be ignored, as they are redundant.
          continue;
        }
        // New vertex is discovered.
        auto vertex = m_next_dfn++;
        push_ref(vertex_ref);
        set_dfn(vertex_ref, vertex);
        dsets.make_set(vertex);
        ancestor[vertex] = vertex;

        // This will be popped after all its successors are finished.
        stack.push(std::make_tuple(vertex_ref, true, pred));

        auto successors = m_successors(vertex_ref);
        // Successors vector is reversed to match the order with WTO.
        for (auto rit = successors.rbegin(); rit != successors.rend(); ++rit) {
          auto succ = get_dfn(*rit);
          if (succ == 0 /* 0 means that vertex is undiscovered. */) {
            // Newly discovered vertex. Search continues.
            stack.push(std::make_tuple(*rit, false, vertex));
          } else if (black[succ]) {
            // A cross edge.
            auto lca = ancestor[dsets.find_set(succ)];
            m_cross_fwds[lca].emplace_back(vertex, succ);
          } else {
            // A back edge.
            m_back_preds[succ].push_back(vertex);
          }
        }
        if (pred != 0) {
          // A tree edge.
          m_non_back_preds[vertex].push_back(pred);
        }
      }
    }
  }