\[2019春软件构造\]优化笔记：我是如何将实验五的建图操作压缩到1.5s的

发表于 | 更新于 | | 阅读次数：

本文使用JGraphT存储Social Network中的人际关系图结构，使用JGraphT中的预设算法压缩建图时间。

注：这里的建图时间包含最短路求解与轨道插入，下文重点优化最短路求解时间。

背景

之前写完软件构造Lab2时，rainywang有建议过将Lab2的Graph ADT进行封装以便之后的使用。

在写Lab3时的Social Network时，为了保存和处理关系图，一开始我直接迁移了Lab2的代码，将Lab2的ADT搬到Lab3并添加了数个API。但看到标签为Larger的几个文件，心里还是对Lab2中naïve的ADT实现感到担忧。仅仅一个返回邻接顶点的操作时间复杂度都要O(n)，明显它是不能够胜任Lab3或者之后的Lab5的性能要求的。

rainywang在Lab2课程结束时，不仅建议过封装Lab2的ADT，也提出了这样一个疑问：网上是否已经有相关图算法ADT了？这个既是疑问又带有明显暗示的说法让人感到不安，显然图算法这个轮子已经被人重造过很多次了，我当然有理由相信有人已经为之写出了不错的java库。

抱着找找看的心理，在Google上尝试搜索了下”java graph library”，在返回的第一个结果发现了JGraphT，它的开源许可证为 Eclipse Public License - v 2.0。

JGraphT Logo

a Java library of graph theory data structures and algorithms

flexible

any object can be used for vertex and edge types, with full type safety via generics
edges can be directed or undirected, weighted or unweighted
simple graphs, multigraphs, and pseudographs

powerful

specialized iterators for graph traversal (DFS, BFS, etc)
algorithms for path finding, clique detection, isomorphism detection, coloring, common ancestors, tours, connectivity, matching, cycle detection, partitions, cuts, flows, centrality, spanning, and the list goes on

efficient

designed for performance, with near-native speed in many cases
adapters for memory-optimized fastutil representation

支持带权有向边、无向边，实现好的BFS和最短路算法，以及高效率。满足了Lab3的所有要求，同时也许能顺便满足Lab5的性能需求。此时我还有些犹豫，因为我不确定在Lab3 deadline将至的情况下，JGraphT的学习成本是否可以平衡掉之后代码的调试时间。不过考虑到JGraphT的算法实现较全可以比较容易的满足需求的变化，以及著名的Don’t reinvent the wheel原则，我还是花了两个小时来阅读文档，事后证明这是一个没有让我后悔的决定。

实现

JGraphT的Graph ADT默认支持两种边：带权边DefaultWeightedEdge和无权边DefaultEdge。Social Network需要保存人与人之间的关系以及亲密度，且312change中人的关系是有向的。因此我创建了两张有向图，分别用于保存人与人之间的关系以及亲密度：

1
2
protected Graph<String, DefaultWeightedEdge> intimacy = new SimpleDirectedWeightedGraph<>(DefaultWeightedEdge.class); //亲密度图
protected Graph<String, DefaultEdge> relation = new SimpleDirectedGraph<>(DefaultEdge.class); //关系图

对节点和边的操作类似于Lab2中定义的API：

1
2
3
4
intimacy.addVertex(name1); //插入节点
DefaultWeightedEdge e = intimacy.addEdge(name1, name2); //插入边
intimacy.setEdgeWeight(e, intimacy); //设置边权
relation.removeEdge(name1, name2); //删除边

计算Friend所在的轨道需要得到Friend与中心点User的最短距离。担心之后可能出现奇怪的需求（如要求轨道以亲密度的最短距离来定义），我一开始没有根据关系没有边权或者说图边权相等这一条件采用BFS，而采用了在最短路问题中适用度更高的Dijkstra算法。JGraphT中的Dijkstra算法实现疑似使用了Decorator模式，调用十分简洁：

1
2
3
4
5
6
7
DijkstraShortestPath<String, DefaultEdge> dijkstraAlg = new DijkstraShortestPath<>(relation); //定义算法
SingleSourcePaths<String, DefaultEdge> iPaths = dijkstraAlg.getPaths(centralName); //求以centralName为起点的单源最短路

GraphPath<String, DefaultEdge> path = iPaths.getPath(name); //获取name节点的最短路
if(path != null) {
    int track = path.getLength(); //得到最短路距离
}

此时对Lab3的Larger文件进行读取和建图操作时间已经压缩到了3s左右。

这里还有一个有趣的插曲：在写完了Lab3不久，在一节形式语言与自动机课上，老师打趣地布置了一个画有2k个点的DFA的任务，并开玩笑说要画出这个图要相当一段时间，能画出这个图的学生期末加5分。JgraphT支持伪图非常适合用来表示自动机，而且自带GraphViz导出API。结果在下午老师布置那个任务之后的3个小时，我就画出了那张图。

这个项目放在https://github.com/mhlwsk/DFA

果然软件构造助力数学课程的学习。

Lab5中的数据量急剧扩大，虽然Dijkstra的速度非常快（时间复杂度为O(E*log(E))，单纯建图只需要数秒），但仍有优化的余地。考虑到关系边权相等这一条件，我把Lab3中采用的Dijkstra换成了时间复杂度为O(n)的BFS，JGraphT中的BFS采用迭代器模式实现，它的调用也非常简洁：

1
2
3
4
5
6
7
8
9
BreadthFirstIterator<String, DefaultEdge> bfsIterator = 
    new BreadthFirstIterator<>(relation, centralName); // 定义BFS序迭代器，以centralName为遍历起点

while (bfsIterator.hasNext()) {
    String name = bfsIterator.next();
	// ...
    int distance = bfsIterator.getDepth(name); // 获取BFS深度
	// ...
}

此时Lab5中的SocialNetworkCircle.txt文件建图时间已经压缩到了1.5s左右。

这里有一个插曲：搜索JgraphT的API时，我发现一个BFSShortestPath<V,E>类，它的API与之前用到的DijkstraShortestPath<V,E>一致。一开始我尝试直接把后者改成前者，但编译器提示BFSShortestPath<V,E>不存在。在确认了不是包导入的问题后，我查看了Github上BFSShortestPath的源码，发现这个文件是13 Feb创建的。而截至此文写作时（1 June）JgraphT最新的release 1.3.0是在13 Nov 2018发布的。也即JGraphT的doc比release都要新。显然这是Javadoc基于最新的源码自动生成的，这里不得不感叹一下javadoc的强大。

结语

不要重新发明轮子，当面对一个具体问题时优先考虑下是否已经有较好的实现了，使用它们可能有助于减轻代码实现与调试导致的焦虑、脱发与偏头痛，并且能够获得较好的可靠性与效率。

不过，使用JGraphT似乎与过早优化原则相抵触：

Premature optimization is the root of all evil – Donald Knuth

我的理解是，如果优化使得软件的其它各项指标（如可变性）急剧下降，那么滞后优化是必要的；而采用JGraphT作为一项优化使得应用的changeability反而有所增加，此时就不必拘泥教条。毕竟，软件开发的过程也是软件的各项指标相互折衷的过程。