グラフ関係のコードいくつか

ようやく大学が夏季休業に入ったので、学校で使った離散数学の本読んでグラフ理論とオートマトンの勉強をしている。
グラフ理論の部分で出てきたアルゴリズムとかでコード書いたのでいくつか。


Bellman-Ford algorithm
まずはBellman-Ford法。これは本には出てこなかったけど、Dijkstra法は書いたことあるのにBellman-Ford法は書いた事ないなぁと思った程度のアルゴリズム力なので、とりあえず書いてみた。

	#include <iostream>
	#include <stdint.h>
	#include <stdlib.h>
	using namespace std;
	const size_t SIZE = 100;
	int64_t V[SIZE], E[SIZE][SIZE];
	int main() {
	for(int i = 0; i < SIZE; i++)
	for(int j = 0; j < SIZE; j++)
	E[i][j] = INT64_MAX;
	for(int i = 0; i < SIZE; i++)
	V[i] = INT64_MAX;
	// |V| = N, |E| = M
	int N, M;
	cin >> N >> M;
	int start, end;
	cin >> start >> end;
	// input format: endpoint_a endpoint_b cost
	for(int i = 0; i < M; i++) {
	int a, b, cost;
	cin >> a >> b >> cost;
	E[a][b] = E[b][a] = cost;
	}
	V[start] = 0;
	int cnt = 0;
	bool updated = true;
	while(updated && cnt++ <= N) {
	updated = false;
	for(int i = 0; i < N; i++) {
	if(V[i] == INT64_MAX)
	continue;
	for(int j = 0; j < N; j++) {
	if(i == j || E[i][j] == INT64_MAX)
	continue;
	if(V[j] > E[i][j] + V[i]) {
	V[j] = E[i][j] + V[i];
	updated = true;
	}
	}
	}
	if(!updated)
	break;
	}
	if(updated)
	cout << -1 << '\n'; // the graph has negative-weight cycle
	else
	cout << V[end] << '\n';
	}

view raw bellman-ford.cc hosted with ❤ by GitHub

一応無向グラフ想定して書いたけど、ちょっと変えれば有向グラフにも適用出来る……はず。一応辺は行列で表現してるので。

Kruskal's algorithm
次にKruskal法。最小全域木を求めるアルゴリズムで、O(ElogE)? O(ElogV)? なアルゴリズム。

	#include <iostream>
	#include <vector>
	#include <algorithm>
	#include <cstdlib>
	#include <cstdint>
	struct UnionFind {
	private:
	std::vector<int64_t> data;
	public:
	UnionFind(size_t size);
	bool unionSet(size_t x, size_t y);
	bool findSet(size_t x, size_t y);
	size_t root(size_t x);
	int64_t size(size_t x);
	};
	UnionFind::UnionFind(size_t size) : data(size, -1) {}
	bool UnionFind::unionSet(size_t x, size_t y) {
	x = root(x);
	y = root(y);
	if(x != y) {
	if(size(x) > size(y))
	std::swap(x, y);
	data[x] += data[y];
	data[y] = x;
	}
	return x != y;
	}
	bool UnionFind::findSet(size_t x, size_t y) {
	return root(x) == root(y);
	}
	size_t UnionFind::root(size_t x) {
	if(data[x] < 0)
	return x;
	else
	return root(data[x]);
	}
	int64_t UnionFind::size(size_t x) {
	return -data[root(x)];
	}
	struct Edge {
	size_t start, end;
	int64_t cost;
	bool operator==(const Edge &e) {
	return cost == e.cost;
	}
	bool operator<(const Edge &e) const {
	return cost < e.cost;
	}
	};
	auto main(void) -> int {
	using namespace std;
	int32_t N, M; // N = |V|, M = |E|
	cin >> N >> M;
	auto edges = new vector<Edge>(M);
	for(auto it = edges->begin(), eit = edges->end(); it != eit; ++it) {
	// Edge format: start_point end_point cost
	size_t st, ed;
	int64_t c;
	cin >> st >> ed >> c;
	Edge edge{st, ed, c};
	*it = edge;
	}
	sort(edges->begin(), edges->end());
	auto minTree = new vector<Edge>;
	auto uft = new UnionFind(N);
	for(auto it = edges->begin(), eit = edges->end(); it != eit; ++it) {
	auto edge = *it;
	if(!uft->findSet(edge.start, edge.end)) {
	minTree->push_back(edge);
	uft->unionSet(edge.start, edge.end);
	}
	}
	for(auto e : *minTree) {
	cout << e.start << ' ' << e.end << ' ' << e.cost << '\n';
	}
	}

view raw kruskal.cc hosted with ❤ by GitHub

同じ木に属しているかどうかはUnion-Find木で書けるので、本の通りにいけば、まずは辺をコストでソートして、小さい辺から、その辺が連結でない2つの木を連結するならば、最小全域木の辺として加えていくというアルゴリズム。

Reverse Polish Notation
アルゴリズムではないけども、逆ポーランド記法をプログラミング3年目?にしてようやく実装したので。

	#include <cstdint>
	#include <cstdlib>
	#include <cstring>
	#include <iostream>
	#include <memory>
	#include <sstream>
	#include <string>
	#include <stack>
	#include <vector>
	#include <boost/algorithm/string/split.hpp>
	#include <boost/algorithm/string/classification.hpp>
	struct Node {
	virtual int32_t value(){return 0;}
	virtual void print(){}
	virtual ~Node(){}
	};
	struct OpNode : Node {
	char op;
	Node *left, *right;
	OpNode(char o, Node* l, Node* r) :
	op(o),
	left(l),
	right(r) {}
	virtual ~OpNode() {
	delete left;
	delete right;
	}
	virtual int32_t value() {
	auto l = left->value();
	auto r = right->value();
	int32_t ret;
	switch(op) {
	case '+':
	ret = l + r;
	break;
	case '-':
	ret = l - r;
	break;
	case '*':
	ret = l * r;
	break;
	case '/':
	ret = l / r;
	break;
	default:
	ret = 0;
	break;
	}
	return ret;
	}
	virtual void print() {
	left->print();
	right->print();
	std::cout << op << ' ';
	}
	};
	struct ValNode : Node {
	int32_t val;
	ValNode(int32_t v) : val(v) {}
	virtual ~ValNode(){}
	virtual int32_t value() {
	return val;
	}
	virtual void print() {
	std::cout << val << ' ';
	}
	};
	bool isOperator(char *e) {
	using std::strcmp;
	return strcmp(e, "+") == 0 || strcmp(e, "-") == 0 || strcmp(e, "*") == 0 || strcmp(e, "/") == 0;
	}
	bool isOperator(std::string e) {
	return e == "+" || e == "-" || e == "*" || e == "/";
	}
	Node *makeTree(std::vector<std::string> vc) {
	std::unique_ptr<std::stack<Node*>> st(new std::stack<Node*>);
	for(auto e : vc) {
	if(isOperator(e)) {
	auto right = st->top();
	st->pop();
	auto left = st->top();
	st->pop();
	auto node = new OpNode(e[0], left, right);
	st->push(node);
	} else {
	std::stringstream ss;
	ss << e;
	int32_t v;
	ss >> v;
	auto node = new ValNode(v);
	st->push(node);
	}
	}
	return st->top();
	}
	Node *makeTree(int n, char **arr) {
	std::unique_ptr<std::stack<Node*>> st(new std::stack<Node*>);
	for(int i = 0; i < n; i++) {
	auto e = arr[i];
	if(isOperator(e)) {
	auto right = st->top();
	st->pop();
	auto left = st->top();
	st->pop();
	auto node = new OpNode(e[0], left, right);
	st->push(node);
	} else {
	std::stringstream ss;
	ss << e;
	int32_t v;
	ss >> v;
	auto node = new ValNode(v);
	st->push(node);
	}
	}
	return st->top();
	}
	auto main(int argc, char **argv) -> int {
	Node *tree;
	if(argc > 1) {
	tree = makeTree(--argc, ++argv);
	} else {
	std::unique_ptr<std::vector<std::string>> vc(new std::vector<std::string>);
	std::string str;
	getline(std::cin, str);
	boost::algorithm::split(*vc, str, boost::is_any_of(" "));
	if(vc->size() == 0 || vc->at(0).length() < 1) {
	std::cerr << "Input Error" << std::endl;
	exit(EXIT_FAILURE);
	}
	tree = makeTree(*vc);
	}
	tree->print();
	std::cout << std::endl;
	std::cout << tree->value() << std::endl;
	exit(EXIT_SUCCESS);
	}

view raw reverse_polish.cc hosted with ❤ by GitHub

ある数式を表す木構造を考えるときに、木の各頂点に番号を付けることを考えると、プリオーダーとポストオーダーという2つの方法が考えられる。
プリオーダーって言うのは、自分自身、左の子ノード、右の子ノードの順に再帰的に番号を付けていく方法で、このやり方だと式木はポーランド記法になる……はず。
ポストオーダーは左の子ノード、右の子ノード、自分自身の順に番号をつけていく方法で、このやり方だと式木は逆ポーランド記法になる。

実装の方法としては、入力をスペース区切りの数字、演算子の列だとして、数字が来たらスタックにそのままプッシュ、演算子が来たら右、左の順にスタックから取り出した値を子ノードとして割り当てて、演算子を根とした木構造にしてスタックにプッシュ。最後にスタックに残った木を取り出すと、これが式木になってる。後はまぁコードの通りに各頂点ごとの値を計算するだけ。

とりあえずグラフは(まだフローとかあるけど)ひと通り分かった……と思うので、次はオートマトンのあたりで何かしらコードを書きたい。