GitHub Viewer
// 2019/02/15 - modified by Tsung-Wei Huang
// - refactored the code
//
// 2019/01/03 - created by Chun-Xun Lin
// - use dynamic tasking to implement graph traversal
#include
#include
#include
#include
struct Node {
size_t level {0};
bool visited {false};
std::atomic dependents {0};
std::vector successors;
void precede(Node& n) {
successors.emplace_back(&n);
n.dependents ++;
}
};
void traverse(Node* n, tf::SubflowBuilder& subflow) {
assert(!n->visited);
n->visited = true;
for(size_t i=0; isuccessors.size(); i++) {
if(--(n->successors[i]->dependents) == 0) {
n->successors[i]->level = n->level + 1;
subflow.emplace([s=n->successors[i]](tf::SubflowBuilder &subflow){
traverse(s, subflow);
});
}
}
}
void sequential_traversal(std::vector& src) {
auto start = std::chrono::system_clock::now();
while(!src.empty()) {
auto n = src.back();
assert(!n->visited);
n->visited = true;
src.pop_back();
for(auto& s: n->successors) {
if(--s->dependents == 0) {
s->level = n->level + 1;
src.emplace_back(s);
}
}
}
auto end = std::chrono::system_clock::now();
std::cout