forked from righier/filter-kruskal
-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathpivot.hpp
33 lines (26 loc) · 920 Bytes
/
pivot.hpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#pragma once
#include <math.h>
#include <algorithm>
#include "utils/graph.hpp"
#include "utils/random.hpp"
// picks the pivot randomply from the edge list and moves it to the start of the
// list
static inline EdgeIt pickRandomPivot(EdgeIt &first, EdgeIt &last) {
static Random rnd(31);
EdgeIt pivotPos = first + rnd.getULong(last - first);
std::swap(*pivotPos, *first);
return first++;
}
// picks sqrt(k) samples and returns the start iterator of the samples
// (the prefix is filled with the samples)
static inline EdgeIt pickRandomSampleRootK(EdgeIt &first, EdgeIt &last) {
static Random rnd(31);
int nSamples = std::max(int(std::sqrt(last - first)), 1);
EdgeIt firstSample = first;
for (int i = 0; i < nSamples; i++) {
EdgeIt picked = first + rnd.getULong(last - first);
std::swap(*(first++), *picked);
}
std::sort(firstSample, first);
return firstSample;
}