一个简陋的个人小项目,也是个人第一个真正意义上的独立项目——Graph

2019-04-18

由来

我最早接触到图这个概念是在大二的离散数学当中图论相关的内容,当时是以著名的哥尼斯堡七桥问题引出图论的概念,现在依然记忆犹新(不过只是记得这个名字,具体的解题思路我重新温习了一下才想起来),当时也提出了求最短路径的迪杰斯特拉算法,不过没有用编程语言具体实现。

之后在数据结构的学习中,又出现了图的相关知识,提出了在计算机中存储图的几种方式,我们学校的课程中学习的是邻接表和邻接矩阵,同时也用编程语言实现了具体的算法。

离散数学中的图用几何图形表示,清晰明了,但实现算法时步骤不清晰;邻接矩阵和邻接表适合实现算法,但可视化效果不好,只能用字符串输出。那么能不能写一个小项目,既能实现算法,又能用可视化较好的形式显示出来呢?之前其他人可能也写过同样功能的项目,但这个想法是我自己独立提出的,而且我有一套自己独特的实现方法,至于实现方法,请看下文详细讲解。

DOT语言

DOT语言是贝尔实验室发明的绘图语言,它可以非常方便地绘制出数学概念中的图,包括有向图和无向图,可以在顶点内添加信息,也可以在边上添加信息,还可以设置不同的顶点形状和边的形状等等功能,它的文档在此:https://graphviz.gitlab.io/_pages/doc/info/lang.html

下面我给出一个DOT语言的使用示例,代码和绘图效果如下:

graph g{
    a--b--c,d--a
}

dot示例.PNG

我是在使用Markdown Preview Enhanced插件的过程中了解到了DOT语言。在Graph项目中,DOT语言是非常重要的一环,它就可以实现将文本到可视化图形的转换

DOT语言最早是在桌面端的一个应用程序叫做Graphviz中实现的,不过现在已经有人在浏览器端用一个名为Viz.js的工具来实现了,也正符合了那句话:“能用 js 实现的功能,最终一定会用 js 实现”。Viz.js也是这个项目主要的依赖文件

Graph项目目前实现的功能

  • 输入邻接矩阵生成无向图
  • 输入邻接矩阵生成有向图
  • 输入邻接表生成无向图
  • 输入邻接表生成有向图
  • 输入邻接矩阵、开始点和结束点的信息,计算最短路径并生成可视化结果
  • 输入邻接表、开始点和结束点的信息,计算最短路径并生成可视化结果

Graph项目的简要工作流程

工作流程

Graph项目的Github地址

https://github.com/aopstudio/Graph

生成的HTML文件的位置

  • 完整的有向图或无向图:D:/graph.html
  • 要求的最短路径示意图:D:/shortestPath.html

主函数代码分析和使用效果

目前我还没有写输入模块,只能在源代码中给定数据来生成图。在源代码中给出五个顶点,

String[] nodes= {"北京","上海","台北","泰州","宁波"};

初始化邻接矩阵的边矩阵,再给定边的权值

int[][] m=new int[nodes.length][nodes.length];
m[0][1]=1213;
m[1][4]=200;
m[1][2]=900;
m[4][2]=600;
m[0][3]=1200;
m[3][4]=400;

将存储边信息的m和存储顶点信息的node包装成我自定义的数据结构MatrixGraph

MatrixGraph mg=new MatrixGraph(m,nodes);

调用MatrixGraph的generateDG方法生成完整图的DOT语言代码,调用shortestPath生成最短路径示意图的DOT语言代码,这里输入的参数0和4代表顶点编号,0是指北京,4是指宁波,也就是求从北京到宁波的最短路径

String graph=mg.generateDG();
String shortestPath=mg.printShortestPath(0, 4);

再将DOT语言代码嵌入到HTML代码中

String html1=GenerateHTML.Generate(graph);
String html2=GenerateHTML.Generate(shortestPath);

最后将HTML代码写入文件

WriteFile.write(html1);
WriteFile.writeShortest(html2);

生成的效果如下:

  • 完整图
    完整图.PNG
  • 最短路径示意图
    最短路径示意图.PNG