sleepy-bfs.cpp

#include <stdio.h>
#include <vector>
#include <queue>
#include <iostream>
#include <thread>
#include <chrono>
#include <functional>
#include <atomic>

struct Node {
public:
	char data;
	std::vector<Node*> children;

	Node(char data_): data(data_) {}
};

std::atomic<int> atomicCounter{ 0 };

std::function<void()> makeThreadFunc(int sleep, Node* node) {
	return [sleep, node]() {	
		// we NEED the sleep for a proper breadth first traversal.
		std::this_thread::sleep_for(std::chrono::milliseconds(sleep * 10));
		
		printf("%c\n", node->data);	
		for (size_t ii = 0; ii < node->children.size(); ++ii) {
			std::thread(makeThreadFunc(atomicCounter++, node->children[ii])).detach();
		}	
	};
}

void sleepyBreadthFirstTraversal(Node* root)
{
	std::thread(makeThreadFunc(atomicCounter++, root)).detach();
	
	// wait out until all threads finished.
	// should be a thread::join, but Im lazy  ¯\_(ツ)_/¯
	std::this_thread::sleep_for(std::chrono::milliseconds(10000));
}

void traverseQueue(Node* root) {

	std::queue<Node*> queue;
	queue.push(root);

	while (!queue.empty()) {

		Node* node = queue.front(); queue.pop();

		printf("%c\n", node->data);

		for (size_t ii = 0; ii < node->children.size(); ++ii) {
			queue.push(node->children[ii]);
		}

	}
}

int main() {

	Node* a = new Node('a'); 
	
	Node* b = new Node('b'); 
	Node* c = new Node('c'); 
	Node* d = new Node('d'); 

	Node* e = new Node('e');
	Node* f = new Node('f');
	Node* g = new Node('g');
	Node* h = new Node('h');

	Node* i = new Node('i');
	Node* j = new Node('j');
	Node* k = new Node('k');
	Node* l = new Node('l');
	
	a->children.push_back(b);
	a->children.push_back(c);
	a->children.push_back(d);

	b->children.push_back(e);
	b->children.push_back(f);

	d->children.push_back(g);
	d->children.push_back(h);

	e->children.push_back(i);
	e->children.push_back(j);

	g->children.push_back(k);
	g->children.push_back(l);
	
	traverseQueue(a);

	printf("\n\n");

	sleepyBreadthFirstTraversal(a);
}