布局器
阅读本章请先读概要
Graph::Easy的布局器负责把内部图形表示转换成一个特定的布局；下面是对于同一种图形表示产生的两种不同的布局：
+---+ +---+ +---+
| A | --> | C | --> | D |
+---+ +---+ +---+
|
|
v
+---+
| E |
+---+
布局器的工作几乎都是自动完成的，这一章将会解释一些内部的实现细节。这会让你明白为什么某个图形的布局会是那样，另外，这回让你更好的指导布局器生成自己想要的布局。
要说明的是，使用函数as_txt()(纯文本），as_grapml(Graph ML)` 和as_graphviz并不是由这个布局器生成的；比如对于graphviz来说，真正的布局通过一个外部程序生成，如dot,neato`等。
概要
要生成一个特定的布局，Graph::Easy分三步完成：
- 首先，对节点进行分类并通过分组信息和rank信息放置在不同的组里面
- 然后它就会创建一个节点链，从有最少输入边的节点开始，尽可能找到最长的节点链；
- 最后一步，布局器把这些节点放置在一个格子板上，就像一个棋盘；当一个节点和连接它的节点放置好之后，布局器尝试寻找连接节点的边。
前两步影响了第三步处理节点的顺序；要找到最长的节点链，布局器会打散节点链并尽可能放在一条直线上。
下面是两个例子，第一个是在pre-v0.24版本上生成的图，第二个是v0.25版本的输出结果，这两个图的不同很明显地说明了这种布局策略的作用：
+------------------------------+
v |
+---------+ +--------+ +--------+ +---------+
| Koblenz | <-- | Bonn | --> | Ulm | --> | Bautzen |
+---------+ +--------+ +--------+ +---------+
| | |
| | |
| v |
| +--------+ +--------+ |
+-----------> | Berlin | --> | Kassel | |
+--------+ +--------+ |
^ |
+-----------------------------+
+--------------------------------------------+
| v
+------+ +---------+ +---------+ +--------+ +--------+
| Bonn | --> | Ulm | --> | Bautzen | --> | Berlin | --> | Kassel |
+------+ +---------+ +---------+ +--------+ +--------+
| | ^
| | |
| v |
| +---------+ |
+--------> | Koblenz | ----------------------+
+---------+
单元和布局
和其他的一些包不同，Graph::Easy工作在一个无穷大的网格板上；下面是一个7*3的单元格：
...........................................
: 0,0 : 1,0 : 2,0 : 3,0 : 4,0 : 5,0 : 6,0 :
...........................................
: 0,1 : 1,1 : 2,1 : 3,1 : 4,1 : 5,1 : 6,1 :
...........................................
: 0,2 : 1,2 : 2,2 : 3,2 : 4,2 : 5,2 : 6,2 :
...........................................
每一个节点可以占据一个或者多个单元格；同样，连接一个节点和另外一个节点的边也可以经过一个或者多个节点；然是，边只能走直线，不能是对角线。
下面是一个有两个节点和一条边的例子：（原文有颜色，这里表达不便，略去）：
...........................................
: 0,0 : 1,0 : 2,0 : 3,0 : 4,0 : 5,0 : 6,0 :
...........................................
:+---+: :+---+: : : : :
:| A |: --> :| B |: 3,1 : 4,1 : 5,1 : 6,1 :
:+---+: :+---+: : : : :
...........................................
: 0,2 : 1,2 : 2,2 : 3,2 : 4,2 : 5,2 : 6,2 :
...........................................
下面是占据多个单元格的边的例子：
...........................................
: : : : : : : :
: +--:-----:--+ : 3,0 : 4,0 : 5,0 : 6,0 :
: | : : v : : : : :
...........................................
:+---+: :+---+: : : : :
:| A |: --> :| B |: 3,1 : 4,1 : 5,1 : 6,1 :
:+---+: :+---+: : : : :
...........................................
: 0,2 : 1,2 : 2,2 : 3,2 : 4,2 : 5,2 : 6,2 :
...........................................
端口
从上面的例子可以看出，每一个单元格有四个端口，右边，下面，左边，和上面；这些方向也可以称作，东，南，西，北：
...........................................
: : : : : : : :
: 0,0 :North: 2,0 : 3,0 : 4,0 : 5,0 : 6,0 :
: : : : : : : :
...........................................
: :+---+: : : : : :
:West :| A |: East: 3,1 : 4,1 : 5,1 : 6,1 :
: :+---+: : : : : :
...........................................
: : : : : : : :
: 0,2 :South: 2,2 : 3,2 : 4,2 : 5,2 : 6,2 :
: : : : : : : :
...........................................
因此，如果一个节点刚好占据一个单元格，由于一个单元格之后四个端口，因此这个节点只能由四个边进入或者发出。
只有四个边是非常大的局限，为了克服这个缺点，一个节点可以占据多个单元格；如果一个节点需要更多的单元格来保证有足够多的端口的时候，这个节点会自动增大。
你也可以显式指出一个节点应该占据多少行和多少列，下一章详细讨论这个话题。
Edge pieces
总共有是一个基本的代表边的单元格。
.........................
: : | : | : :
:-----: | :--+--: :
: : | : | : :
.........................
: : | : | : :
: +--: +--:--+ :--+ :
: | : : : | :
.........................
: : | : | : | :
: : v : | : | :
:--+--:--+--:->+ : +<-:
: ^ : : | : | :
: | : : | : | :
.........................
每一个Edge pieces都可以与起点（对于垂直的边不可见，水平边是空格）和终点（箭头）相结合。不是所有的组合都是有效的，但是布局器会充分利用空间来自动选择。
下面是一些水平边的可能组合：
.........................
: : : : :
: --> :---> : ----: <---:
: : : : :
.........................
: : : : :
: <-> : --- :-----: :
: : : : :
.........................
另外，还有四种自循环的Edge pieces，用来把一个边和它自己连接起来：
.........................
: : : : | ^ :
: +- : -+ : : +-+ :
: | : | : : :
: +> : <+ : +-+ : :
: : : v | : :
.........................
这四个edge pieces每一个都有一个起点和终点，虽然他们可能由零个，一个或者两个箭头。
边标签
垂直，水平和自循环的边可以有一个标签，标签出现的位置由布局器自动选择。
边交叉
边与边之间可以交叉，但是布局器会尽量避免交叉的情况。哪些边可以交叉以及在哪里可以交叉都是由约束条件的，通常，一个边只能与另外一个没有标签的边正交。
看看下面这个强制的布局——实际情况并不会这样，除非你通过把上面一排节点的空格堵住来强制这么做。
+----------+ +---------+ +----------+ +----------+
| Koblenz | <.- | Bonn | --> | Ulm | --> | Bautzen |
+----------+ +---------+ +----------+ +----------+
^ : | |
| : +-----------+ |
| v | |
| +---------+ +----------+ | |
| | Berlin | --> | Kassel | | |
| +---------+ +----------+ | |
| ^ | |
+----------------+---------------------------+ |
| |
| |
+--------------------------------+
根据最先创建的节点的不同，交叉的位置也有可能是这样：
+----------+ +---------+ +----------+ +----------+
| Koblenz | <.- | Bonn | --> | Ulm | --> | Bautzen |
+----------+ +---------+ +----------+ +----------+
^ : | |
| : +----------------+--+
| v | |
| +---------+ +----------+ | |
| | Berlin | --> | Kassel | | |
| +---------+ +----------+ | |
| ^ | |
| +--------------------------------+ |
| |
| |
+----------------------------------------------------+
在上面的图中Ulm到Koblenz的边和Bautzen到Berlin的边发生了交叉；另外一个看起来更好的方式是穿过Bonn到Berlin的边，但是由于这个边非常短，因此并不会被交叉。
Edge Joints
当两个或者更多的边共享一个起点（不仅仅指同一个方向）的时候，它们可能在某个地方发生分叉；同样，如果两个或者更多的边共享一个终点，那么它们有可能在某个地方汇聚在一起。
[ Potsdam ], [ Mannheim ]
--> { end: back,0; }
[ Weimar ]
--> { start: front,0; } [ Finsterwalde ], [ Aachen ]
+----------+ +--------+ +--------------+
| Mannheim | ------+-> | Weimar | -+-----> | Finsterwalde |
+----------+ | +--------+ | +--------------+
| |
| |
| |
+----------+ | | +--------------+
| Potsdam | ------+ +-----> | Aachen |
+----------+ +--------------+
请查阅hinting这一章获取更详细的内容。
多单元格的节点
默认情况下，一个节点就占据一个单元格；布局器会通过边来适当调整单元格的大小；也可以通过[size][2]属性来指定某个单元格最小的大小。
...........................................
: : : : : : : :
: 0,0 :North:North: 3,0 : 4,0 : 5,0 : 6,0 :
: : : : : : : :
...........................................
: :+---------+: : : : :
:West :| A |: East: 4,1 : 5,1 : 6,1 :
: :+---------+: : : : :
...........................................
: : : : : : : :
: 0,2 :South:South: 3,2 : 4,2 : 5,2 : 6,2 :
: : : : : : : :
...........................................
...........................................
: : : : : : : :
: 0,0 :North:North: 3,0 : 4,0 : 5,0 : 6,0 :
: : : : : : : :
...........................................
: :+---------+: : : : :
:West :| |: East: 4,1 : 5,1 : 6,1 :
: :| |: : : : :
.......| A |.........................
: :| |: : : : :
:West :| |: East: 4,2 : 5,2 : 6,2 :
: :+---------+: : : : :
...........................................
: : : : : : : :
: 0,3 :South:South: 3,3 : 4,3 : 5,3 : 6,3 :
: : : : : : : :
...........................................
路径寻找
要找出从一个节点到另外一个阶段的路径（有可能是同一个），布局器有两种方式进行：
- 启发式的寻找（捷径），下面的情况会使用启发式算法寻径：
- 如果一个节点可以通过直线到达的时候
- 如果可以通过最多一个转折可以找到的时候
- 是自循环的时候
- 对于其他的所有情况，启发式算法无法寻找路径；会使用通用的A星搜索算法。
请查询A星搜索算法进一步了解。