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

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

        先简单描述一下题目：无向图最短路径的动态规划求解，及界面演示。我采用的方法是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;
}