-
Notifications
You must be signed in to change notification settings - Fork 6
/
Copy pathclique.hpp
executable file
·200 lines (182 loc) · 5.99 KB
/
clique.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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
#ifndef ENUMERABLE_CLIQUE_H
#define ENUMERABLE_CLIQUE_H
#include <cstdint>
#include <memory>
#include <vector>
#include "enumerable/enumerable.hpp"
#include "permute/permute.hpp"
#include "util/graph.hpp"
template <typename node_t>
using Clique = std::vector<node_t>;
template <typename node_t>
using CliqueEnumerationNode = std::pair<Clique<node_t>, node_t>;
#define DEGENERACY
template <typename Graph>
class CliqueEnumeration
: public Enumerable<CliqueEnumerationNode<typename Graph::node_t>,
Clique<typename Graph::node_t>> {
public:
using node_t = typename Graph::node_t;
using NodeCallback = typename Enumerable<CliqueEnumerationNode<node_t>,
Clique<node_t>>::NodeCallback;
explicit CliqueEnumeration(Graph* graph)
:graph_(
#ifndef DEGENERACY
graph->Clone()
#else
graph->Permute(DegeneracyOrder(*graph))
#endif
){}
void SetUp() override {
candidates_bitset_.resize(graph_->size());
bad_bitset_.resize(graph_->size());
}
size_t MaxRoots() override { return graph_->size(); }
void GetRoot(size_t i, const NodeCallback& cb) override {
std::pair<std::vector<node_t>, node_t> root;
if (graph_->degree(i) == graph_->fwd_degree(i)) {
root.first.clear();
root.first.push_back(i);
root.second = i;
CompleteFwd(&root.first);
cb(root);
}
}
void ListChildren(const CliqueEnumerationNode<node_t>& clique_info,
const NodeCallback& cb) override {
const std::vector<node_t>& clique = clique_info.first;
node_t parind = clique_info.second;
assert(!clique.empty());
node_t max_bad = clique.front();
for (node_t neigh : graph_->fwd_neighs(clique.front())) {
bool ok = true;
for (node_t node : clique) {
if (node > neigh) break;
if (!graph_->are_neighs(neigh, node)) {
ok = false;
break;
}
}
if (ok) {
bad_bitset_[neigh] = true;
bad_.push_back(neigh);
}
if (ok && max_bad < neigh) {
max_bad = neigh;
}
}
Candidates(clique, parind, [this, max_bad, &clique, &cb](node_t cand) {
return ChildrenCand(
clique, cand,
[this, max_bad, cand, &clique, &cb](std::vector<node_t>* child) {
node_t idx = child->front();
for (node_t node : *child)
if (graph_->degree(node) < graph_->degree(idx)) {
idx = node;
}
for (node_t neigh : graph_->neighs(idx)) {
bool works = true;
for (node_t node : *child) {
if (!graph_->are_neighs(neigh, node)) {
works = false;
break;
}
}
if (works) {
if (neigh < clique.front()) return true;
if (neigh <= cand && graph_->are_neighs(neigh, cand))
return true;
if (bad_bitset_[neigh]) return true;
}
}
std::pair<std::vector<node_t>, node_t> child_info;
child_info.second = cand;
child->push_back(cand);
CompleteFwd(child);
child_info.first = *child;
return cb(child_info);
});
});
for (node_t b : bad_) bad_bitset_[b] = false;
bad_.clear();
}
Clique<node_t> NodeToItem(
const CliqueEnumerationNode<node_t>& node) override {
return node.first;
}
private:
void CompleteSmallest(std::vector<node_t>* clique, node_t small) {
for (node_t neigh : graph_->fwd_neighs(small)) {
bool can_add = true;
for (node_t node : *clique) {
if (!graph_->are_neighs(neigh, node)) {
can_add = false;
break;
}
}
if (can_add) clique->push_back(neigh);
}
}
void Candidates(const std::vector<node_t>& clique, node_t parind,
const std::function<bool(node_t)>& callback) {
for (node_t node : clique) {
candidates_bitset_[node] = true;
}
for (node_t node : clique) {
for (node_t neigh : graph_->fwd_neighs(node)) {
if (neigh > parind && !candidates_bitset_[neigh]) {
candidates_bitset_[neigh] = true;
candidates_.push_back(neigh);
}
}
}
for (node_t node : clique) {
candidates_bitset_[node] = false;
}
for (node_t node : candidates_) {
if (!callback(node)) {
break;
}
}
for (node_t node : candidates_) {
candidates_bitset_[node] = false;
}
candidates_.clear();
}
bool ChildrenCand(const std::vector<node_t>& clique, node_t cand,
const std::function<bool(std::vector<node_t>*)>& callback) {
for (node_t node : clique) {
if (node > cand) continue;
if (graph_->are_neighs(cand, node)) {
child_.push_back(node);
}
}
bool go_on = callback(&child_);
child_.clear();
return go_on;
}
void CompleteFwd(std::vector<node_t>* clique) {
CompleteSmallest(clique, clique->front());
}
static thread_local std::vector<bool> candidates_bitset_;
static thread_local std::vector<node_t> candidates_;
static thread_local std::vector<node_t> child_;
static thread_local std::vector<bool> bad_bitset_;
static thread_local std::vector<node_t> bad_;
std::unique_ptr<Graph> graph_;
};
template <typename Graph>
thread_local std::vector<bool> CliqueEnumeration<Graph>::candidates_bitset_;
template <typename Graph>
thread_local std::vector<typename Graph::node_t>
CliqueEnumeration<Graph>::candidates_;
template <typename Graph>
thread_local std::vector<typename Graph::node_t>
CliqueEnumeration<Graph>::child_;
template <typename Graph>
thread_local std::vector<bool> CliqueEnumeration<Graph>::bad_bitset_;
template <typename Graph>
thread_local std::vector<typename Graph::node_t> CliqueEnumeration<Graph>::bad_;
extern template class CliqueEnumeration<fast_graph_t<uint32_t, void>>;
extern template class CliqueEnumeration<fast_graph_t<uint64_t, void>>;
#endif // ENUMERABLE_CLIQUE_H