d-SEAMS
Install
Output
Methods
Docs
Engine & CLI
Python
Rust
Julia
R
Lua / Fennel
Fortran
PLUMED
linkcell
Wiki
Cite
GitHub
seams-core
v2.14.0
libyodaLib, the C++ engine of d-SEAMS
Toggle main menu visibility
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
13
namespace
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.
19
struct
EdgeSet
{
20
std::uint64_t
hash
= 1469598103934665603ull;
21
std::vector<std::pair<int, int>>
edges
;
22
};
23
24
namespace
{
25
26
void
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
67
void
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
80
inline
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
135
inline
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
seams
Definition
cpu_features.hpp:30
seams::edgeSetOf
EdgeSet edgeSetOf(const std::vector< std::vector< int > > &rows)
Definition
edge_set.hpp:80
seams::provenEqual
bool provenEqual(const EdgeSet &a, const EdgeSet &b)
Definition
edge_set.hpp:135
seams::EdgeSet
Definition
edge_set.hpp:19
seams::EdgeSet::edges
std::vector< std::pair< int, int > > edges
Definition
edge_set.hpp:21
seams::EdgeSet::hash
std::uint64_t hash
Definition
edge_set.hpp:20
src
include
internal
edge_set.hpp