clique_enumeration.hpp¶
计算所有非空团的顶点权乘积之和；保留度数排序下的乘法与累加顺序，使用局部位集和复用缓冲。自环与重边不产生额外团。
Complexity: Time: \(O(n \log (n + 1) + m + M D + C (1 + \lceil D / 64\rceil))\), with \(M\) distinct non-loop edges, \(D\) maximum forward degree, \(C\) nonempty cliques. Space: \(O(n + m + D \lceil D / 64\rceil)\), including \(O(D)\) recursion.
AC 记录：enumerate_cliques。
Implementation¶
当前头文件，省略 include guard；依赖见 #include。
/// @complexity Time: O(n log(n+1) + m + M D + C (1+ceil(D/64))), with M
/// distinct non-loop edges, D maximum forward degree, C nonempty cliques.
/// Space: O(n + m + D ceil(D/64)), including O(D) recursion.
#include <algorithm>
#include <bit>
#include <cassert>
#include <cstddef>
#include <cstdint>
#include <span>
#include <utility>
#include <vector>
namespace noya {
/// @brief Sum the products of vertex weights over all nonempty cliques.
/// Require n >= 0, valid endpoints and at least n weights. Loops/duplicates
/// do not create extra cliques. Keep the original order: increasing raw
/// degree (loops counted twice), then vertex ID, with depth-first prefix order.
/// T needs T{}, T(1), copying, * and +=; products are left-associated.
template <class T>
T sum_of_clique_products(int n, const std::vector<std::pair<int, int>> &es,
const std::vector<T> &wt) {
assert(n >= 0 && wt.size() >= std::size_t(n));
using mask = std::uint64_t;
std::vector<std::size_t> deg(n);
for (auto [a, b] : es) {
assert(0 <= a && a < n && 0 <= b && b < n);
++deg[a];
++deg[b];
}
T ans{};
if (es.empty()) {
for (int u = 0; u < n; ++u) ans += T(1) * wt[u];
return ans;
}
std::vector<int> ord(n), rank(n);
for (int i = 0; i < n; ++i) ord[i] = i;
std::stable_sort(ord.begin(), ord.end(),
[&](int a, int b) { return deg[a] < deg[b]; });
for (int i = 0; i < n; ++i) rank[ord[i]] = i;
// Store only edges pointing forward in the fixed multiplication order.
std::vector<std::size_t> start(std::size_t(n) + 1);
for (auto [a, b] : es)
if (a != b) ++start[std::min(rank[a], rank[b]) + 1];
for (int u = 0; u < n; ++u) start[u + 1] += start[u];
std::vector<int> adj(start.back());
{
auto at = start;
for (auto [a, b] : es) {
a = rank[a];
b = rank[b];
if (a > b) std::swap(a, b);
if (a != b) adj[at[a]++] = b;
}
}
std::vector<int> id(n, -1);
std::size_t end = 0;
for (int u = 0; u < n; ++u) {
auto begin = start[u], stop = start[u + 1];
start[u] = end;
for (auto i = begin; i < stop; ++i) {
int v = adj[i];
if (id[v] != u) {
id[v] = u;
adj[end++] = v;
}
}
std::sort(adj.begin() + start[u], adj.begin() + end);
}
start[n] = end;
adj.resize(end);
std::fill(id.begin(), id.end(), -1);
auto neighbors = [&](int u) {
return std::span<const int>(adj).subspan(start[u], start[u + 1] - start[u]);
};
std::vector<mask> local, buf;
for (int root = 0; root < n; ++root) {
auto vs = neighbors(root);
int d = int(vs.size()), words = d / 64 + (d % 64 != 0);
T base = T(1) * wt[ord[root]];
ans += base;
if (!d) continue;
for (int i = 0; i < d; ++i) id[vs[i]] = i;
// A large independent neighborhood needs no quadratic local matrix.
bool ready = d <= 64;
if (ready) local.assign(d, 0);
for (int i = 0; i < d; ++i) {
for (int v : neighbors(vs[i])) {
int j = id[v];
if (j < 0) continue;
if (!ready) {
local.assign(std::size_t(d) * words, 0);
ready = true;
}
local[std::size_t(i) * words + j / 64] |= mask(1) << (j % 64);
}
}
for (int v : vs) id[v] = -1;
if (!ready) {
for (int v : vs) ans += base * wt[ord[v]];
continue;
}
if (d <= 64) {
auto dfs = [&](auto &self, mask can, const T &prod) -> void {
while (can) {
int u = std::countr_zero(can);
can &= can - 1;
T next = prod * wt[ord[vs[u]]];
ans += next;
mask nxt = can & local[u];
if (nxt) self(self, nxt, next);
}
};
dfs(dfs, d == 64 ? ~mask(0) : (mask(1) << d) - 1, base);
continue;
}
// One reusable row per depth; do not allocate for each visited clique.
buf.resize(std::size_t(d + 1) * words);
std::fill_n(buf.data(), words, ~mask(0));
if (d % 64) buf[words - 1] = (mask(1) << (d % 64)) - 1;
auto dfs = [&](auto &self, int depth, int first, const T &prod) -> void {
mask *can = buf.data() + std::size_t(depth) * words;
for (int w = first; w < words; ++w) {
while (can[w]) {
int u = w * 64 + std::countr_zero(can[w]);
can[w] &= can[w] - 1;
T next = prod * wt[ord[vs[u]]];
ans += next;
mask *nxt = can + words;
bool any = false;
for (int j = w; j < words; ++j) {
nxt[j] = can[j] & local[std::size_t(u) * words + j];
any |= nxt[j] != 0;
}
// Earlier words are already consumed and may contain stale data.
if (any) self(self, depth + 1, w, next);
}
}
};
dfs(dfs, 0, 0, base);
}
return ans;
}
} // namespace noya
// NOYA_CLIQUE_ENUMERATION_HPP
#ifndef NOYA_CLIQUE_ENUMERATION_HPP
#define NOYA_CLIQUE_ENUMERATION_HPP 1
/// @complexity Time: O(n log(n+1) + m + M D + C (1+ceil(D/64))), with M
/// distinct non-loop edges, D maximum forward degree, C nonempty cliques.
/// Space: O(n + m + D ceil(D/64)), including O(D) recursion.
#include <algorithm>
#include <bit>
#include <cassert>
#include <cstddef>
#include <cstdint>
#include <span>
#include <utility>
#include <vector>
namespace noya {
/// @brief Sum the products of vertex weights over all nonempty cliques.
/// Require n >= 0, valid endpoints and at least n weights. Loops/duplicates
/// do not create extra cliques. Keep the original order: increasing raw
/// degree (loops counted twice), then vertex ID, with depth-first prefix order.
/// T needs T{}, T(1), copying, * and +=; products are left-associated.
template <class T>
T sum_of_clique_products(int n, const std::vector<std::pair<int, int>> &es,
const std::vector<T> &wt) {
assert(n >= 0 && wt.size() >= std::size_t(n));
using mask = std::uint64_t;
std::vector<std::size_t> deg(n);
for (auto [a, b] : es) {
assert(0 <= a && a < n && 0 <= b && b < n);
++deg[a];
++deg[b];
}
T ans{};
if (es.empty()) {
for (int u = 0; u < n; ++u) ans += T(1) * wt[u];
return ans;
}
std::vector<int> ord(n), rank(n);
for (int i = 0; i < n; ++i) ord[i] = i;
std::stable_sort(ord.begin(), ord.end(),
[&](int a, int b) { return deg[a] < deg[b]; });
for (int i = 0; i < n; ++i) rank[ord[i]] = i;
// Store only edges pointing forward in the fixed multiplication order.
std::vector<std::size_t> start(std::size_t(n) + 1);
for (auto [a, b] : es)
if (a != b) ++start[std::min(rank[a], rank[b]) + 1];
for (int u = 0; u < n; ++u) start[u + 1] += start[u];
std::vector<int> adj(start.back());
{
auto at = start;
for (auto [a, b] : es) {
a = rank[a];
b = rank[b];
if (a > b) std::swap(a, b);
if (a != b) adj[at[a]++] = b;
}
}
std::vector<int> id(n, -1);
std::size_t end = 0;
for (int u = 0; u < n; ++u) {
auto begin = start[u], stop = start[u + 1];
start[u] = end;
for (auto i = begin; i < stop; ++i) {
int v = adj[i];
if (id[v] != u) {
id[v] = u;
adj[end++] = v;
}
}
std::sort(adj.begin() + start[u], adj.begin() + end);
}
start[n] = end;
adj.resize(end);
std::fill(id.begin(), id.end(), -1);
auto neighbors = [&](int u) {
return std::span<const int>(adj).subspan(start[u], start[u + 1] - start[u]);
};
std::vector<mask> local, buf;
for (int root = 0; root < n; ++root) {
auto vs = neighbors(root);
int d = int(vs.size()), words = d / 64 + (d % 64 != 0);
T base = T(1) * wt[ord[root]];
ans += base;
if (!d) continue;
for (int i = 0; i < d; ++i) id[vs[i]] = i;
// A large independent neighborhood needs no quadratic local matrix.
bool ready = d <= 64;
if (ready) local.assign(d, 0);
for (int i = 0; i < d; ++i) {
for (int v : neighbors(vs[i])) {
int j = id[v];
if (j < 0) continue;
if (!ready) {
local.assign(std::size_t(d) * words, 0);
ready = true;
}
local[std::size_t(i) * words + j / 64] |= mask(1) << (j % 64);
}
}
for (int v : vs) id[v] = -1;
if (!ready) {
for (int v : vs) ans += base * wt[ord[v]];
continue;
}
if (d <= 64) {
auto dfs = [&](auto &self, mask can, const T &prod) -> void {
while (can) {
int u = std::countr_zero(can);
can &= can - 1;
T next = prod * wt[ord[vs[u]]];
ans += next;
mask nxt = can & local[u];
if (nxt) self(self, nxt, next);
}
};
dfs(dfs, d == 64 ? ~mask(0) : (mask(1) << d) - 1, base);
continue;
}
// One reusable row per depth; do not allocate for each visited clique.
buf.resize(std::size_t(d + 1) * words);
std::fill_n(buf.data(), words, ~mask(0));
if (d % 64) buf[words - 1] = (mask(1) << (d % 64)) - 1;
auto dfs = [&](auto &self, int depth, int first, const T &prod) -> void {
mask *can = buf.data() + std::size_t(depth) * words;
for (int w = first; w < words; ++w) {
while (can[w]) {
int u = w * 64 + std::countr_zero(can[w]);
can[w] &= can[w] - 1;
T next = prod * wt[ord[vs[u]]];
ans += next;
mask *nxt = can + words;
bool any = false;
for (int j = w; j < words; ++j) {
nxt[j] = can[j] & local[std::size_t(u) * words + j];
any |= nxt[j] != 0;
}
// Earlier words are already consumed and may contain stale data.
if (any) self(self, depth + 1, w, next);
}
}
};
dfs(dfs, 0, 0, base);
}
return ans;
}
} // namespace noya
#endif // NOYA_CLIQUE_ENUMERATION_HPP
/// @complexity Time: O(n log(n+1) + m + M D + C (1+ceil(D/64))), with M
/// distinct non-loop edges, D maximum forward degree, C nonempty cliques.
/// Space: O(n + m + D ceil(D/64)), including O(D) recursion.
#include <algorithm>
#include <bit>
#include <cassert>
#include <cstddef>
#include <cstdint>
#include <span>
#include <utility>
#include <vector>
namespace noya {
/// @brief Sum the products of vertex weights over all nonempty cliques.
/// Require n >= 0, valid endpoints and at least n weights. Loops/duplicates
/// do not create extra cliques. Keep the original order: increasing raw
/// degree (loops counted twice), then vertex ID, with depth-first prefix order.
/// T needs T{}, T(1), copying, * and +=; products are left-associated.
template <class T>
T sum_of_clique_products(int n, const std::vector<std::pair<int, int>> &es,
const std::vector<T> &wt) {
assert(n >= 0 && wt.size() >= std::size_t(n));
using mask = std::uint64_t;
std::vector<std::size_t> deg(n);
for (auto [a, b] : es) {
assert(0 <= a && a < n && 0 <= b && b < n);
++deg[a];
++deg[b];
}
T ans{};
if (es.empty()) {
for (int u = 0; u < n; ++u) ans += T(1) * wt[u];
return ans;
}
std::vector<int> ord(n), rank(n);
for (int i = 0; i < n; ++i) ord[i] = i;
std::stable_sort(ord.begin(), ord.end(),
[&](int a, int b) { return deg[a] < deg[b]; });
for (int i = 0; i < n; ++i) rank[ord[i]] = i;
// Store only edges pointing forward in the fixed multiplication order.
std::vector<std::size_t> start(std::size_t(n) + 1);
for (auto [a, b] : es)
if (a != b) ++start[std::min(rank[a], rank[b]) + 1];
for (int u = 0; u < n; ++u) start[u + 1] += start[u];
std::vector<int> adj(start.back());
{
auto at = start;
for (auto [a, b] : es) {
a = rank[a];
b = rank[b];
if (a > b) std::swap(a, b);
if (a != b) adj[at[a]++] = b;
}
}
std::vector<int> id(n, -1);
std::size_t end = 0;
for (int u = 0; u < n; ++u) {
auto begin = start[u], stop = start[u + 1];
start[u] = end;
for (auto i = begin; i < stop; ++i) {
int v = adj[i];
if (id[v] != u) {
id[v] = u;
adj[end++] = v;
}
}
std::sort(adj.begin() + start[u], adj.begin() + end);
}
start[n] = end;
adj.resize(end);
std::fill(id.begin(), id.end(), -1);
auto neighbors = [&](int u) {
return std::span<const int>(adj).subspan(start[u], start[u + 1] - start[u]);
};
std::vector<mask> local, buf;
for (int root = 0; root < n; ++root) {
auto vs = neighbors(root);
int d = int(vs.size()), words = d / 64 + (d % 64 != 0);
T base = T(1) * wt[ord[root]];
ans += base;
if (!d) continue;
for (int i = 0; i < d; ++i) id[vs[i]] = i;
// A large independent neighborhood needs no quadratic local matrix.
bool ready = d <= 64;
if (ready) local.assign(d, 0);
for (int i = 0; i < d; ++i) {
for (int v : neighbors(vs[i])) {
int j = id[v];
if (j < 0) continue;
if (!ready) {
local.assign(std::size_t(d) * words, 0);
ready = true;
}
local[std::size_t(i) * words + j / 64] |= mask(1) << (j % 64);
}
}
for (int v : vs) id[v] = -1;
if (!ready) {
for (int v : vs) ans += base * wt[ord[v]];
continue;
}
if (d <= 64) {
auto dfs = [&](auto &self, mask can, const T &prod) -> void {
while (can) {
int u = std::countr_zero(can);
can &= can - 1;
T next = prod * wt[ord[vs[u]]];
ans += next;
mask nxt = can & local[u];
if (nxt) self(self, nxt, next);
}
};
dfs(dfs, d == 64 ? ~mask(0) : (mask(1) << d) - 1, base);
continue;
}
// One reusable row per depth; do not allocate for each visited clique.
buf.resize(std::size_t(d + 1) * words);
std::fill_n(buf.data(), words, ~mask(0));
if (d % 64) buf[words - 1] = (mask(1) << (d % 64)) - 1;
auto dfs = [&](auto &self, int depth, int first, const T &prod) -> void {
mask *can = buf.data() + std::size_t(depth) * words;
for (int w = first; w < words; ++w) {
while (can[w]) {
int u = w * 64 + std::countr_zero(can[w]);
can[w] &= can[w] - 1;
T next = prod * wt[ord[vs[u]]];
ans += next;
mask *nxt = can + words;
bool any = false;
for (int j = w; j < words; ++j) {
nxt[j] = can[j] & local[std::size_t(u) * words + j];
any |= nxt[j] != 0;
}
// Earlier words are already consumed and may contain stale data.
if (any) self(self, depth + 1, w, next);
}
}
};
dfs(dfs, 0, 0, base);
}
return ans;
}
} // namespace noya
// NOYA_CLIQUE_ENUMERATION_HPP