项目背景

算法设计

实验难点

动画演示

束化效果

后续工作

参考文献

图所包含的信息量很难在计算机屏幕上显示

图（Graph）在生活中被普遍应用于表示物体之间的相互关联。 尽管计算机设备发展迅速，但也难以跟上信息爆炸似的增长，很快图所包含的信息量很难在计算机屏幕上显示，比如图中节点数大于屏幕像素的时候。 这对人们直观地在屏幕上观察一个图并发现图中的内在信息产生了很大的障碍。

边束化将相似的边绑在一起提高图的清晰度

这个问题的一种解决方案是对图本身的简化，例如用一个复杂节点表示一堆相似并且融合了的点，这个复杂节点可以通过鼠标选择观察内部所含的普通节点。这种技术有时候是在所难免的，比如图中节点数大于屏幕像素的时候，它的缺点是视野离散、缺乏连续性。 另一种解决方案是在图可视化的时候进行优化，例如边束化。
边束化通过将相似的边绑在一起来提高图的清晰度，体现出图的内在模式。边束化仅对图中的边进行可视化优化，一般认为图的顶点位置给定（可以由其他方法事先优化得到）。 它在2006年由Danny Holten第一次提出[1]，如上图所示，通过控制边被绑在一起的紧密程度，让用户在细节与宏观模式间平滑地转化。边束化以后，不仅主要趋势明显了，一些细节（图的右下角部分）也更加清晰了。

借助计算几何知识提出自己的算法

Holten的算法只能处理有一个树状结构的节点之间的连线。 而其他人提出的算法有各自的不足之处，如Geometry-Based Edge Clustering[2]造成边束过于弯曲， 人眼难以跟踪，Force-Directed Edge Bundling[3]以及Winding Roads[4]的效率较低。 我们想利用计算几何中的知识提出自己的算法。在结果分析中与其他算法进行了对比。

利用交点衡量边的趋势

一个图中，边的趋势可以由很多信息衡量，比如边的方向、彼此之间的距离、节点连接关系等。这些因素比较复杂，因此边束化是一个比较困难的问题。
借助计算几何的知识，或许可以通过交点信息来衡量边的走势：对于一般的图，彼此靠近的边往往有很多交点。

融合交点得到边的控制点

交点往往数据巨大，而且很显然，每个边都通过由自己产生的交点。如果稍微移动这些交点的位置并且仍然让边通过它（这时边会变为曲线），就有可能通过把交点融合得到合适的控制点。这样做的一个优点是融合交点造成相应边被捆绑的效果可以由动画直观地对应。

通过BO算法求图的交点

扫描线求交点的BO算法一方面不太难实现，另一方面也有可以接受的时间复杂度。从后面的结果分析中可以知道确实足够快。

采用的数据结构

本实验实现扫描线求交点的BO算法，利用这个算法进行边束化，并设计软件演示这一过程。

实验过程中遇到的主要难点在于算法设计和由于数据量非常大造成的实现问题。

难点一：如何融合交点

融合的过程可以比较自然地认为是取所有交点的平均。融合的难度在于决定哪一些交点应该被融合在一起，以产生光滑合理紧凑的边束。

首先必须解决什么样的交点适合被融合。很自然的，应该是“相似”的交点。这个“相似”不仅表示几何位置上相似，而且应该含有“相似”的边。如果从边被绑在一起的角度考虑，因为融合后的交点会对所有包含的边产生一个共同的控制点，因此希望这一些边彼此之间交点很多（证明这些边确实联系紧密应该被捆绑）。
综合以上分析，得到一个数学模型：如果有n个交点，它们分布在面积为S的区域内，并且由m条边产生， 则希望以下分数最高：

score = n/(m(m-1)S)

这个分数高一方面要求融合的交点所在的面积小，一方面还要求这些交点由尽可能少的边产生。
之所以选择m(m-1)，是因为如果m条边两两相交最多产生m(m-1)/2个交点。以此为目标可以设计优化函数：在所有对交点进行划分的方式中选择一个，使得融合的分数平均最大。 为了鼓励融合，S可以设一个下界。这样的方式虽然理论结构清晰，但是难以求解。即使用人工智能的方式可以解决，效率也不高，因为 交点的数目非常庞大（可以是图中边的数目的平方倍）。
考虑用几何的方式求解，最终设计算法如下：

1. 将图划分成a*a的小格。小格的大小由局部交点个数决定。
2. 将所有小格内的交点融合。（这是因为它们地理位置非常相近，典型的小格大小是5px*5px）。
3. 对图中的每个小格进行迭代：顺序考虑每个小格的8个邻居，分别计算与该邻居融合后的平均分数增长，找到增长最大的邻居，如果该增长大于0，则与其融合。为了鼓励融合，对融合后小格的分数乘以一个“融合因子”（实现时选取3）。
4. 重复3直至整张图没有新的融合发生。

为了使形成的曲线光滑，还需要对控制点进行合理的排序，并控制点中的尖锐变化。

难点二：BO算法的数值不稳定问题

这个问题是由于红黑树查找元素时依赖的Compare()函数的数值不稳定造成的。
当线段很少时无论怎么设计Compare()都不会出错，但是当测试数据达到10000多条线段时，数值不稳定的问题就很突出。
在网络学堂上请教老师以后得到很好的解答。思想是每个线段存储在红黑树中的对应指针，只依赖左右孩子及父节点等连接关系就可以完成IntersectEvent与RightPointEvent的操作。因此Compare()函数可以只针对LeftPointEvent，从而通过ToLeft()实现。

难点三：交点的表现形式

图中交点往往非常多，即使一个像素代表一个交点也会彼此重叠导致无法辨认，
而且边束化往往注重体现图中的宏观模式而不是某个交点的具体位置。
因此设计将交点扩散成一个区域并互相叠加，形成类似“降水量”图的效果(见下图)。
这样不仅美观，也能体现出图的宏观模式。这是在可视化上的一个设计。

难点四：流畅的动画效果

首先碰到的问题是移动单根的扫描线。本来是很简单的动画，因为图中的边过多，底层判断这个移动的扫描线与边的覆盖关系非常耗时。解决方案是将边渲染完成后存成一张图片，以图片的方式显示。
其次是交点的绘制，因为交点的特殊表现形式，可以用bitmap来绘制。但在显示由于交点融合造成的边捆绑时，不可避免地需要绘制很多曲线，会比较耗时。 因此最大的图migrations.xml还是有一些卡, 动画演示  ->   演示视频 中有加速播放的美国移民图边束化动画。 值得指出的是这仅仅是动画的不流畅，不是边束化算法的效率问题。

界面展示

界面设计如下——可以打开一个GraphML（通用格式）或者.graph文件进行边束化，或者自己绘制直线进行边束化。使用方式参见演示视频。

点击“bundle it!”按钮以后开始边束化的动画。
整个过程分为扫描线求交点和融合交点进行边束化两个阶段。

第一阶段,扫描线水平扫过区域，将此时已经确定的交点绘制出来。

第二阶段，交点被融合，相应地边被捆绑在一起,如下图所示。

演示视频

演示视频1——如何使用本软件

演示视频2——美国移民图的边束化动画演示（加速）

实验数据

SampleTestData文件夹下包含小规模的随机生成数据graph1.xml、偏小规模的人工生成数据links15_simple.xml（几百条边）、中等规模的实际数据eb_link.xml（近百个点）、中等偏上规模的实际数据airline.xml（美国航线图，上千条边）、大规模的实际数据migrations.xml（美国移民图，近万条边）。
以上数据都是通用的GraphML格式。其中美国航线图和移民图被边束化方向的论文中广泛测试。下面会有效率及边束化效果的对比。当然用户也可以手绘数据并保存结果。

边束化结果

以下是两个简单图的边束化结果。左图为原始图，右图为边束化结果。因为图本身比较简单，束化效果不明显，但是可以看出算法的合理性。

上面的圆形图中，左上角清晰了很多，右上角部分的几个边束也被很好地表现出来。
下面对比美国航线图的束化效果。从上至下分别为Geometry-Based[2]，Force-Directed[3]， Multilevel Aggregated[5]以及本算法的结果。
本算法的线条略显松散，但是宏观模式很明显，线条比较流畅。松散一些的原因一方面是算法的问题，另一方面也是没有仔细地渲染淡化外围边（Outliers）。

以下是针对美国移民图的束化结果对比。从上至下分别为Geometry-Based[2]，Winding Roads[4] 和本算法。本算法和这两个算法相比确实显得不够清晰。一方面没有进行边的裁剪，另一方面边之间融合得不够，如果采用更加细致的交点融合算法可能会有更好的结果，例如全局最优的遗传算法或者模拟退火。因为时间的关系没有办法验证。但是算法确实也找出了一些图的模式。从某种程度上来说这种模式也是更加可信的。

算法效率

算法用WPF在VS2010上实现。系统为win7，以下数据在Intel® Core™ i5-2410 CPU @2.3GHz下测试得到。 时间并不是完全紧的，因为这两个阶段的时间内都为后面的动画生成了必要的数据。

可以看出在没有进行刻意优化的情况下，效率已经可以接受。比Geometry-Based[2]略慢，比Force-Directed[3]快不少。

更加细致的点融合算法

目前的点融合是局部优化的，可能会造成融合度不够等问题。 因此可以考虑更加精细合理的融合算法，例如人工智能领域的遗传算法等全局最优算法。

优化公式考虑边的方向

目前的优化公式融合的交点群具有聚集面积小、所含交点个数多、所含边数目少的特点。我们可以进一步考虑“相似性”，即融合的交点应该包含的是方向相似的边。

进一步调整动画的流畅性

当边的控制点发生变化时，可以不要重新生成曲线，而是在现有曲线上进行调整。

附录：参考文献

[1] D. Holten. Hierarchical edge bundles: Visualization of adjacency relations in hierarchical data. IEEE Transactions on Visualization and ComputerGraphics, 12(5):741–748, 2006.

[2] W. Cui, H. Zhou, H. Qu, P.C. Wong, and X. Li. Geometry-Based Edge Clustering for Graph Visualization, IEEE Transactions on Visualization and Computer Graphics (TVCG: Proc. of InfoVis'08), vol.

[3] D. Holten, and J.J.v. Wijk. Force-Directed Edge Bundling for Graph Visualization, Computer Graphics Forum (Proceedings of Eurographics/IEEE-VGTC Symposium on Visualization), vol. 28, no. 3, pp. 983-990, 2009.

[4] A. Lambert, R. Bourqui, and D. Auber. Winding roads: Routing edges into bundles. In 12th Eurographics/IEEE-VGTC Symposium on Visualization (Computer Graphics Forum; Proceedings of EuroVis 2009). To appear., 2010.

[5] Emden R. Gansner, Yifan Hu, Stephen North, Carlos Scheidegger. Multilevel Agglomerative Edge Bundling for Visualizing Large Graphs. In Pacific Visualization Symposium (PacificVis), 2011 IEEE, pages 187 – 194, 2011.

[6] M. Dickerson, D. Eppstein, M. T. Goodrich, and J. Y. Meng. Confluent drawings: Visualizing non-planar diagrams in a planar way. J. Graph Algorithms Appl., 9(1):31–52, 2005.

[7] D. Phan, L. Xiao, R. Yeh, P. Hanrahan, and T. Winograd. Flow map layout. IEEE Symposium on Information Visualization 2005, pages 219–224, 2005.

[8] H. Zhou, X. Yuan, H. Qu, W. Cui, and B. Chen. Visual clustering in parallel coordinates. Computer Graphics Forum, 27(3):1047–1054, 2008.

[9] H. Zhou, X. Yuan, W. Cui, H. Qu, and B. Chen. Energy-based hierarchical edge clustering of graphs. In Visualization Symposium, 2008. PacificVIS ’08. IEEE Pacific, pages 55–61, 2008.

[10] H. Qu, H. Zhou, and Y.Wu. Controllable and progressive edge clustering for large networks. In Proceed. of Symposium on Graph Drawing, pages 399–404, 2006.

Group F