プリム法で求めた全域木を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; }