transaction/StronglyConnectedComponents.cpp

/**
 * Licensed to the Apache Software Foundation (ASF) under one
 * or more contributor license agreements.  See the NOTICE file
 * distributed with this work for additional information
 * regarding copyright ownership.  The ASF licenses this file
 * to you under the Apache License, Version 2.0 (the
 * "License"); you may not use this file except in compliance
 * with the License.  You may obtain a copy of the License at
 *
 *   http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing,
 * software distributed under the License is distributed on an
 * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
 * KIND, either express or implied.  See the License for the
 * specific language governing permissions and limitations
 * under the License.
 **/

#include "transaction/StronglyConnectedComponents.hpp"

#include <cstdint>
#include <stack>
#include <unordered_map>
#include <vector>

#include "transaction/DirectedGraph.hpp"

namespace quickstep {
namespace transaction {

StronglyConnectedComponents::StronglyConnectedComponents(
    const DirectedGraph &directed_graph)
    : directed_graph_(directed_graph),
      is_marked_(directed_graph_.getNumNodes(), false),
      component_ids_(directed_graph_.getNumNodes(), 0),
      low_ids_(directed_graph_.getNumNodes(), 0),
      preorder_counter_(0),
      no_of_components_(0) {
  findStronglyConnectedComponents();
}

void StronglyConnectedComponents::findStronglyConnectedComponents() {
  for (DirectedGraph::node_id v = 0; v < directed_graph_.getNumNodes(); ++v) {
    if (!is_marked_[v]) {
      depthFirstSearch(v);
    }
  }
}


void StronglyConnectedComponents::depthFirstSearch(DirectedGraph::node_id v) {
  // Mark this node.
  is_marked_[v] = true;

  // Set the low_id = preorder_counter and increment counter.
  // Right now low_id eqaual to the counter because the node
  // have not seen any other node.
  low_ids_[v] = preorder_counter_++;

  // Set min = counter = low_id.
  // It keeps track of the minimum traversal order the node has
  // seen.
  std::uint64_t min = low_ids_[v];

  // Push the node to the stack.
  traversal_stack_.push(v);

  // For every adjacent node w:
  // 1-) Apply DFS if w is not marked (recursively).
  // 2-) If low id of w is smaller than minimum number
  //     we have seen so far, update our minimum.
  for (DirectedGraph::node_id w : directed_graph_.getAdjacentNodes(v)) {
    if (!is_marked_[w]) {
      depthFirstSearch(w);
    }
    if (low_ids_[w] < min) {
      min = low_ids_[w];
    }
  }

  // If this node's low id is bigger than the minimum
  // traversal order we have seen so far, update the
  // minimum to reflect changes. That means also we captured
  // a cycle here. To keep invariant we have to keep node in
  // stack, therefore it returns.
  if (min < low_ids_[v]) {
    low_ids_[v] = min;
    return;
  }

  // Reaching here means:
  // - v.min >= v.low_id
  // v is the root of strongly connected component.
  DirectedGraph::node_id w;
  do {
    // Until we get our node, pop from stack.
    w = traversal_stack_.top();

    // Make component id of the node on the top
    // equals to current number of component counter.
    component_ids_[w] = no_of_components_;

    // Set the low id to the more than max number posssible
    // which is the (no_nodes + 1).
    low_ids_[w] = directed_graph_.getNumNodes();
    traversal_stack_.pop();
  } while (w != v);

  // Increment current no of component counter.
  no_of_components_++;
}

std::unordered_map<std::uint64_t, std::vector<DirectedGraph::node_id>>
    StronglyConnectedComponents::getComponentMapping() const {
  std::unordered_map<std::uint64_t, std::vector<DirectedGraph::node_id>> component_mapping;
  for (std::uint64_t i = 0; i < component_ids_.size(); ++i) {
    component_mapping[component_ids_[i]].push_back(i);
  }
  return component_mapping;
}

}  // namespace transaction
}  // namespace quickstep