[Qt] 图的可视化编程 - Graph Visualization

时间:2022-06-11 22:58:14


        写这篇博客的起因,是最近帮我同学的同学,写了一份课程设计,哈哈哈哈(不要举报哦,小宝贝)。

        先简单描述一下题目:无向图最短路径的动态规划求解,及界面演示。我采用的方法是Floyd算法,这个在我之前的博客中也有写到,这里也不再多说了。但是我一直想尝试一下利用编程的手段,将图结构展示出来,所以正好趁着这次机会,我就做了这样的一个程序,也顺便写一篇博文记录一下如何实现图的可视化编程Graph Visualizetion)。


演示程序下载链接:

      http://download.csdn.net/detail/mahabharata_/9905795

程序效果图:

[Qt] 图的可视化编程 - Graph Visualization

[Qt] 图的可视化编程 - Graph Visualization[Qt] 图的可视化编程 - Graph Visualization


最后来一个动画演示:

[Qt] 图的可视化编程 - Graph Visualization


正文

       这个程序大概是2个小时的作品,所以比较简陋,但是预期的效果姑且还是达到了。程序采用Qt开发,不过Qt的QPainter和MFC的HDC本质上是一样的,都是设定画笔、画刷啊,然后在对应的坐标绘制相应大小的图形,所以也可以参考一下。接下来的篇幅可能我会简单的说一下设计思想和部分代码。


一、关于图的可视化

       图的可视化(Graph Visualization)一直是一个比较麻烦的问题,当然实现上面截图的效果可能比较简单一些,但一些复杂图的生成、其他酷炫的效果可能要比预想的麻烦许多。

       我们对图结构的数据组织一般是下图的样式:

       [Qt] 图的可视化编程 - 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;
}