绘图简介
Mathematica 提供了美观的绘图函数. 已实现的算法包括弹簧嵌入（spring embedding）、弹簧电嵌入（spring-electrical embedding）、高维嵌入（high-dimensional embedding）、径向嵌入（radial drawing）、随机嵌入（random embedding）、环形嵌入（circular embedding）和螺旋嵌入（spiral embedding）. 此外，我们还为用户提供了有向图的分层/分级绘图算法和树的绘制算法. 这些算法使用以下四种函数实现：
GraphPlot、
GraphPlot3D、
LayeredGraphPlot 和
TreePlot.
绘图函数.
GraphPlot 和
GraphPlot3D 适合一般图的直线绘制.
LayeredGraphPlot 试图在一系列层上绘制图的各个顶点； 因此，它最适合应用于诸如流程图的绘制之类的情况.
TreePlot 对于绘制树或者类似树形的图特别有用. 这些函数的设计原理使它们可以有效地应用于相当大规模的图.
以下显示了使用这四种函数中的每一种所绘制出来的图.
Out[1]//TableForm= |
| |  |
在这些函数中，一个图或者由形如
的规则列表表示，其中
和
是顶点，或者由图的邻接矩阵表示. 我们也支持以
Combinatorica 程序包格式表示的图.
图论符号
图
是由一组顶点
（也称为节点）和一组边
组成的. 如果
，那么
和
这两个顶点组成了图的一条边.
如果
同时也满足
，那么
是一个无向图. 否则，它是一个有向图. 前者可以使用线段绘制，而后者可以使用箭头绘制. 在一个无向图中，使用符号
来表示
和
之间的边常常是方便的.
| Out[2]= |  |
| Out[3]= |  |
输入格式
在
Mathematica 中，图可以由以下三种数据结构之一表示. 一个图可以由一个规则列表表示.
例如，
表示以下有向图.
| Out[4]= |  |
一个图也可以使用它的邻接矩阵表示. 设
是一个有向图. 假设顶点是从
到
的索引值，也就是说，
，那么
的邻接矩阵是一个
×
矩阵，其中，如果
，则
；否则
.
另一方面，一个无向图由对称的邻接矩阵表示. 如果
，则矩阵中的元素
；否则，
.
| Out[5]= |  |
由于邻接矩阵中含有值为零的元素，使用
SparseArray 表示矩阵往往是方便的.
最后，也支持以
Combinatorica 程序包格式表示的图.
这个例子使用
Combinatorica 创建了一个蝴蝶图，并且显示
Combinatorica 所分配的布局.
| Out[8]= |  |
| Out[9]= |  |
GraphPlot 使用
下一节中描述的算法来展开一个图. 如果
GraphPlot 用于
Combinatorica 格式的图，但是由
Combinatorica 所分配的绘图法被保留（preserved），则可以指定
Method->None.
| Out[10]= |  |
绘图算法
图经常被用来封装项之间的关系. 图的绘制使这些关系可视化. 可视化表示的益处取决于绘图是否美观. 虽然对于美观的绘图没有严格的标准，人们普遍认为美观的绘图应该具有最小的边的交叉度和一致的顶点间距. 在各种文献中对这个问题都进行了广泛深入的研究 [
1]，并且其中也提出了许多解决方法. 两个流行的直边绘图算法，弹簧嵌入和弹簧电嵌入，都通过最小化图的物理模型的能量来实现. 另一方面，高维嵌入法在高维空间中嵌入图形，并且把它投射回二维或者三维空间. 此外，还有以分级方式绘制有向图，以及绘制树形图的算法. 随机嵌入、环形嵌入和螺旋嵌入不使用图布局的任何连接信息，因此，对这些算法这里不做进一步的讨论.
弹簧嵌入
弹簧嵌入算法在每个节点对之间分配"力量". 当两个节点太靠近的时候，就产生排斥力. 而当两个节点距离太远的时候，它们就受到吸引力影响. 这种情况可以利用由弹簧连接的顶点来说明——因此得名"弹簧嵌入".
该算法通过对所有边添加弹簧，并且在所有不相邻的顶点对之间添加宽松的弹簧来实现. 因此，在二维空间，系统的总能量为
这里，
和
是节点
和
的坐标向量，而
是它们之间的欧式距离.
是顶点
和顶点
之间的弹簧的自然距离，并且可以被选作
和
之间的图距离. 参数
是弹簧的强度，其中
是表示弹簧强度的参数.
是顶点数.
图顶点的布局通过最小化能量函数来计算. 最小化能量函数的一个方法是沿着弹簧力的方向迭代移动每个顶点直到大致达到平衡. 多级技术用于克服局部极小问题.
弹簧嵌入特别适用于类似规则网格图的问题，在规则网格图中，它对图的布局方式可以使得顶点之间的欧式距离与图距离成正比.
这里使用弹簧嵌入算法绘制一个 20×20 网格图.
| Out[12]= |  |
但是，该方法需要更多的内存和CPU时间. 为了降低它的
复杂度，相距比较远的顶点在力量和能量计算中被忽略. 参见
GraphPlot 和
GraphPlot3D 方法选项
以获取更多信息.
弹簧电嵌入
弹簧嵌入算法的缺点是它需要知道每对顶点之间的图距离. 弹簧电嵌入法使用两种力量. 吸引力
限于相邻的顶点，并且与它们之间的欧式距离成正比，其中
与自然弹簧长度相关. 另一方面，电势力，
，是全局的，并且与节点
和
之间的欧式距离成反比. 总体而言，用来最小化的能量为
，其中
这里，
是调节排斥力和吸引力相对强度的常量，而
是节点
和
之间的欧式距离. 对于具有两个顶点的图，顶点之间的理想欧式距离是
，从而使得总能量为零.
图顶点的布局通过最小化能量函数来计算. 这样做的一个方法是通过沿着弹簧力的方向迭代移动顶点，直到大致达到平衡. 多层技术 [
7] 用于克服局部极小问题，而八叉树数据结构 [
16] 用于在某些情况下降低计算复杂性.
一般情况下，弹簧电嵌入对大多数问题都适用. 使用多层技术和八叉树技术，可以在复杂度为
下有效地完成.
这里使用
绘制一个 20×20 的网格图.
| Out[14]= |  |
该算法的一个副作用是外围的顶点往往比中心的顶点彼此更加接近，这一点在前面绘制的图中可以看出. 这种趋势可以使用方法选项
缓解，如
"一般绘图" 中所述.
高维嵌入算法
在高维嵌入方法中，一个图嵌入在高维空间中，并且投影回二维或者三维空间中. 首先，
维坐标系统基于
个中心创建. 该中心是一组
个顶点的集合，这些顶点的选择是距离越远越好. 第一个顶点是随机选择的，然后每个剩余的中心选择距离前面选中中心最远的顶点. 换句话说，如果已经选定
个中心，那么
是满足下面条件的顶点：与
个中心的最短图距离大于或等于所有其它顶点与这
个中心的最短图距离.
在这
个中心的情况下，可以建立
维坐标系统. 每个顶点
具有坐标
，其中
是顶点
和中心
的图距离.
维坐标向量形成一个
×
矩阵
，其中
是
的第
行.
由于我们只可能在二维和三维空间绘图，并且由于这些坐标互相关联，这些
维坐标以合适的线性组合投影回二维或者三维空间. 假定具有
个坐标和
个中心的图投射到二维空间. 为了使投影不受偏移影响，
首先规范化为
.
令
和
是两个这样的
维向量. 它们应该是不相关的，所以它们必须互相正交.
要达到这个目的，用户把
和
选为
×
对称矩阵
的前两个最大的特征值所对应的特征向量. 选择两个高度不相关的向量的过程也称为主成分分析（principal component analysis）.
总体说来，对于二维绘图，高维嵌入方法使用由
和
给出的顶点坐标.
这里使用
绘制一个 20×20 网格图.
| Out[16]= |  |
高维嵌入方法往往是非常快的，但是其结果的质量往往比力导向（force-directed）算法更低. 这种方法可以使用
GraphPlot 和
GraphPlot3D 中的
Method
指定.
有向图的分级绘制算法
用于绘制有向无圈图（DAGs）的算法依据 Sugiyama et al 的思想. [
14]，以及随后的发展 [
15]. 它包括以下阶段：
1. DAG 的顶点首先被赋以初步的
级别，使得如果从
到
，存在一条边，那么很可能
. 这是为了确保最后的绘图具有大多数方向向下的有向边.
2. 生成
坐标，以使得如果从
到
有一条边，并且
，则它们的
坐标尽可能接近，但是使用一个集合最小化分隔. 这确保了最终绘制的图不含有许多很长的边. 这个过程把这些顶点分配给有限数目的层. 如果一条边穿过很多层，那么增加虚拟的顶点.
3. 对于每个顶点赋以初步的
级别，以最小化边的交叉数目.
4. 
坐标由最小化
产生，其约束条件为在同一层的顶点遵从第3步产生的
级别，并且使用一个集合最小化分隔.
由此产生的绘图法在一个层次结构上展示该图，其中大多数的边都层下降趋势.
LayeredGraphPlot 函数实现该算法.
绘制树的算法
绘制树的两种算法是径向绘图法和分层绘图算法 [
1]. 在径向绘图算法中，对这个树选择一个合适的根. 然后，从树的根开始，在楔形中绘制每个子树，其中楔形的角与子树中的叶子数目成正比. 在分层绘图算法中，给该树选择一个合适的根. 然后，从根开始，迭代地绘制根的子树，使得在同一层的顶点具有同样的
坐标，而相邻子树在水平上最接近的顶点相距单位距离. 根位于子树的
坐标的中心，而它的
坐标在它们上面一个单位.
TreePlot 函数在这两种算法之间选择，取决于函数的第二个参数.
选择合适的绘图函数
对于一般的图的绘制，考虑使用
GraphPlot 或者
GraphPlot3D.
GraphPlot 或者
GraphPlot3D 计算一个视觉上美观的二维/三维布局，并且使用这样的布局绘图. 参见
"一般绘图" 以获得这些函数的详细信息，以及参见 [
17] 以获得算法的详细信息.
为了获得有向图的分层/分级绘制法，使用
LayeredGraphPlot.
LayeredGraphPlot 试图在一系列层结构中绘制图的顶点，其中主导顶点位于上方，而在层级中较低位置的顶点逐步往下. 这种函数最适合于应用如流程图绘制. 参见
"有向图的分层绘制" 以获得该函数的详细信息.
TreePlot 专门设计用来绘制树和类树图. 参见
"树形图" 以获得该函数的详细信息.
参考文献
[1] Di Battista, G., P. Eades, R. Tamassia, and I. G. Tollis. Graph Drawing: Algorithms for the Visualization of Graphs. Prentice Hall, 1999.
[2] Fruchterman, T. M. J. and E. M. Reingold. "Graph Drawing by Force-Directed Placement." Software—Practice and Experience 21, no. 11 (1991): 1129-1164.
[3] Eades, P. "A Heuristic for Graph Drawing." Congressus Numerantium 42 (1984): 149-160.
[4] Quinn, N. and M. Breuer. "A Force Directed Component Placement Procedure for Printed Circuit Boards." IEEE Trans. on Circuits and Systems 26, no. 6 (1979): 377-388.
[5] Kamada, T. and S. Kawai. "An Algorithm for Drawing General Undirected Graphs." Information Processing Letters 31 (1989): 7-15.
[6] Harel, D. and Y. Koren. "Graph Drawing by High-Dimensional Embedding." In Proceedings of 10th Int. Symp. Graph Drawing (GD'02), 207-219, 2002.
[7] Walshaw, C. "A Multilevel Algorithm for Force-Directed Graph-Drawing." J. Graph Algorithms Appl. 7, no. 3 (2003): 253-285.
[8] Cuthill, E. and J. McKee. "Reducing the Bandwidth of Sparse Symmetric Matrices." In Proceedings, 24th National Conference of ACM, 157-172, 1969.
[9] Lim, A., B. Rodrigues, and F. Xiao. "A Centroid-Based Approach to Solve the Bandwidth Minimization Problem." In Proceedings of the 37th Annual Hawaii International Conference on System Sciences (HICSS'04), 30075.1, 2004.
[10] Barnard, S. T., A. Pothen, and H. D. Simon. "A Spectral Algorithm for Envelope Reduction of Sparse Matrices." Journal of Numerical Linear Algebra with Applications 2, no. 4 (1995): 317-334.
[11] Sloan, S. "A Fortran Program for Profile and Wavefront Reduction." International Journal for Numerical Methods in Engineering 28, no. 11 (1989): 2651-2679.
[12] Reid, J. K. and J. A. Scott. "Ordering Symmetric Sparse Matrices for Small Profile and Wavefront." International Journal for Numerical Methods in Engineering 45, no. 12 (1999): 1737-1755.
[13] George, J. A. "Computer Implementation of the Finite-Element Method." Report STAN CS-71-208, PhD Thesis, Department of Computer Science, Stanford University, Stanford, California, 1971.
[14] Sugiyama, K., S. Tagawa, and M. Toda. "Methods for Visual Understanding of Hierarchical Systems." IEEE Trans. Syst. Man, Cybern. 11, no. 2 (1981): 109-125.
[15] Gansner, E. R., E. Koutsofios, S. C. North, and K. P. Vo. "A Technique for Drawing Directed Graphs." IEEE Trans. Software Engineering 19, no. 3 (1993): 214-230.
[16] Quigley, A. "Large Scale Relational Information Visualization, Clustering, and Abstraction." PhD Thesis, Department of Computer Science and Software Engineering, University of Newcastle, Australia, 2001.
[17] Hu, Y. F. "Efficient, High-Quality Force-Directed Graph Drawing." The Mathematica Journal 10, no. 1 (2006): 37-71.
