verifier.cpp

#include "graph.h"
#include <iostream>
#include <vector>
#include <string>
#include <cassert>
#include <stdexcept>
#include <stack>

Graph readGraph(std::istream& input) {
	std::string line;
	std::getline(input, line);
	const std::string digraph = "Digraph";
	const std::string undirected = "Undirected graph";
	const std::string gap = " with ";
	Graph::DirType dType = Graph::undirected;
	if (line[0]==digraph[0]) {
		line = line.substr(digraph.size()+gap.size());
		dType = Graph::directed;
	} else {
		line = line.substr(undirected.size()+gap.size());
	}
	const int nodeCount = std::stoi(line);
	Graph ret(nodeCount, dType);
	while (std::getline(input, line)) {
		if (line.size()==0 || line[0]=='T') {
			continue;
		}
		std::size_t minUnprocessed;
		Graph::NodeId start = std::stoi(line, &minUnprocessed);
		line = line.substr(minUnprocessed+3);
		Graph::NodeId end = std::stoi(line, &minUnprocessed);
		line = line.substr(minUnprocessed+std::string(" weight = ").length());
		double weight = std::stod(line);
		if (dType==Graph::directed || start>end) {
			ret.add_edge(start, end, weight);
		}
	}
	return ret;
}

bool verifyDFSTree(const Graph& graph, const Graph& tree, const Graph::NodeId start) {
	const Graph::NodeId n = tree.num_nodes();
	assert(graph.num_nodes()==n);
	assert(start<n && start>=0);
	std::stack<Graph::NodeId> stack;
	stack.push(start);
	struct NodeData {
		bool inPath = false;
		bool visited = false;
	};
	std::vector<NodeData> data(n);
	std::vector<std::vector<bool>> edgeValid(n, std::vector<bool>(n, false));
	while (!stack.empty()) {
		const Graph::NodeId curr = stack.top();
		NodeData& currData = data[curr];
		const auto& neighborsT = tree.get_node(curr).adjacent_nodes();
		const auto& neighborsG = graph.get_node(curr).adjacent_nodes();
		currData.visited = true;
		currData.inPath = true;
		Graph::NodeId next = n;
		for (const Graph::Neighbor& neighbor:neighborsT) {
			if (!data[neighbor.id()].visited) {
				next = neighbor.id();
				break;
			}
		}
		if (next==n) {
			for (const Graph::Neighbor& neighbor:neighborsG) {
				const Graph::NodeId end = neighbor.id();
				if (!edgeValid[end][curr] && data[end].inPath) {
					edgeValid[end][curr] = edgeValid[curr][end] = true;
				}
			}
			stack.pop();
			currData.inPath = false;
		} else {
			stack.push(next);
		}
	}
	for (Graph::NodeId i = 0;i<n;++i) {
		const Graph::Node& node = graph.get_node(i);
		for (const Graph::Neighbor& neighbor:node.adjacent_nodes()) {
			if (!edgeValid[i][neighbor.id()]) {
				return false;
			}
		}
	}
	return true;
}

int main(int argc, char** argv) {
	if (argc!=3) return 1;
	Graph g(argv[1], Graph::undirected);
	int startnode = std::stoi(argv[2]);
	std::string tmp;
	std::getline(std::cin, tmp);
	Graph tree = readGraph(std::cin);
	std::cout << "Valid: " << verifyDFSTree(g, tree, startnode) << std::endl;
}