topological_sort.cpp

#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <memory>
#include <unordered_map>
#include <stdexcept>
#include <algorithm>
#include <cmath>
#include <random>
#include <deque>
#include <cassert>

struct DagNode{
	std::string name;
	std::vector<DagNode *> dependencies;
	int aux = 0;

	DagNode(const std::string &name): name(name){}
	void check_node_for_cycles(){
		if (this->aux)
			throw std::runtime_error("Cycle detected.");
		this->aux = 1;
		for (auto &d : this->dependencies)
			d->check_node_for_cycles();
		this->aux = 0;
	}
	int get_order(){
		int ret = -1;
		for (auto &node : this->dependencies){
			auto order = node->get_order();
			if (order < 0)
				return this->aux = -1;
			ret = std::max(ret, order);
		}
		return this->aux = ret + 1;
	}
	bool depends_on(DagNode *other) const{
		if (other == this)
			return true;
		for (auto &dependency : this->dependencies)
			if (dependency->depends_on(other))
				return true;
		return false;
	}
};

std::vector<std::string> split_line(const std::string &line){
	std::stringstream stream(line);
	std::vector<std::string> ret;
	while (true){
		std::string word;
		if (!(stream >> word))
			break;
		ret.emplace_back(std::move(word));
	}
	return ret;
}

bool sort_node(DagNode *a, DagNode *b){
	return a->name < b->name;
}

struct Dag{
	std::vector<std::unique_ptr<DagNode>> nodes;

	Dag(){
		std::unordered_map<std::string, std::vector<std::string>> map;
		while (true){
			std::string line;
			std::getline(std::cin, line);
			if (!line.size())
				break;
			auto words = split_line(line);
			if (!words.size())
				break;
			std::string first = std::move(words.front());
			words.erase(words.begin());
			map[std::move(first)] = std::move(words);
		}
		//Check input.
		for (auto &kv : map){
			for (auto &dependency : kv.second){
				auto it = map.find(dependency);
				if (it == map.end()){
					std::stringstream stream;
					stream << "Invalid DAG. Node named \"" << kv.first << "\" references an unknown node named \"" << dependency << "\".";
					throw std::runtime_error(stream.str());
				}
			}
		}
		//Construct nodes.
		std::unordered_map<std::string, std::unique_ptr<DagNode>> nodes;
		for (auto &kv : map)
			nodes[kv.first] = std::make_unique<DagNode>(kv.first);
		//Link nodes.
		for (auto &kv : map){
			for (auto &dependency : kv.second){
				auto node1 = nodes.find(kv.first);
				auto node2 = nodes.find(dependency);
				node1->second->dependencies.push_back(node2->second.get());
			}
		}
		this->nodes.reserve(nodes.size());
		for (auto &kv : nodes)
			this->nodes.emplace_back(std::move(kv.second));
		this->check_for_cycles();
	}
	Dag(const Dag &) = delete;
	void operator=(const Dag &) = delete;
	Dag(Dag &&other){
		this->nodes = std::move(other.nodes);
	}
	const Dag &operator=(Dag &&other){
		this->nodes = std::move(other.nodes);
		return *this;
	}
	void check_for_cycles(){
		for (auto &node : this->nodes)
			node->aux = 0;
		for (auto &node : this->nodes)
			node->check_node_for_cycles();
	}
	std::vector<std::vector<DagNode *>> topological_sort(){
		for (auto &node : this->nodes)
			node->aux = -1;
		bool all_set;
		do{
			all_set = true;
			for (auto &node : this->nodes)
				if (node->get_order() < 0)
					all_set = false;
		}while (!all_set);
		decltype(this->topological_sort()) ret;
		for (auto &node : this->nodes){
			auto order = node->get_order();
			if (ret.size() <= order)
				ret.resize(order + 1);
			ret[order].push_back(node.get());
		}
		for (auto &list : ret)
			std::sort(list.begin(), list.end(), sort_node);
		return ret;
	}
};

typedef decltype(Dag().topological_sort()) sorted_t;

std::vector<std::vector<DagNode *>> generate_3_random_orderings(const sorted_t &sorted){
	decltype(generate_3_random_orderings(sorted)) ret;
	std::vector<DagNode *> base;
	for (auto &a : sorted)
		for (auto &b : a)
			base.push_back(b);
	std::random_device dev;
	std::mt19937 rand(dev());

	for (int i = 0; i < 3; i++){
		auto candidate = base;
		std::shuffle(candidate.begin(), candidate.end(), rand);
		auto n = candidate.size();
		bool valid_order;
		do{
			for (size_t i = 0; i < n - 1; i++){
				for (size_t j = i + 1; j < n; j++){
					if (candidate[i]->depends_on(candidate[j]))
						std::swap(candidate[i], candidate[j]);
					else if (candidate[j]->depends_on(candidate[i]))
						continue;
					else if (rand() % 2)
						std::swap(candidate[i], candidate[j]);
				}
			}
			valid_order = true;
			for (size_t i = 0; i < n - 1 && valid_order; i++){
				for (size_t j = i + 1; j < n; j++){
					if (candidate[i]->depends_on(candidate[j])){
						valid_order = false;
						break;
					}
				}
			}
		}while (!valid_order);
		ret.emplace_back(std::move(candidate));
	}
	return ret;
}

int main(){
	try{
		Dag dag;
		auto sorted = dag.topological_sort();
		int order = 0;
		for (auto &level : sorted){
			std::cout << "level " << order << ":";
			for (auto &node : level)
				std::cout << " " << node->name;
			std::cout << std::endl;
			order++;
		}

		std::cout << "Warning: The following orderings are not guaranteeed to be different, nor is the program guaranteed to terminate!\n";
		auto orderings = generate_3_random_orderings(sorted);
		int ordering_no = 0;
		for (auto &ordering : orderings){
			std::cout << "ordering " << ++ordering_no << ":";
			for (auto &node : ordering)
				std::cout << " " << node->name;
			std::cout << std::endl;
		}
	}catch (std::exception &e){
		std::cerr << e.what() << std::endl;
	}
	return 0;
}