/* Distributed under the OSI-approved BSD 3-Clause License.  See accompanying
   file Copyright.txt or https://cmake.org/licensing for details.  */
#include "cmComputeComponentGraph.h"

#include <algorithm>
#include <cassert>

cmComputeComponentGraph::cmComputeComponentGraph(Graph const& input)
  : InputGraph(input)
{
}

cmComputeComponentGraph::~cmComputeComponentGraph() = default;

void cmComputeComponentGraph::Compute()
{
  // Identify components.
  Tarjan();

  // Compute the component graph.
  ComponentGraph.resize(0);
  ComponentGraph.resize(Components.size());
  TransferEdges();
}

void cmComputeComponentGraph::Tarjan()
{
  int n = static_cast<int>(InputGraph.size());
  TarjanEntry entry = { 0, 0 };
  TarjanEntries.resize(0);
  TarjanEntries.resize(n, entry);
  TarjanComponents.resize(0);
  TarjanComponents.resize(n, -1);
  TarjanWalkId = 0;
  TarjanVisited.resize(0);
  TarjanVisited.resize(n, 0);
  for (int i = 0; i < n; ++i) {
    // Start a new DFS from this node if it has never been visited.
    if (!TarjanVisited[i]) {
      assert(TarjanStack.empty());
      ++TarjanWalkId;
      TarjanIndex = 0;
      TarjanVisit(i);
    }
  }
}

void cmComputeComponentGraph::TarjanVisit(int i)
{
  // We are now visiting this node.
  TarjanVisited[i] = TarjanWalkId;

  // Initialize the entry.
  TarjanEntries[i].Root = i;
  TarjanComponents[i] = -1;
  TarjanEntries[i].VisitIndex = ++TarjanIndex;
  TarjanStack.push(i);

  // Follow outgoing edges.
  EdgeList const& nl = InputGraph[i];
  for (cmGraphEdge const& ni : nl) {
    int j = ni;

    // Ignore edges to nodes that have been reached by a previous DFS
    // walk.  Since we did not reach the current node from that walk
    // it must not belong to the same component and it has already
    // been assigned to a component.
    if (TarjanVisited[j] > 0 && TarjanVisited[j] < TarjanWalkId) {
      continue;
    }

    // Visit the destination if it has not yet been visited.
    if (!TarjanVisited[j]) {
      TarjanVisit(j);
    }

    // If the destination has not yet been assigned to a component,
    // check if it has a better root for the current object.
    if (TarjanComponents[j] < 0) {
      if (TarjanEntries[TarjanEntries[j].Root].VisitIndex <
          TarjanEntries[TarjanEntries[i].Root].VisitIndex) {
        TarjanEntries[i].Root = TarjanEntries[j].Root;
      }
    }
  }

  // Check if we have found a component.
  if (TarjanEntries[i].Root == i) {
    // Yes.  Create it.
    int c = static_cast<int>(Components.size());
    Components.emplace_back();
    NodeList& component = Components[c];

    // Populate the component list.
    int j;
    do {
      // Get the next member of the component.
      j = TarjanStack.top();
      TarjanStack.pop();

      // Assign the member to the component.
      TarjanComponents[j] = c;
      TarjanEntries[j].Root = i;

      // Store the node in its component.
      component.push_back(j);
    } while (j != i);

    // Sort the component members for clarity.
    std::sort(component.begin(), component.end());
  }
}

void cmComputeComponentGraph::TransferEdges()
{
  // Map inter-component edges in the original graph to edges in the
  // component graph.
  int n = static_cast<int>(InputGraph.size());
  for (int i = 0; i < n; ++i) {
    int i_component = TarjanComponents[i];
    EdgeList const& nl = InputGraph[i];
    for (cmGraphEdge const& ni : nl) {
      int j = ni;
      int j_component = TarjanComponents[j];
      if (i_component != j_component) {
        // We do not attempt to combine duplicate edges, but instead
        // store the inter-component edges with suitable multiplicity.
        ComponentGraph[i_component].emplace_back(
          j_component, ni.IsStrong(), ni.IsCross(), ni.GetBacktrace());
      }
    }
  }
}
