graphcoloring.hh

Go to the documentation of this file.

// SPDX-FileCopyrightText: Copyright © DUNE Project contributors, see file AUTHORS.md
// SPDX-License-Identifier: LicenseRef-GPL-2.0-only-with-DUNE-exception OR LGPL-3.0-or-later
 
#ifndef DUNE_ASSEMBLER_PARALLEL_GRAPHCOLORING_HH
#define DUNE_ASSEMBLER_PARALLEL_GRAPHCOLORING_HH
 
#include <algorithm>
#include <initializer_list>
#include <limits>
#include <queue>
#include <type_traits>
#include <utility>
#include <vector>
 
#include <dune/common/rangeutilities.hh>
 
namespace Dune::Assembler::Experimental {
 
 
 
template <class Adjacency, class SeedNodesContainer>
auto computeColoring (const Adjacency& adjacency, SeedNodesContainer&& seedNodes)
{
 
  // Hack to access i-th entry without adjacency[i].
  // This is necessary to support TransformedRangeView,
  // because the latter does not provide operator[]
  // in dune-2.9 although the range is random-access.
  auto adjacentNodes = [&](auto i) {
    return adjacency.begin()[i];
  };
 
  using size_type = std::decay_t<decltype(*adjacentNodes(0).begin())>;
 
  // Use magic values to tag fully unprocessed and queued (but non-colored) entries.
  size_type nonProcessedStatus = std::numeric_limits<size_type>::max();
  size_type queuedStatus = std::numeric_limits<size_type>::max()-1;
 
  // Initialize result vector with unprocessed state for all entries.
  std::vector<size_type> color(adjacency.size(), nonProcessedStatus);
 
  // Queue for the advancing front method
  auto queue = std::queue<size_type>();
 
  // Some helper methods to make code more expressive
  auto isColored = [&](const auto& i) {
    return color[i]<queuedStatus;
  };
  auto isNonProcessed = [&](const auto& i) {
    return color[i]==nonProcessedStatus;
  };
  auto queueNode = [&](const auto& i) {
    color[i] = queuedStatus;
    queue.push(i);
  };
 
  // Fill queue with seed nodes (or {0} if seed node container is empty)
  for (size_type i : seedNodes)
    queueNode(i);
  if (queue.empty())
    queueNode(0);
 
  // A temporary data structure to store the colors of already
  // colored neighbors.
  //
  // There's various possible data structures here. The most
  // obvious would be a set-like container storing the used
  // color indices. This could be (with increasing performance)
  // std::set, std::unordered_set, std::vector (keep sorted and unique),
  // std::vector (just append, sort and remove duplicates afterwards).
  // Since we expect that the total number of colors is small,
  // it is significantly faster to simply mark used colors in
  // a flag vector. Because memory usage is not an issue here,
  // we use std::vector<char> which measurably outperformes
  // std::vector<bool> due to faster bit access.
  std::vector<char> colorIsUsed;
  colorIsUsed.resize(32);
 
  // If the graph has several connected components that are not
  // reachable by the seed nodes, then we need to do several sweeps
  // of the advancing front method.
  while (not queue.empty())
  {
    // Use advancing front method to traverse graph
    while (not queue.empty())
    {
      // Process next entry from queue
      auto i = queue.front();
      queue.pop();
 
      // Collect colors of already colored neighbors,
      // put nonprocessed neighbors into queue,
      // and do nothing with already queued neighbors.
      colorIsUsed.assign(colorIsUsed.size(), false);
      for (const auto& neighbor: adjacentNodes(i))
      {
        if (isColored(neighbor))
          colorIsUsed[color[neighbor]] = true;
        else if (isNonProcessed(neighbor))
          queueNode(neighbor);
      }
 
      // Assign first color that is not used by any processed neighbor to the current node
      color[i] = std::find(colorIsUsed.begin(), colorIsUsed.end(), false) - colorIsUsed.begin();
 
      // If necessary: Resize flag vector
      if (color[i]==colorIsUsed.size())
        colorIsUsed.resize(color[i]+1);
    }
 
    // If there are still some uncolored nodes, then the graph has connected
    // components that are not reachable by the provided seed nodes. Hence we
    // do another advancing front sweep starting from the first uncolored node.
    auto firstNonProcessedIt = std::find(color.begin(), color.end(), nonProcessedStatus);
    if (firstNonProcessedIt!=color.end())
      queueNode(firstNonProcessedIt - color.begin());
  }
 
  return color;
}
 
 
 
template <class Adjacency, class T>
auto computeColoring (const Adjacency& adjacency, std::initializer_list<T> seedIndices)
{
  return computeColoring(adjacency, std::vector<T>{seedIndices});
}
 
 
 
template <class Adjacency>
auto computeColoring (const Adjacency& adjacency)
{
  return computeColoring(adjacency, {0});
}
 
 
 
} // end namespace Dune::Assembler::Experimental
 
#endif // DUNE_ASSEMBLER_PARALLEL_GRAPHCOLORING_HH