seams-core v2.14.0
libyodaLib, the C++ engine of d-SEAMS
Loading...
Searching...
No Matches
edge_set.hpp
Go to the documentation of this file.
1#ifndef SEAMS_EDGE_SET_H_
2#define SEAMS_EDGE_SET_H_
3
4#include <algorithm>
5#include <cstdint>
6#include <utility>
7#include <vector>
8
9#ifdef SEAMS_HAS_OPENMP
10#include <omp.h>
11#endif
12
13namespace seams {
14
15// Undirected edges, self entries dropped, each pair stored once as (lo, hi)
16// and sorted. The hash is FNV-1a over that list. Reuse is allowed only when
17// the hashes match and the lists then compare equal. A hash match alone is
18// not enough.
19struct EdgeSet {
20 std::uint64_t hash = 1469598103934665603ull;
21 std::vector<std::pair<int, int>> edges;
22};
23
24namespace {
25
26void sortEdgePairs(std::vector<std::pair<int, int>> &edges) {
27#if !defined(SEAMS_HAS_OPENMP)
28 std::sort(edges.begin(), edges.end());
29#else
30 const std::size_t n = edges.size();
31 const int nT = omp_get_max_threads();
32 if (n < 8192 || nT < 2 || omp_in_parallel()) {
33 std::sort(edges.begin(), edges.end());
34 return;
35 }
36 const std::size_t chunk =
37 (n + static_cast<std::size_t>(nT) - 1) / static_cast<std::size_t>(nT);
38#pragma omp parallel for schedule(static)
39 for (int t = 0; t < nT; ++t) {
40 const std::size_t begin = static_cast<std::size_t>(t) * chunk;
41 if (begin >= n) {
42 continue;
43 }
44 const std::size_t end = std::min(n, begin + chunk);
45 std::sort(edges.begin() + static_cast<std::ptrdiff_t>(begin),
46 edges.begin() + static_cast<std::ptrdiff_t>(end));
47 }
48 for (std::size_t width = chunk; width < n; width *= 2) {
49 const std::size_t span = width * 2;
50 const int blocks =
51 static_cast<int>((n + span - 1) / span);
52#pragma omp parallel for schedule(static)
53 for (int b = 0; b < blocks; ++b) {
54 const std::size_t begin = static_cast<std::size_t>(b) * span;
55 const std::size_t mid = std::min(n, begin + width);
56 const std::size_t end = std::min(n, begin + span);
57 if (begin < mid && mid < end) {
58 std::inplace_merge(edges.begin() + static_cast<std::ptrdiff_t>(begin),
59 edges.begin() + static_cast<std::ptrdiff_t>(mid),
60 edges.begin() + static_cast<std::ptrdiff_t>(end));
61 }
62 }
63 }
64#endif
65}
66
67void hashEdges(EdgeSet &out) {
68 std::uint64_t h = 1469598103934665603ull;
69 for (const auto &e : out.edges) {
70 h ^= static_cast<std::uint64_t>(static_cast<std::uint32_t>(e.first));
71 h *= 1099511628211ull;
72 h ^= static_cast<std::uint64_t>(static_cast<std::uint32_t>(e.second));
73 h *= 1099511628211ull;
74 }
75 out.hash = h;
76}
77
78} // namespace
79
80inline EdgeSet edgeSetOf(const std::vector<std::vector<int>> &rows) {
81 EdgeSet out;
82 const int nRows = static_cast<int>(rows.size());
83 bool parallel = false;
84#ifdef SEAMS_HAS_OPENMP
85 parallel = nRows >= 4096 && omp_get_max_threads() > 1 && !omp_in_parallel();
86#endif
87 if (parallel) {
88#ifdef SEAMS_HAS_OPENMP
89 const int team = omp_get_max_threads();
90 std::vector<std::vector<std::pair<int, int>>> parts(
91 static_cast<std::size_t>(team));
92#pragma omp parallel
93 {
94 std::vector<std::pair<int, int>> local;
95#pragma omp for schedule(static)
96 for (int i = 0; i < nRows; ++i) {
97 const auto &row = rows[static_cast<std::size_t>(i)];
98 for (std::size_t k = 1; k < row.size(); ++k) {
99 const int j = row[k];
100 if (j < 0 || j == i) {
101 continue;
102 }
103 local.emplace_back(std::min(i, j), std::max(i, j));
104 }
105 }
106 parts[static_cast<std::size_t>(omp_get_thread_num())] = std::move(local);
107 }
108 std::size_t total = 0;
109 for (const auto &part : parts) {
110 total += part.size();
111 }
112 out.edges.reserve(total);
113 for (auto &part : parts) {
114 out.edges.insert(out.edges.end(), part.begin(), part.end());
115 }
116#endif
117 } else {
118 for (int i = 0; i < nRows; ++i) {
119 const auto &row = rows[static_cast<std::size_t>(i)];
120 for (std::size_t k = 1; k < row.size(); ++k) {
121 const int j = row[k];
122 if (j < 0 || j == i) {
123 continue;
124 }
125 out.edges.emplace_back(std::min(i, j), std::max(i, j));
126 }
127 }
128 }
129 sortEdgePairs(out.edges);
130 out.edges.erase(std::unique(out.edges.begin(), out.edges.end()), out.edges.end());
131 hashEdges(out);
132 return out;
133}
134
135inline bool provenEqual(const EdgeSet &a, const EdgeSet &b) {
136 if (a.hash != b.hash) {
137 return false;
138 }
139 return a.edges == b.edges;
140}
141
142} // namespace seams
143
144#endif
EdgeSet edgeSetOf(const std::vector< std::vector< int > > &rows)
Definition edge_set.hpp:80
bool provenEqual(const EdgeSet &a, const EdgeSet &b)
Definition edge_set.hpp:135
std::vector< std::pair< int, int > > edges
Definition edge_set.hpp:21
std::uint64_t hash
Definition edge_set.hpp:20