斯坦福CS106L-C++作业1——graph drawing problem

参考资料：
斯坦福CS106L

此次作业主要是stream和vector的运用。

问题描述：

一个图通常可以画成很多形式，有些形式比较任意“看懂”，尝试将一幅图画得比较通俗。
下图很难看出什么结构

下图跟上图是一样的，但结构明显好多了。

算法：

没有一种通用可以解决所有画图问题的算法，每种算法都有自己画得好的图，也有画得不好的图，这里采用的是force-directed layout algorithm。
画图的算法可以从减少交叉和增加对称性入手，本作业的算法用
另外两条准则：
1、相连的节点有吸引力
2、没有相连的节点有排斥力
程序采用迭代的方式，首先初始安排节点，然后更具以上两条原则计算各自节点上的”力“，力的计算可以有多种方式，根据”力“新节点的位置。
初始安排节点：可以均匀摆放在一个圆上。

何时停止迭代：让用户选择迭代多久
计算力：Fruchterman-Reingold algorithm，排斥力跟距离成反比（注意系数一般是10^{-3），排斥力在任意两个节点之间，吸引力跟距离的平方成正比（也有一个一般是10}-3的系数），吸引力在每条边的两端点之间。
移动：根据净力的大小移动每个点。

作业任务

1.用户输入要画图的图描述文件
2.输入要运行的时间t
3.初始化每个点初试位置
4.在时间t内计算力，然后移动各节点

代表图的数据结构

Node：包含每个节点横纵坐标x，y的结构体。

/**
 * Type: Node
 * -----------------------------------------------------------------------
 * A type representing a node in a graph.  Each node stores only the x and
 * y coordinates of where the node is in the plane; all other information
 * about the node is stored implicitly by its position in the SimpleGraph
 * list of nodes.
 */
struct Node {
  double x, y;
};

Edge：记录起点终点的序号

/**
 * Type: Edge
 * -----------------------------------------------------------------------
 * A type representing an edge in the graph.  It stores its endpoints by
 * the indices in which they occur in the SimpleGraph's list of Nodes.
 */
struct Edge {
  std::size_t start, end;
};

SimpleGraph：点和边

/**
 * Type: SimpleGraph
 * -----------------------------------------------------------------------
 * A type representing a simple graph of nodes and edges.
 */

struct SimpleGraph {
    std::vector<Node> nodes;
    std::vector<Edge> edges;
};

图描述文件：下面代表8个定点，接着每行两个数字表示对应序号的点之间有一条边。

任务分解
1、从磁盘读取图文件

#include <string>
#include <sstream>
#include <fstream>

SimpleGraph* readGraphFromDisk() {
    std::string fileName;
    std::ifstream is;

    while (true) {
        std::cout << "input file name:" << std::endl;
        //记得#include <sstream>
        std::getline(std::cin, fileName);

        is.open(fileName);
        if (!is) {
            std::cout << "file doesn't exist!" << std::endl;
        } else {
            break;
        }
    }

    std::size_t n_nodes;
    Edge edge;
    SimpleGraph *p_G =  new SimpleGraph();

    // 读取顶点数
    is >> n_nodes;
    p_G->nodes.resize(n_nodes);

    // 依次读取边
    while (is >> edge.start >> edge.end) {
        p_G->edges.push_back(edge);
    }
    return p_G;
}

2、初始化点的位置

#include <cmath>
const double PI = 3.14159265358979323;
void InitNode(SimpleGraph& G){
    std::size_t n_nodes = G.nodes.size();

    for(std::size_t i=0;i<n_nodes;i++){
        G.nodes.at(i).x = cos(2*PI*i/n_nodes);
        G.nodes.at(i).y = sin(2*PI*i/n_nodes);
    }
}

3、时间的计算：

#include <ctime>
    time_t startTime = time(NULL);
    double elapseTime = 0;
    do{
        UpdateGraph(*p_G);
        DrawGraph(*p_G);
        elapseTime = difftime(time(NULL),startTime);
    }while(elapseTime >= excuteTimeInS);

4、算法具体实现：

#define K_REPL 0.001
#define K_ATTR 0.001
void UpdateGraph(SimpleGraph& G){
    int N_nodes = G.nodes.size();
    std::vector<Node> nodes_forces(N_nodes,{0.0,0.0});

    int start,end;
    double force,angle;

    //排斥力
    for(int i=0;i<N_nodes;i++)
        for(int j=i+1;j<N_nodes;j++){
            start = i;
            end = j;

            force = K_REPL/sqrt(CalcSquareDistance(G,start,end));
            angle = atan2(G.nodes[end].y - G.nodes[start].y,G.nodes[end].x - G.nodes[start].x);
            nodes_forces[start].x -= force*cos(angle);
            nodes_forces[start].y -= force*sin(angle);
            nodes_forces[end].x += force*cos(angle);
            nodes_forces[end].y += force*sin(angle);
        }


    //吸引力
    for(Edge edge:G.edges)
    {
        start = edge.start;
        end = edge.end;

        force = CalcSquareDistance(G,start,end) * K_ATTR;
        angle = atan2(G.nodes[end].y - G.nodes[start].y,G.nodes[end].x - G.nodes[start].x);
        nodes_forces[start].x += force*cos(angle);
        nodes_forces[start].y += force*sin(angle);
        nodes_forces[end].x -= force*cos(angle);
        nodes_forces[end].y -= force*sin(angle);
    }

    //根据力进行调整位置
    for(int i=0;i<N_nodes;i++){
        G.nodes[i].x += nodes_forces[i].x;
        G.nodes[i].y += nodes_forces[i].y;
    }
}

main函数

// Main method
int main() {
    SimpleGraph *p_G;

    Welcome();

    p_G = readGraphFromDisk("127binary-tree");
    InitNode(*p_G);
    DrawGraph(*p_G);

    double excuteTimeInS;
    std::cout << "input excute time in seconds:" << std::endl;
    std::cin >> excuteTimeInS;

    time_t startTime = time(NULL);
    while(difftime(time(NULL),startTime) <= excuteTimeInS){
        UpdateGraph(*p_G);
    }
    DrawGraph(*p_G);

    std::cout << "finish!" << std::endl;

    delete p_G;
    return 0;
}

实验结果：
127binary-tree：

初试化

3s后

10s后

斯坦福CS106L-C++作业1——graph drawing problem

问题描述：

算法：

作业任务

代表图的数据结构