src/graph/GraphTemplate.hpp

• View this file on GitHub
• Last update: 2026-04-13 17:59:31+09:00
• Include: #include "src/graph/GraphTemplate.hpp"

Depends on

• src/assert/DebugAssert.hpp

Code

#include "../assert/DebugAssert.hpp"

struct Graph {
public:
	Graph() : Graph(0) {}
	Graph(int N) : n_(N), g(N) {}
	void add_directed_edge(int u, int v) {
		assertf(0 <= u && u < n_ && 0 <= v && v < n_,
			"Graph::add_directed_edge: invalid vertex index (u={}, v={}, n={})",
			u, v, n_);
		g[u].push_back(v);
	}	
	void add_undirected_edge(int u, int v) {
		assertf(0 <= u && u < n_ && 0 <= v && v < n_,
			"Graph::add_undirected_edge: invalid vertex index (u={}, v={}, n={})",
			u, v, n_);
		g[u].push_back(v);
		g[v].push_back(u);
	}
	vector<int>& operator[](int u) {
		return g[u];
	}
	const vector<int>& operator[](int u) const {
		return g[u];
	}
	int size() const {
		return n_;
	}
private:
	int n_;
	vector<vector<int>> g;
};

template<class T>
struct WeightedGraph {
public:
	WeightedGraph() : WeightedGraph(0) {}
	WeightedGraph(int N) : n_(N), g(N) {}
	void add_directed_edge(int u, int v, T w) {
		assertf(0 <= u && u < n_ && 0 <= v && v < n_,
			"WeightedGraph::add_directed_edge: invalid vertex index (u={}, v={}, n={})",
			u, v, n_);
		g[u].push_back(make_pair(v, w));
	}
	void add_undirected_edge(int u, int v, T w) {
		assertf(0 <= u && u < n_ && 0 <= v && v < n_,
			"WeightedGraph::add_undirected_edge: invalid vertex index (u={}, v={}, n={})",
			u, v, n_);
		g[u].push_back(make_pair(v, w));
		g[v].push_back(make_pair(u, w));
	}
	vector<pair<int, T>>& operator[](int u) {
		return g[u];
	}
	const vector<pair<int, T>>& operator[](int u) const {
		return g[u];
	}
	int size() const {
		return n_;
	}
private:
	int n_;
	vector<vector<pair<int, T>>> g;
};

using Tree = Graph;

#line 1 "src/assert/DebugAssert.hpp"
namespace debug_assert {

template<class T>
std::string to_string_any(const T& value) {
	std::ostringstream oss;
	oss << value;
	return oss.str();
}

inline void collect_args(std::vector<std::string>&) {}

template<class T, class... Rest>
void collect_args(std::vector<std::string>& out, T&& head, Rest&&... rest) {
	out.push_back(to_string_any(std::forward<T>(head)));
	collect_args(out, std::forward<Rest>(rest)...);
}

template<class... Args>
std::string format(std::string_view fmt, Args&&... args) {
	std::vector<std::string> vals;
	vals.reserve(sizeof...(Args));
	collect_args(vals, std::forward<Args>(args)...);

	std::string out;
	out.reserve(fmt.size() + vals.size() * 8);

	size_t arg_idx = 0;
	for (size_t i = 0; i < fmt.size(); ++i) {
		if (fmt[i] == '{' && i + 1 < fmt.size() && fmt[i + 1] == '{') {
			out.push_back('{');
			++i;
			continue;
		}
		if (fmt[i] == '}' && i + 1 < fmt.size() && fmt[i + 1] == '}') {
			out.push_back('}');
			++i;
			continue;
		}
		if (fmt[i] == '{' && i + 1 < fmt.size() && fmt[i + 1] == '}') {
			if (arg_idx >= vals.size()) {
				throw std::invalid_argument("format: missing argument for '{}' placeholder");
			}
			out += vals[arg_idx++];
			++i;
			continue;
		}
		out.push_back(fmt[i]);
	}

	if (arg_idx != vals.size()) {
		throw std::invalid_argument("format: too many arguments for format string");
	}

	return out;
}

[[noreturn]] inline void fail(const char* expr, const char* file, int line, const char* func, const std::string& msg) {
	std::ostringstream oss;
	oss << "Assertion failed: (" << expr << ")\n"
		<< "Location: " << file << ':' << line << " in " << func;
	if (!msg.empty()) {
		oss << "\nMessage: " << msg;
	}
	throw std::runtime_error(oss.str());
}

}  // namespace debug_assert

#define assertf(cond, fmt, ...) \
	do { \
		if (!(cond)) { \
			::debug_assert::fail(#cond, __FILE__, __LINE__, __func__, ::debug_assert::format((fmt), ##__VA_ARGS__)); \
		} \
	} while (0)

#define panic(fmt, ...) \
	do { \
		::debug_assert::fail("PANIC", __FILE__, __LINE__, __func__, ::debug_assert::format((fmt), ##__VA_ARGS__)); \
	} while (0)
#line 2 "src/graph/GraphTemplate.hpp"

struct Graph {
public:
	Graph() : Graph(0) {}
	Graph(int N) : n_(N), g(N) {}
	void add_directed_edge(int u, int v) {
		assertf(0 <= u && u < n_ && 0 <= v && v < n_,
			"Graph::add_directed_edge: invalid vertex index (u={}, v={}, n={})",
			u, v, n_);
		g[u].push_back(v);
	}	
	void add_undirected_edge(int u, int v) {
		assertf(0 <= u && u < n_ && 0 <= v && v < n_,
			"Graph::add_undirected_edge: invalid vertex index (u={}, v={}, n={})",
			u, v, n_);
		g[u].push_back(v);
		g[v].push_back(u);
	}
	vector<int>& operator[](int u) {
		return g[u];
	}
	const vector<int>& operator[](int u) const {
		return g[u];
	}
	int size() const {
		return n_;
	}
private:
	int n_;
	vector<vector<int>> g;
};

template<class T>
struct WeightedGraph {
public:
	WeightedGraph() : WeightedGraph(0) {}
	WeightedGraph(int N) : n_(N), g(N) {}
	void add_directed_edge(int u, int v, T w) {
		assertf(0 <= u && u < n_ && 0 <= v && v < n_,
			"WeightedGraph::add_directed_edge: invalid vertex index (u={}, v={}, n={})",
			u, v, n_);
		g[u].push_back(make_pair(v, w));
	}
	void add_undirected_edge(int u, int v, T w) {
		assertf(0 <= u && u < n_ && 0 <= v && v < n_,
			"WeightedGraph::add_undirected_edge: invalid vertex index (u={}, v={}, n={})",
			u, v, n_);
		g[u].push_back(make_pair(v, w));
		g[v].push_back(make_pair(u, w));
	}
	vector<pair<int, T>>& operator[](int u) {
		return g[u];
	}
	const vector<pair<int, T>>& operator[](int u) const {
		return g[u];
	}
	int size() const {
		return n_;
	}
private:
	int n_;
	vector<vector<pair<int, T>>> g;
};

using Tree = Graph;

Back to top page