写这篇博客的起因,是最近帮我同学的同学,写了一份课程设计,哈哈哈哈(不要举报哦,小宝贝)。
先简单描述一下题目:无向图最短路径的动态规划求解,及界面演示。我采用的方法是Floyd算法,这个在我之前的博客中也有写到,这里也不再多说了。但是我一直想尝试一下利用编程的手段,将图结构展示出来,所以正好趁着这次机会,我就做了这样的一个程序,也顺便写一篇博文记录一下如何实现图的可视化编程(Graph Visualizetion)。
演示程序下载链接:
http://download.csdn.net/detail/mahabharata_/9905795
程序效果图:
最后来一个动画演示:
正文
这个程序大概是2个小时的作品,所以比较简陋,但是预期的效果姑且还是达到了。程序采用Qt开发,不过Qt的QPainter和MFC的HDC本质上是一样的,都是设定画笔、画刷啊,然后在对应的坐标绘制相应大小的图形,所以也可以参考一下。接下来的篇幅可能我会简单的说一下设计思想和部分代码。
一、关于图的可视化
图的可视化(Graph Visualization)一直是一个比较麻烦的问题,当然实现上面截图的效果可能比较简单一些,但一些复杂图的生成、其他酷炫的效果可能要比预想的麻烦许多。
我们对图结构的数据组织一般是下图的样式:
那么问题来了。我们只知道结点和边的信息,但是不同的图的边的密度、边的分布是不一样的,我们如何才能加载这些数据,并分析数据使得生成的图结点均匀分布,并且每一条边都不交叉呢? 这个应该是个比较难的问题。
当然,我们可以在图的数据中,预先指定每个结点的坐标,但是这样又未免太过麻烦。网上也有相关的论文提出了这一问题的解决方案,也希望不幸点开此文的各位大佬给予些许指点,哈哈。 不过这篇博客所采用的解决方法可能比较简单,也仅仅抛出这样的问题,这个程序毕竟只是两个小时的作品,所以也不做深入探讨了。
二、图的绘制
这里仅仅贴出与图的可视化有关的代码,关于图的组织、图的最短路径搜寻可以去看一下我的另外一篇博客:点击打开链接。
关于上面抛出的问题:我采用了一种比较简单的解决方案:将所有结点在显示区域中围绕中心,绕着一个圆心均匀排列。这个时候需要先计算半径r(半径应为显示区域的1/3),然后利用顶点个数n均匀分割一个圆周。同时,还提供了鼠标的选取和拖动结点的操作,因此还要重写鼠标的press、move和release事件。具体代码如下:
1. 显示区域GraphView类的头文件:
#ifndef GRAPHVIEW_H
#define GRAPHVIEW_H
#include <QWidget>
#include <QPainter>
#include <cmath>
#include <QMouseEvent>
#include "floyd.h"
namespace Ui {
class GraphView;
}
class GraphView : public QWidget
{
Q_OBJECT
public:
explicit GraphView(QWidget *parent = 0);
~GraphView();
Floyd m_floyd; // 算法解析器
QList<QPoint> m_nodePos;
void loadGraphFromFile(const QString& fname);
void getShortestPath(QString start,QString end);
protected:
void paintEvent(QPaintEvent* event);
int m_currentID;
void mousePressEvent(QMouseEvent* event);
void mouseMoveEvent(QMouseEvent* event);
void mouseReleaseEvent(QMouseEvent* event);
private:
Ui::GraphView *ui;
};
#endif // GRAPHVIEW_H
2. 显示区域GraphView的源文件
#include "graphview.h"
#include "ui_graphview.h"
GraphView::GraphView(QWidget *parent) :
QWidget(parent),
ui(new Ui::GraphView)
{
ui->setupUi(this);
}
void GraphView::loadGraphFromFile(const QString &fname)
{
m_nodePos.clear();
m_floyd.readGraphFromFile(fname);
// 初始化一些数据
float delta = (360.0/(m_floyd.Num()))*3.14159/180.0;
int radius = height()/2-70;
QPoint center(width()/2, height()/2);
for(int i=0; i< m_floyd.Num(); i++)
{
QPoint c;
c.setX(center.x() + radius*sin(delta*i));
c.setY(center.y() + radius*cos(delta*i));
m_nodePos.push_back(c);
}
qDebug()<<"加载完成";
update();
}
void GraphView::getShortestPath(QString start, QString end)
{
m_floyd.getShortestPath(start,end);
update();
}
void GraphView::paintEvent(QPaintEvent *event)
{
QPainter painter(this);
if(m_floyd.Num() == 0)
return;
for(int i=0; i< m_floyd.Num(); i++)
{
QPoint c(m_nodePos[i]);
// draw node
painter.setBrush(QBrush(QColor(1, 101, 187,160)));
painter.setPen(QPen(QColor(255,255,255,0)));
painter.drawEllipse(c,20,20);
QPen pen(QColor(54, 52, 51));
pen.setWidth(4);
painter.setPen(pen);
painter.setFont(QFont("Consolas",19));
QPoint tc(c.x()-7,c.y()+7);
painter.drawText(tc, m_floyd.NodeName(i));
}
// draw edge
for(int i=0; i<m_floyd.Num(); i++)
{
for(int k=0; k<m_floyd.Num()&& k<i; k++)
{
int length = m_floyd.getEdge(i,k);
if(length== MAXINT)
continue;
QPoint s(m_nodePos[i]);
QPoint e(m_nodePos[k]);
QPoint tpos;
tpos.setX((s.x()+e.x())/2);
tpos.setY((s.y()+e.y())/2);
QPen pen(QColor(124, 122, 121,200));
pen.setWidth(4);
painter.setPen(pen);
painter.drawLine(s,e);
QPen pen1(QColor(28, 114, 14));
pen1.setWidth(4);
painter.setPen(pen1);
painter.setFont(QFont("Consolas",19));
painter.drawText(tpos,QString::number(m_floyd.getEdge(i,k)));
}
}
// draw path
for(int i=0; i<m_floyd.shortestPath.size(); i++)
{
QPoint c(m_nodePos[m_floyd.shortestPath[i]]);
QPoint tc(c.x()-7,c.y()+7);
if(i==0 || i== m_floyd.shortestPath.size()-1)
painter.setBrush(QBrush(QColor(120, 195, 41)));
else
painter.setBrush(QBrush(QColor(249, 109, 59)));
painter.drawEllipse(c,20,20);
painter.drawText(tc, m_floyd.NodeName(m_floyd.shortestPath[i]));
}
}
void GraphView::mousePressEvent(QMouseEvent *event)
{
QPoint pos = event->pos();
m_currentID = -1;
for(int i=0; i<m_nodePos.size(); i++)
{
int dx = pos.x() - m_nodePos[i].x();
int dy = pos.y() - m_nodePos[i].y();
int dist = sqrt(dx*dx+dy*dy);
if(dist < 20)
{
m_currentID = i;
}
}
}
void GraphView::mouseMoveEvent(QMouseEvent *event)
{
if(m_currentID == -1)
return;
m_nodePos[m_currentID] = event->pos();
update();
}
void GraphView::mouseReleaseEvent(QMouseEvent *event)
{
m_currentID = -1;
}
GraphView::~GraphView()
{
delete ui;
}