small_cycle_count.hpp

SECTIONGraph INCLUDEnoya/small_cycle_count.hpp

统计简单图中的小长度环（如三角形、四边形等），用于固定小环计数。

Complexity: Time: O(E sqrt(E)) triangle counting and O(sum_v deg(v)^2) four-cycle counting (in worst case O(E^2)). Space: O(V + E + K), where K is number of seen vertex pairs.

AC 记录：enumerate_triangles。

跳到代码 · GitHub ↗

Implementation

ReferenceSourceExpanded

当前头文件，省略 include guard；依赖见 #include。

/// @complexity Time: O(E sqrt(E)) triangle counting and
/// O(sum_v deg(v)^2) four-cycle counting (in worst case O(E^2)).
/// Space: O(V + E + K), where K is number of seen vertex pairs.

#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>> es) {
  for (auto &[a, b] : es) {
    assert(0 <= a && a < n);
    assert(0 <= b && b < n);
    if (a > b) {
      std::swap(a, b);
    }
  }
  es.erase(std::remove_if(es.begin(), es.end(),
                          [](auto e) { return e.first == e.second; }),
           es.end());
  std::sort(es.begin(), es.end());
  es.erase(std::unique(es.begin(), es.end()), es.end());
  return es;
}

} // 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>> es) {
  es = small_cycle_count_internal::simple_edges(n, std::move(es));
  std::vector<int> deg(n);
  for (auto [a, b] : es) {
    deg[a]++;
    deg[b]++;
  }
  std::vector<std::vector<int>> out(n);
  for (auto [a, b] : es) {
    if (std::tie(deg[a], a) > std::tie(deg[b], b)) {
      std::swap(a, b);
    }
    out[a].push_back(b);
  }
  std::vector<bool> vis(n);
  std::uint64_t res = 0;
  for (int a = 0; a < n; a++) {
    for (int b : out[a]) {
      vis[b] = true;
    }
    for (int b : out[a]) {
      for (int c : out[b]) {
        res += vis[c];
      }
    }
    for (int b : out[a]) {
      vis[b] = false;
    }
  }
  return res;
}

/// @brief Sum w[a]*w[b]*w[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>> &es,
                        const std::vector<T> &w) {
  assert(int(w.size()) == n);
  std::vector<int> deg(n);
  for (auto [a, b] : es) {
    assert(0 <= a && a < n && 0 <= b && b < n);
    assert(a != b);
    deg[a]++;
    deg[b]++;
  }
  std::vector<std::vector<int>> out(n);
  for (auto [a, b] : es) {
    if (std::tie(deg[a], a) > std::tie(deg[b], b)) {
      std::swap(a, b);
    }
    out[a].push_back(b);
  }
  std::vector<bool> vis(n);
  T res{};
  for (int a = 0; a < n; a++) {
    for (int b : out[a]) {
      vis[b] = true;
    }
    for (int b : out[a]) {
      for (int c : out[b]) {
        if (vis[c]) {
          res += w[a] * w[b] * w[c];
        }
      }
    }
    for (int b : out[a]) {
      vis[b] = false;
    }
  }
  return res;
}

/// @brief Count (not necessarily induced) four-cycles in an undirected simple
/// graph in O(sum_v deg(v)^2) time; duplicate input edges and self-loops are
/// ignored.
inline std::uint64_t four_cycle_count(int n,
                                      std::vector<std::pair<int, int>> es) {
  es = small_cycle_count_internal::simple_edges(n, std::move(es));
  std::vector<std::vector<int>> g(n);
  for (auto [a, b] : es) {
    g[a].push_back(b);
    g[b].push_back(a);
  }
  std::unordered_map<std::uint64_t, std::uint64_t> com;
  std::uint64_t d2 = 0;
  for (int mid = 0; mid < n; mid++) {
    auto &adj = g[mid];
    for (int i1 = 0; i1 < int(adj.size()); i1++) {
      for (int i2 = i1 + 1; i2 < int(adj.size()); i2++) {
        std::uint32_t a = adj[i1];
        std::uint32_t b = adj[i2];
        if (a > b) {
          std::swap(a, b);
        }
        std::uint64_t key = (std::uint64_t(a) << 32) | b;
        d2 += com[key]++;
      }
    }
  }
  return d2 / 2;
}

} // namespace noya

#ifndef NOYA_SMALL_CYCLE_COUNT_HPP
#define NOYA_SMALL_CYCLE_COUNT_HPP 1

/// @complexity Time: O(E sqrt(E)) triangle counting and
/// O(sum_v deg(v)^2) four-cycle counting (in worst case O(E^2)).
/// Space: O(V + E + K), where K is number of seen vertex pairs.

#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>> es) {
  for (auto &[a, b] : es) {
    assert(0 <= a && a < n);
    assert(0 <= b && b < n);
    if (a > b) {
      std::swap(a, b);
    }
  }
  es.erase(std::remove_if(es.begin(), es.end(),
                          [](auto e) { return e.first == e.second; }),
           es.end());
  std::sort(es.begin(), es.end());
  es.erase(std::unique(es.begin(), es.end()), es.end());
  return es;
}

} // 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>> es) {
  es = small_cycle_count_internal::simple_edges(n, std::move(es));
  std::vector<int> deg(n);
  for (auto [a, b] : es) {
    deg[a]++;
    deg[b]++;
  }
  std::vector<std::vector<int>> out(n);
  for (auto [a, b] : es) {
    if (std::tie(deg[a], a) > std::tie(deg[b], b)) {
      std::swap(a, b);
    }
    out[a].push_back(b);
  }
  std::vector<bool> vis(n);
  std::uint64_t res = 0;
  for (int a = 0; a < n; a++) {
    for (int b : out[a]) {
      vis[b] = true;
    }
    for (int b : out[a]) {
      for (int c : out[b]) {
        res += vis[c];
      }
    }
    for (int b : out[a]) {
      vis[b] = false;
    }
  }
  return res;
}

/// @brief Sum w[a]*w[b]*w[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>> &es,
                        const std::vector<T> &w) {
  assert(int(w.size()) == n);
  std::vector<int> deg(n);
  for (auto [a, b] : es) {
    assert(0 <= a && a < n && 0 <= b && b < n);
    assert(a != b);
    deg[a]++;
    deg[b]++;
  }
  std::vector<std::vector<int>> out(n);
  for (auto [a, b] : es) {
    if (std::tie(deg[a], a) > std::tie(deg[b], b)) {
      std::swap(a, b);
    }
    out[a].push_back(b);
  }
  std::vector<bool> vis(n);
  T res{};
  for (int a = 0; a < n; a++) {
    for (int b : out[a]) {
      vis[b] = true;
    }
    for (int b : out[a]) {
      for (int c : out[b]) {
        if (vis[c]) {
          res += w[a] * w[b] * w[c];
        }
      }
    }
    for (int b : out[a]) {
      vis[b] = false;
    }
  }
  return res;
}

/// @brief Count (not necessarily induced) four-cycles in an undirected simple
/// graph in O(sum_v deg(v)^2) time; duplicate input edges and self-loops are
/// ignored.
inline std::uint64_t four_cycle_count(int n,
                                      std::vector<std::pair<int, int>> es) {
  es = small_cycle_count_internal::simple_edges(n, std::move(es));
  std::vector<std::vector<int>> g(n);
  for (auto [a, b] : es) {
    g[a].push_back(b);
    g[b].push_back(a);
  }
  std::unordered_map<std::uint64_t, std::uint64_t> com;
  std::uint64_t d2 = 0;
  for (int mid = 0; mid < n; mid++) {
    auto &adj = g[mid];
    for (int i1 = 0; i1 < int(adj.size()); i1++) {
      for (int i2 = i1 + 1; i2 < int(adj.size()); i2++) {
        std::uint32_t a = adj[i1];
        std::uint32_t b = adj[i2];
        if (a > b) {
          std::swap(a, b);
        }
        std::uint64_t key = (std::uint64_t(a) << 32) | b;
        d2 += com[key]++;
      }
    }
  }
  return d2 / 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(sum_v deg(v)^2) four-cycle counting (in worst case O(E^2)).
/// Space: O(V + E + K), where K is number of seen vertex pairs.

namespace noya {
namespace small_cycle_count_internal {

inline std::vector<std::pair<int, int>>
simple_edges(int n, std::vector<std::pair<int, int>> es) {
  for (auto &[a, b] : es) {
    assert(0 <= a && a < n);
    assert(0 <= b && b < n);
    if (a > b) {
      std::swap(a, b);
    }
  }
  es.erase(std::remove_if(es.begin(), es.end(),
                          [](auto e) { return e.first == e.second; }),
           es.end());
  std::sort(es.begin(), es.end());
  es.erase(std::unique(es.begin(), es.end()), es.end());
  return es;
}

} // 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>> es) {
  es = small_cycle_count_internal::simple_edges(n, std::move(es));
  std::vector<int> deg(n);
  for (auto [a, b] : es) {
    deg[a]++;
    deg[b]++;
  }
  std::vector<std::vector<int>> out(n);
  for (auto [a, b] : es) {
    if (std::tie(deg[a], a) > std::tie(deg[b], b)) {
      std::swap(a, b);
    }
    out[a].push_back(b);
  }
  std::vector<bool> vis(n);
  std::uint64_t res = 0;
  for (int a = 0; a < n; a++) {
    for (int b : out[a]) {
      vis[b] = true;
    }
    for (int b : out[a]) {
      for (int c : out[b]) {
        res += vis[c];
      }
    }
    for (int b : out[a]) {
      vis[b] = false;
    }
  }
  return res;
}

/// @brief Sum w[a]*w[b]*w[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>> &es,
                        const std::vector<T> &w) {
  assert(int(w.size()) == n);
  std::vector<int> deg(n);
  for (auto [a, b] : es) {
    assert(0 <= a && a < n && 0 <= b && b < n);
    assert(a != b);
    deg[a]++;
    deg[b]++;
  }
  std::vector<std::vector<int>> out(n);
  for (auto [a, b] : es) {
    if (std::tie(deg[a], a) > std::tie(deg[b], b)) {
      std::swap(a, b);
    }
    out[a].push_back(b);
  }
  std::vector<bool> vis(n);
  T res{};
  for (int a = 0; a < n; a++) {
    for (int b : out[a]) {
      vis[b] = true;
    }
    for (int b : out[a]) {
      for (int c : out[b]) {
        if (vis[c]) {
          res += w[a] * w[b] * w[c];
        }
      }
    }
    for (int b : out[a]) {
      vis[b] = false;
    }
  }
  return res;
}

/// @brief Count (not necessarily induced) four-cycles in an undirected simple
/// graph in O(sum_v deg(v)^2) time; duplicate input edges and self-loops are
/// ignored.
inline std::uint64_t four_cycle_count(int n,
                                      std::vector<std::pair<int, int>> es) {
  es = small_cycle_count_internal::simple_edges(n, std::move(es));
  std::vector<std::vector<int>> g(n);
  for (auto [a, b] : es) {
    g[a].push_back(b);
    g[b].push_back(a);
  }
  std::unordered_map<std::uint64_t, std::uint64_t> com;
  std::uint64_t d2 = 0;
  for (int mid = 0; mid < n; mid++) {
    auto &adj = g[mid];
    for (int i1 = 0; i1 < int(adj.size()); i1++) {
      for (int i2 = i1 + 1; i2 < int(adj.size()); i2++) {
        std::uint32_t a = adj[i1];
        std::uint32_t b = adj[i2];
        if (a > b) {
          std::swap(a, b);
        }
        std::uint64_t key = (std::uint64_t(a) << 32) | b;
        d2 += com[key]++;
      }
    }
  }
  return d2 / 2;
}

} // namespace noya