NFA determinization

nfa-determinization.cpp

#include <utility>
#include <set>
#include <vector>
#include <optional>
#include <queue>
#include <map>
#include <iostream>
#include <iterator>

int main() {
	std::vector<std::vector<std::pair<size_t, std::optional<int>>>> graph {
		{{ 1, std::nullopt }, { 8, std::nullopt }},
		{{ 2, std::nullopt }, { 4, std::nullopt }},
		{{ 3, 0 }},
		{{ 7, std::nullopt }},
		{{ 5, 1 }},
		{{ 6, 0 }},
		{{ 7, std::nullopt }},
		{{ 1, std::nullopt }, { 8, std::nullopt }},
		{}
	};
	std::set<int> chars;
	for (const auto &node: graph) {
		for (const auto &edge: node) {
			if (edge.second) {
				chars.emplace(edge.second.value());
			}
		}
	}
	auto get_eps_closure = [&](std::set<size_t> nodes) {
		std::queue<size_t> q;
		for (auto x: nodes) {
			q.push(x);
		}
		while (!q.empty()) {
			size_t x = q.front();
			q.pop();
			for (const auto &edge: graph[x]) {
				if (!edge.second && nodes.emplace(edge.first).second) {
					q.emplace(edge.first);
				}
			}
		}
		return nodes;
	};
	auto src = get_eps_closure({ 0 });
	std::vector<std::pair<std::set<size_t>, std::vector<std::pair<size_t, int>>>> new_graph {{ src, {}}};
	std::map<std::set<size_t>, size_t> new_nodes {{ src, 0 }};
	std::queue<size_t> q;
	q.push(0);
	while (!q.empty()) {
		size_t x = q.front();
		q.pop();
		for (auto y: chars) {
			std::set<size_t> nodes;
			for (const auto &node_id: new_graph[x].first) {
				for (const auto &edge: graph[node_id]) {
					if (edge.second == y) {
						nodes.insert(edge.first);
					}
				}
			}
			if (!nodes.empty()) {
				nodes = get_eps_closure(nodes);
				auto res = new_nodes.emplace(nodes, new_nodes.size());
				new_graph[x].second.emplace_back(res.first->second, y);
				if (res.second) {
					new_graph.emplace_back(nodes, std::vector<std::pair<size_t, int>> {});
					q.push(res.first->second);
				}
			}
		}
	}
	for (size_t i = 0; i < new_graph.size(); i++) {
		std::cout << "node " << i << ": ";
		std::copy(new_graph[i].first.begin(), new_graph[i].first.end(), std::ostream_iterator<size_t>(std::cout, " "));
		std::cout << '\n';
		for (const auto &edge: new_graph[i].second) {
			std::cout << i << " -" << edge.second << "-> " << edge.first << '\n';
		}
		std::cout << '\n';
	}
}