プリム法で求めた全域木をOpenGLで表示してみる

前のエントリで最小全域木問題をプリム法で解いてみたものの、出力が数字の羅列だと達成感が薄いのでOpenGLで表示させる。

さっきPythonで解いた全域木

頂点数を増やしてみた

頂点をランダムに打つようにして沢山打ってみた

おおお。

// 無向な完全グラフの最小全域木問題の可視化
#include<cmath>
#include<cstdlib>
#include<ctime>
#include<vector>
#include<set>
#include<GL/glut.h>
using namespace std;

//const double in[][2] = {{18, 25}, {36, 50}, {36, 27}, {46, 37}, {73, 37}, {65, 12}, {-1, -1}};
//const double in[][2] = {{18, 25}, {36, 50}, {36, 27}, {46, 37}, {73, 37}, {65, 12}, {34, 40}, {10, 32}, {50, 14}, {75, 30}, {80, 35}, {52, 31}, {53, 53}, {64, 45}, {-1, -1}};

class Point {
public:
	Point(double s, double t): x(s), y(t){};
	double x, y;
};
class Edge {
public:
	Edge(Point s, Point d): src(s), dst(d){};
	Point src, dst;
};

vector<Edge> edges;
vector<Point> points;

double dist(Point u, Point v)
{
	double a = (u.x - v.x) * (u.x - v.x);
	double b = (u.y - v.y) * (u.y - v.y);
	return sqrt(a+b);
}

vector<Edge> MST(const vector<Point> &ps)
{
	vector<vector<double> > m(ps.size(), vector<double>(ps.size()));
	// 距離行列の作成
	for(int i=0; i<ps.size(); i++)
		for(int j=0; j<ps.size(); j++)
			m[i][j] = dist(ps[i], ps[j]);

	set<int> X; X.insert(0);
	set<int> Y; for(int i=1; i<ps.size(); i++) Y.insert(i);

	set<int>::iterator xi;
	set<int>::iterator yi;
	int src, dst;
	while(Y.size() != 0){
		double mcost = 1e8;
		for(xi = X.begin(); xi != X.end(); xi++){
			for(yi = Y.begin(); yi != Y.end(); yi++){
				double c = m[*xi][*yi];
				if(mcost > c){
					mcost = c;
					src = *xi;
					dst = *yi;
				}
			}
		}
		printf("minimum cost path: %d -> %d\n", src, dst);
		X.insert(dst);
		Y.erase(dst);
		edges.push_back(Edge(ps[src], ps[dst]));
	}
	return edges;
}

double scale=2e-2;
double slide=-.8;
void vertex(double x, double y)
{
	glVertex2d(x*scale+slide, y*scale+slide);
}

void display()
{
	glClearColor(0, 0, 0, 0);
	glClear(GL_COLOR_BUFFER_BIT);
	glPointSize(5);

	// 軸の描画
	glColor3f(.7, .7, .7);
	glBegin(GL_LINES);
	vertex(-1000, 0); vertex(1000, 0);
	vertex(0, -1000); vertex(0, 1000);
	glEnd();

	glColor3f(1, 1, 1);
	glBegin(GL_LINES);
	for(int i=0; i<edges.size(); i++){
		vertex(edges[i].src.x, edges[i].src.y);
		vertex(edges[i].dst.x, edges[i].dst.y);
	}
	glEnd();

	glColor3f(1, 0, 0);
	glBegin(GL_POINTS);
	for(int i=0; i<points.size(); i++)
		vertex(points[i].x, points[i].y);
	glEnd();
}

void init()
{
/*
	for(int i=0; in[i][0] != -1 and in[i][1] != -1; i++){
		Point x(in[i][0], in[i][1]);
		points.push_back( x );
	}
*/
	// ランダムに点を打つ
        srand(time(NULL));
	for(int i=0; i<100; i++){
		Point x(rand()%80, rand()%80);
		points.push_back( x );
	}
	edges = MST(points);
}

int main(int argc, char **argv)
{
	glutInit(&argc, argv);
	glutCreateWindow("Minimum Spanning Tree");
	glutDisplayFunc(display);

	init();

	glutMainLoop();
	return 0;
}