small_cycle_count.hpp¶
Count triangles in an undirected simple graph in O(m sqrt(m)) orientation time; duplicate input edges and self-loops are ignored.
Verified by enumerate_triangles.
统计简单图中的小长度环（如三角形、四边形等），用于固定小环计数。
Implementation¶
#ifndef NOYA_SMALL_CYCLE_COUNT_HPP
#define NOYA_SMALL_CYCLE_COUNT_HPP 1
/// @complexity Time: O(E sqrt(E)) triangle counting and O(E^(3/2)) four-cycle counting.
/// Space: O(V + E).
#include <algorithm>
#include <cassert>
#include <cstdint>
#include <unordered_map>
#include <utility>
#include <vector>
namespace noya {
namespace small_cycle_count_internal {
inline std::vector<std::pair<int, int>>
simple_edges(int n, std::vector<std::pair<int, int>> edges) {
for (auto &[first, second] : edges) {
assert(0 <= first && first < n);
assert(0 <= second && second < n);
if (first > second) {
std::swap(first, second);
}
}
edges.erase(
std::remove_if(edges.begin(), edges.end(),
[](auto edge) { return edge.first == edge.second; }),
edges.end());
std::sort(edges.begin(), edges.end());
edges.erase(std::unique(edges.begin(), edges.end()), edges.end());
return edges;
}
} // namespace small_cycle_count_internal
/// @brief Count triangles in an undirected simple graph in O(m sqrt(m))
/// orientation time; duplicate input edges and self-loops are ignored.
inline std::uint64_t triangle_count(int n,
std::vector<std::pair<int, int>> edges) {
edges = small_cycle_count_internal::simple_edges(n, std::move(edges));
std::vector<int> degree(n);
for (auto [first, second] : edges) {
degree[first]++;
degree[second]++;
}
std::vector<std::vector<int>> outgoing(n);
for (auto [first, second] : edges) {
if (std::tie(degree[first], first) > std::tie(degree[second], second)) {
std::swap(first, second);
}
outgoing[first].push_back(second);
}
std::vector<bool> marked(n);
std::uint64_t result = 0;
for (int first = 0; first < n; first++) {
for (int second : outgoing[first]) {
marked[second] = true;
}
for (int second : outgoing[first]) {
for (int third : outgoing[second]) {
result += marked[third];
}
}
for (int second : outgoing[first]) {
marked[second] = false;
}
}
return result;
}
/// @brief Sum weight[a]*weight[b]*weight[c] over all triangles of a simple
/// graph. Orienting every edge toward the larger (degree, vertex) endpoint
/// bounds every out-degree by O(sqrt(m)); intersecting outgoing lists then
/// visits each triangle once in O(m sqrt(m)) time.
template <class T>
T weighted_triangle_sum(int n, const std::vector<std::pair<int, int>> &edges,
const std::vector<T> &weight) {
assert(int(weight.size()) == n);
std::vector<int> degree(n);
for (auto [first, second] : edges) {
assert(0 <= first && first < n && 0 <= second && second < n);
assert(first != second);
degree[first]++;
degree[second]++;
}
std::vector<std::vector<int>> outgoing(n);
for (auto [first, second] : edges) {
if (std::tie(degree[first], first) > std::tie(degree[second], second)) {
std::swap(first, second);
}
outgoing[first].push_back(second);
}
std::vector<bool> marked(n);
T result{};
for (int first = 0; first < n; first++) {
for (int second : outgoing[first]) {
marked[second] = true;
}
for (int second : outgoing[first]) {
for (int third : outgoing[second]) {
if (marked[third]) {
result += weight[first] * weight[second] * weight[third];
}
}
}
for (int second : outgoing[first]) {
marked[second] = false;
}
}
return result;
}
/// @brief Count (not necessarily induced) four-cycles in an undirected simple
/// graph in O(sum degree^2); duplicate input edges and self-loops are ignored.
inline std::uint64_t four_cycle_count(int n,
std::vector<std::pair<int, int>> edges) {
edges = small_cycle_count_internal::simple_edges(n, std::move(edges));
std::vector<std::vector<int>> graph(n);
for (auto [first, second] : edges) {
graph[first].push_back(second);
graph[second].push_back(first);
}
std::unordered_map<std::uint64_t, std::uint64_t> common;
std::uint64_t doubled = 0;
for (int middle = 0; middle < n; middle++) {
auto &neighbors = graph[middle];
for (int first_index = 0; first_index < int(neighbors.size());
first_index++) {
for (int second_index = first_index + 1;
second_index < int(neighbors.size()); second_index++) {
std::uint32_t first = neighbors[first_index];
std::uint32_t second = neighbors[second_index];
if (first > second) {
std::swap(first, second);
}
std::uint64_t key = (std::uint64_t(first) << 32) | second;
doubled += common[key]++;
}
}
}
return doubled / 2;
}
} // namespace noya
#endif // NOYA_SMALL_CYCLE_COUNT_HPP
#include <algorithm>
#include <cassert>
#include <cstdint>
#include <unordered_map>
#include <utility>
#include <vector>
/// @complexity Time: O(E sqrt(E)) triangle counting and O(E^(3/2)) four-cycle counting.
/// Space: O(V + E).
namespace noya {
namespace small_cycle_count_internal {
inline std::vector<std::pair<int, int>>
simple_edges(int n, std::vector<std::pair<int, int>> edges) {
for (auto &[first, second] : edges) {
assert(0 <= first && first < n);
assert(0 <= second && second < n);
if (first > second) {
std::swap(first, second);
}
}
edges.erase(
std::remove_if(edges.begin(), edges.end(),
[](auto edge) { return edge.first == edge.second; }),
edges.end());
std::sort(edges.begin(), edges.end());
edges.erase(std::unique(edges.begin(), edges.end()), edges.end());
return edges;
}
} // namespace small_cycle_count_internal
/// @brief Count triangles in an undirected simple graph in O(m sqrt(m))
/// orientation time; duplicate input edges and self-loops are ignored.
inline std::uint64_t triangle_count(int n,
std::vector<std::pair<int, int>> edges) {
edges = small_cycle_count_internal::simple_edges(n, std::move(edges));
std::vector<int> degree(n);
for (auto [first, second] : edges) {
degree[first]++;
degree[second]++;
}
std::vector<std::vector<int>> outgoing(n);
for (auto [first, second] : edges) {
if (std::tie(degree[first], first) > std::tie(degree[second], second)) {
std::swap(first, second);
}
outgoing[first].push_back(second);
}
std::vector<bool> marked(n);
std::uint64_t result = 0;
for (int first = 0; first < n; first++) {
for (int second : outgoing[first]) {
marked[second] = true;
}
for (int second : outgoing[first]) {
for (int third : outgoing[second]) {
result += marked[third];
}
}
for (int second : outgoing[first]) {
marked[second] = false;
}
}
return result;
}
/// @brief Sum weight[a]*weight[b]*weight[c] over all triangles of a simple
/// graph. Orienting every edge toward the larger (degree, vertex) endpoint
/// bounds every out-degree by O(sqrt(m)); intersecting outgoing lists then
/// visits each triangle once in O(m sqrt(m)) time.
template <class T>
T weighted_triangle_sum(int n, const std::vector<std::pair<int, int>> &edges,
const std::vector<T> &weight) {
assert(int(weight.size()) == n);
std::vector<int> degree(n);
for (auto [first, second] : edges) {
assert(0 <= first && first < n && 0 <= second && second < n);
assert(first != second);
degree[first]++;
degree[second]++;
}
std::vector<std::vector<int>> outgoing(n);
for (auto [first, second] : edges) {
if (std::tie(degree[first], first) > std::tie(degree[second], second)) {
std::swap(first, second);
}
outgoing[first].push_back(second);
}
std::vector<bool> marked(n);
T result{};
for (int first = 0; first < n; first++) {
for (int second : outgoing[first]) {
marked[second] = true;
}
for (int second : outgoing[first]) {
for (int third : outgoing[second]) {
if (marked[third]) {
result += weight[first] * weight[second] * weight[third];
}
}
}
for (int second : outgoing[first]) {
marked[second] = false;
}
}
return result;
}
/// @brief Count (not necessarily induced) four-cycles in an undirected simple
/// graph in O(sum degree^2); duplicate input edges and self-loops are ignored.
inline std::uint64_t four_cycle_count(int n,
std::vector<std::pair<int, int>> edges) {
edges = small_cycle_count_internal::simple_edges(n, std::move(edges));
std::vector<std::vector<int>> graph(n);
for (auto [first, second] : edges) {
graph[first].push_back(second);
graph[second].push_back(first);
}
std::unordered_map<std::uint64_t, std::uint64_t> common;
std::uint64_t doubled = 0;
for (int middle = 0; middle < n; middle++) {
auto &neighbors = graph[middle];
for (int first_index = 0; first_index < int(neighbors.size());
first_index++) {
for (int second_index = first_index + 1;
second_index < int(neighbors.size()); second_index++) {
std::uint32_t first = neighbors[first_index];
std::uint32_t second = neighbors[second_index];
if (first > second) {
std::swap(first, second);
}
std::uint64_t key = (std::uint64_t(first) << 32) | second;
doubled += common[key]++;
}
}
}
return doubled / 2;
}
} // namespace noya