clique_enumeration.hpp

SECTIONGraph INCLUDEnoya/clique_enumeration.hpp

Sum the products of vertex weights over all nonempty cliques. Vertices are ordered by degree and every clique is generated exactly once from its smallest vertex in that order. Recursion intersects the remaining candidates with the chosen vertex's adjacency bitset, so only prefixes that are already cliques are visited.

Verified by enumerate_cliques.

枚举无向图的所有团，并把每个团交给回调统计或计算贡献。

Implementation

View on GitHub

SourceExpanded

#ifndef NOYA_CLIQUE_ENUMERATION_HPP
#define NOYA_CLIQUE_ENUMERATION_HPP 1

/// @complexity Time: O((n + number of cliques) ceil(n / 64)) after O(n + m)
/// graph construction.
/// Space: O(n^2 / 64) adjacency bits and O(n^2 / 64) recursion workspace.

#include <algorithm>
#include <bit>
#include <cstdint>
#include <utility>
#include <vector>

namespace noya {

/// @brief Sum the products of vertex weights over all nonempty cliques.
/// Vertices are ordered by degree and every clique is generated exactly once
/// from its smallest vertex in that order. Recursion intersects the remaining
/// candidates with the chosen vertex's adjacency bitset, so only prefixes that
/// are already cliques are visited.
template <class T>
T sum_of_clique_products(int vertex_count,
                         const std::vector<std::pair<int, int>> &edges,
                         const std::vector<T> &weights) {
  int words = (vertex_count + 63) / 64;
  std::vector<int> degree(vertex_count);
  for (auto [first, second] : edges) {
    degree[first]++;
    degree[second]++;
  }
  std::vector<int> order(vertex_count);
  for (int i = 0; i < vertex_count; i++) {
    order[i] = i;
  }
  std::stable_sort(order.begin(), order.end(), [&](int first, int second) {
    return degree[first] < degree[second];
  });
  std::vector<int> rank(vertex_count);
  for (int i = 0; i < vertex_count; i++) {
    rank[order[i]] = i;
  }

  std::vector<std::vector<std::uint64_t>> adjacency(
      vertex_count, std::vector<std::uint64_t>(words));
  for (auto [first, second] : edges) {
    first = rank[first];
    second = rank[second];
    adjacency[first][second >> 6] |= std::uint64_t(1) << (second & 63);
    adjacency[second][first >> 6] |= std::uint64_t(1) << (first & 63);
  }

  T answer{};
  auto enumerate = [&](auto &self, std::vector<std::uint64_t> candidates,
                       const T &product) -> void {
    for (int word = 0; word < words; word++) {
      while (candidates[word] != 0) {
        int bit = std::countr_zero(candidates[word]);
        int vertex = word * 64 + bit;
        candidates[word] &= candidates[word] - 1;
        T next_product = product * weights[order[vertex]];
        answer += next_product;
        std::vector<std::uint64_t> next(words);
        for (int i = word; i < words; i++) {
          next[i] = candidates[i] & adjacency[vertex][i];
        }
        self(self, std::move(next), next_product);
      }
    }
  };
  std::vector<std::uint64_t> all(words, ~std::uint64_t(0));
  if (vertex_count % 64 != 0) {
    all.back() = (std::uint64_t(1) << (vertex_count % 64)) - 1;
  }
  enumerate(enumerate, std::move(all), T(1));
  return answer;
}

} // namespace noya

#endif // NOYA_CLIQUE_ENUMERATION_HPP

#include <algorithm>
#include <bit>
#include <cstdint>
#include <utility>
#include <vector>

/// @complexity Time: O((n + number of cliques) ceil(n / 64)) after O(n + m)
/// graph construction.
/// Space: O(n^2 / 64) adjacency bits and O(n^2 / 64) recursion workspace.

namespace noya {

/// @brief Sum the products of vertex weights over all nonempty cliques.
/// Vertices are ordered by degree and every clique is generated exactly once
/// from its smallest vertex in that order. Recursion intersects the remaining
/// candidates with the chosen vertex's adjacency bitset, so only prefixes that
/// are already cliques are visited.
template <class T>
T sum_of_clique_products(int vertex_count,
                         const std::vector<std::pair<int, int>> &edges,
                         const std::vector<T> &weights) {
  int words = (vertex_count + 63) / 64;
  std::vector<int> degree(vertex_count);
  for (auto [first, second] : edges) {
    degree[first]++;
    degree[second]++;
  }
  std::vector<int> order(vertex_count);
  for (int i = 0; i < vertex_count; i++) {
    order[i] = i;
  }
  std::stable_sort(order.begin(), order.end(), [&](int first, int second) {
    return degree[first] < degree[second];
  });
  std::vector<int> rank(vertex_count);
  for (int i = 0; i < vertex_count; i++) {
    rank[order[i]] = i;
  }

  std::vector<std::vector<std::uint64_t>> adjacency(
      vertex_count, std::vector<std::uint64_t>(words));
  for (auto [first, second] : edges) {
    first = rank[first];
    second = rank[second];
    adjacency[first][second >> 6] |= std::uint64_t(1) << (second & 63);
    adjacency[second][first >> 6] |= std::uint64_t(1) << (first & 63);
  }

  T answer{};
  auto enumerate = [&](auto &self, std::vector<std::uint64_t> candidates,
                       const T &product) -> void {
    for (int word = 0; word < words; word++) {
      while (candidates[word] != 0) {
        int bit = std::countr_zero(candidates[word]);
        int vertex = word * 64 + bit;
        candidates[word] &= candidates[word] - 1;
        T next_product = product * weights[order[vertex]];
        answer += next_product;
        std::vector<std::uint64_t> next(words);
        for (int i = word; i < words; i++) {
          next[i] = candidates[i] & adjacency[vertex][i];
        }
        self(self, std::move(next), next_product);
      }
    }
  };
  std::vector<std::uint64_t> all(words, ~std::uint64_t(0));
  if (vertex_count % 64 != 0) {
    all.back() = (std::uint64_t(1) << (vertex_count % 64)) - 1;
  }
  enumerate(enumerate, std::move(all), T(1));
  return answer;
}

} // namespace noya