All possible topological orderings

topological_orderings.cpp

#include<iostream>
#include<vector>
#include<set> 
// we assume that for the same elements, the iteration order is always the same
// which is not the case for unordered_map



void _topological_ordering(std::set<int>& s,
	std::vector<int>& v,
	std::vector<std::vector<int>>& orderings,
	int n,
	std::vector<std::vector<int>>& adjacency_matrix
) {
	if (s.empty()) {
		orderings.push_back(v);
		return;
	}

	int cnt_s = s.size();

	for (int i = 0; i < cnt_s; i++) {
		auto it = s.begin();
		auto node = *std::next(it, i); 
		s.erase(node);
		v.push_back(node);

		auto edges_buffer = std::vector<int>(n); // from node to j
		auto affected_nodes = std::vector<int>{};
		for (int j = 0; j < n; j++) {
			if (adjacency_matrix[node][j] == 1) {
				affected_nodes.push_back(j);
			}
			edges_buffer[j] = adjacency_matrix[node][j];
			adjacency_matrix[node][j] = -1;
		}

		auto new_no_incomming_edges_nodes = std::set<int>{};

		for (int j : affected_nodes) {
			bool flag = true;
			for (int k = 0; k < n; k++) {
				if (adjacency_matrix[k][j] > 0) {
					flag = false;
					break;
				}
			}
			if (flag) {
				new_no_incomming_edges_nodes.insert(j);
			}
		}

		for (auto new_node : new_no_incomming_edges_nodes) {
			s.insert(new_node);
		}



		_topological_ordering(s, v, orderings, n, adjacency_matrix);




		s.insert(node);
		v.pop_back();

		for (int j = 0; j < n; j++) {
			adjacency_matrix[node][j] = edges_buffer[j];
		}

		for (auto new_node : new_no_incomming_edges_nodes) {
			s.erase(new_node);
		}
	}

}




// there is space for optimization. 
std::vector<std::vector<int>> topological_orderings(std::vector<std::vector<int>> adjacency_matrix) {
	const int n = adjacency_matrix.size();


	auto s = std::set<int>{}; // set of all nodes with no incoming edge
	for (int i = 0; i < n; i++) {
		bool flag = true;
		for (int j = 0; j < n; j++) {
			if (adjacency_matrix[j][i] > 0) {
				flag = false;
				break;
			}
		}
		if (flag) {
			s.insert(i);
		}
	}


	auto v = std::vector<int>{};
	auto ans = std::vector<std::vector<int>>{};

	_topological_ordering(s, v, ans, n, adjacency_matrix);


	return ans;
}


int main() {
	int n = 7;
	auto adjacancy_matrix = std::vector<std::vector<int>>(n, std::vector<int>(n, -1));
	adjacancy_matrix[0][1] = 1;
	adjacancy_matrix[1][2] = 1;
	adjacancy_matrix[1][3] = 1;
	adjacancy_matrix[1][4] = 1;
	adjacancy_matrix[4][5] = 1;
	adjacancy_matrix[2][4] = 1;
	adjacancy_matrix[3][4] = 1;
	adjacancy_matrix[6][3] = 1;

	auto orderings = topological_orderings(std::move(adjacancy_matrix));
	int cnt = orderings.size();
	std::cout << "Total number of possible topological orderings: " << cnt << std::endl;
	for (auto&& ordering : orderings) {
		for (auto node : ordering) {
			std::cout << static_cast<char> (node + 'A') << " ";
		}
		std::cout << std::endl;
	}
}