布局器

阅读本章请先读概要

Graph::Easy的布局器负责把内部图形表示转换成一个特定的布局；下面是对于同一种图形表示产生的两种不同的布局：

布局器 - 图1

  1. +---+     +---+     +---+
  2. | A | --> | C | --> | D |
  3. +---+     +---+     +---+
  4.             |
  5.             |
  6.             v
  7.           +---+
  8.           | E |
  9.           +---+

布局器的工作几乎都是自动完成的，这一章将会解释一些内部的实现细节。这会让你明白为什么某个图形的布局会是那样，另外，这回让你更好的指导布局器生成自己想要的布局。

要说明的是，使用函数as_txt()(纯文本），as_grapml(Graph ML)和</code>as_graphviz<code>并不是由这个布局器生成的；比如对于</code>graphviz<code>来说，真正的布局通过一个外部程序生成，如</code>dot<code>,</code>neato等。

概要

要生成一个特定的布局，Graph::Easy分三步完成：

  • 首先，对节点进行分类并通过分组信息和rank信息放置在不同的组里面
  • 然后它就会创建一个节点链，从有最少输入边的节点开始，尽可能找到最长的节点链；
  • 最后一步，布局器把这些节点放置在一个格子板上，就像一个棋盘；当一个节点和连接它的节点放置好之后，布局器尝试寻找连接节点的边。

前两步影响了第三步处理节点的顺序；要找到最长的节点链，布局器会打散节点链并尽可能放在一条直线上。

下面是两个例子，第一个是在pre-v0.24版本上生成的图，第二个是v0.25版本的输出结果，这两个图的不同很明显地说明了这种布局策略的作用：

  1.  +------------------------------+
  2.   v                              |
  3. +---------+     +--------+     +--------+     +---------+
  4. | Koblenz | <-- | Bonn   | --> | Ulm    | --> | Bautzen |
  5. +---------+     +--------+     +--------+     +---------+
  6.   |               |                             |
  7.   |               |                             |
  8.   |               v                             |
  9.   |             +--------+     +--------+       |
  10.   +-----------> | Berlin | --> | Kassel |       |
  11.                 +--------+     +--------+       |
  12.                   ^                             |
  13.                   +-----------------------------+
  1.  +--------------------------------------------+
  2.   |                                            v
  3. +------+     +---------+     +---------+     +--------+     +--------+
  4. | Bonn | --> | Ulm     | --> | Bautzen | --> | Berlin | --> | Kassel |
  5. +------+     +---------+     +---------+     +--------+     +--------+
  6.   |            |                               ^
  7.   |            |                               |
  8.   |            v                               |
  9.   |          +---------+                       |
  10.   +--------> | Koblenz | ----------------------+
  11.              +---------+

单元和布局

和其他的一些包不同，Graph::Easy工作在一个无穷大的网格板上；下面是一个7*3的单元格：

  1. ...........................................
  2. : 0,0 : 1,0 : 2,0 : 3,0 : 4,0 : 5,0 : 6,0 :
  3. ...........................................
  4. : 0,1 : 1,1 : 2,1 : 3,1 : 4,1 : 5,1 : 6,1 :
  5. ...........................................
  6. : 0,2 : 1,2 : 2,2 : 3,2 : 4,2 : 5,2 : 6,2 :
  7. ...........................................

每一个节点可以占据一个或者多个单元格；同样，连接一个节点和另外一个节点的边也可以经过一个或者多个节点；然是，边只能走直线，不能是对角线。

下面是一个有两个节点和一条边的例子：（原文有颜色，这里表达不便，略去）：

  1. ...........................................
  2. : 0,0 : 1,0 : 2,0 : 3,0 : 4,0 : 5,0 : 6,0 :
  3. ...........................................
  4. :+---+:     :+---+:     :     :     :     :
  5. :| A |: --> :| B |: 3,1 : 4,1 : 5,1 : 6,1 :
  6. :+---+:     :+---+:     :     :     :     :
  7. ...........................................
  8. : 0,2 : 1,2 : 2,2 : 3,2 : 4,2 : 5,2 : 6,2 :
  9. ...........................................

下面是占据多个单元格的边的例子：

  1. ...........................................
  2. :     :     :     :     :     :     :     :
  3. :  +--:-----:--+  : 3,0 : 4,0 : 5,0 : 6,0 :
  4. :  |  :     :  v  :     :     :     :     :
  5. ...........................................
  6. :+---+:     :+---+:     :     :     :     :
  7. :| A |: --> :| B |: 3,1 : 4,1 : 5,1 : 6,1 :
  8. :+---+:     :+---+:     :     :     :     :
  9. ...........................................
  10. : 0,2 : 1,2 : 2,2 : 3,2 : 4,2 : 5,2 : 6,2 :
  11. ...........................................

端口

从上面的例子可以看出，每一个单元格有四个端口，右边，下面，左边，和上面；这些方向也可以称作，东，南，西，北：

  1. ...........................................
  2. :     :     :     :     :     :     :     :
  3. : 0,0 :North: 2,0 : 3,0 : 4,0 : 5,0 : 6,0 :
  4. :     :     :     :     :     :     :     :
  5. ...........................................
  6. :     :+---+:     :     :     :     :     :
  7. :West :| A |: East: 3,1 : 4,1 : 5,1 : 6,1 :
  8. :     :+---+:     :     :     :     :     :
  9. ...........................................
  10. :     :     :     :     :     :     :     :
  11. : 0,2 :South: 2,2 : 3,2 : 4,2 : 5,2 : 6,2 :
  12. :     :     :     :     :     :     :     :
  13. ...........................................

因此，如果一个节点刚好占据一个单元格，由于一个单元格之后四个端口，因此这个节点只能由四个边进入或者发出。

只有四个边是非常大的局限，为了克服这个缺点，一个节点可以占据多个单元格；如果一个节点需要更多的单元格来保证有足够多的端口的时候，这个节点会自动增大。

你也可以显式指出一个节点应该占据多少行和多少列，下一章详细讨论这个话题。

Edge pieces

总共有是一个基本的代表边的单元格。

  1. .........................
  2. :     :  |  :  |  :     :
  3. :-----:  |  :--+--:     :
  4. :     :  |  :  |  :     :
  5. .........................
  6. :     :  |  :  |  :     :
  7. :  +--:  +--:--+  :--+  :
  8. :  |  :     :     :  |  :
  9. .........................
  10. :     :  |  :  |  :  |  :
  11. :     :  v  :  |  :  |  :
  12. :--+--:--+--:->+  :  +<-:
  13. :  ^  :     :  |  :  |  :
  14. :  |  :     :  |  :  |  :
  15. .........................

每一个Edge pieces都可以与起点（对于垂直的边不可见，水平边是空格）和终点（箭头）相结合。不是所有的组合都是有效的，但是布局器会充分利用空间来自动选择。

下面是一些水平边的可能组合：

  1. .........................
  2. :     :     :     :     :
  3. : --> :---> : ----: <---:
  4. :     :     :     :     :
  5. .........................
  6. :     :     :     :     :
  7. : <-> : --- :-----:     :
  8. :     :     :     :     :
  9. .........................

另外，还有四种自循环的Edge pieces，用来把一个边和它自己连接起来：

  1. .........................
  2. :     :     :     : | ^ :
  3. :  +- : -+  :     : +-+ :
  4. :  |  :  |  :     :     :
  5. :  +> : <+  : +-+ :     :
  6. :     :     : v | :     :
  7. .........................

这四个edge pieces每一个都有一个起点和终点，虽然他们可能由零个，一个或者两个箭头。

边标签

垂直，水平和自循环的边可以有一个标签，标签出现的位置由布局器自动选择。

边交叉

边与边之间可以交叉，但是布局器会尽量避免交叉的情况。哪些边可以交叉以及在哪里可以交叉都是由约束条件的，通常，一个边只能与另外一个没有标签的边正交。

看看下面这个强制的布局——实际情况并不会这样，除非你通过把上面一排节点的空格堵住来强制这么做。

  1. +----------+     +---------+     +----------+     +----------+
  2. | Koblenz  | <.- | Bonn    | --> | Ulm      | --> | Bautzen  |
  3. +----------+     +---------+     +----------+     +----------+
  4.   ^                :               |                |
  5.   |                :               +-----------+    |
  6.   |                v                           |    |
  7.   |              +---------+     +----------+  |    |
  8.   |              | Berlin  | --> | Kassel   |  |    |
  9.   |              +---------+     +----------+  |    |
  10.   |                ^                           |    |
  11.   +----------------+---------------------------+    |
  12.                    |                                |
  13.                    |                                |
  14.                    +--------------------------------+

根据最先创建的节点的不同，交叉的位置也有可能是这样：

  1. +----------+     +---------+     +----------+     +----------+
  2. | Koblenz  | <.- | Bonn    | --> | Ulm      | --> | Bautzen  |
  3. +----------+     +---------+     +----------+     +----------+
  4.   ^                :               |                |
  5.   |                :               +----------------+--+
  6.   |                v                                |  |
  7.   |              +---------+     +----------+       |  |
  8.   |              | Berlin  | --> | Kassel   |       |  |
  9.   |              +---------+     +----------+       |  |
  10.   |                ^                                |  |
  11.   |                +--------------------------------+  |
  12.   |                                                    |
  13.   |                                                    |
  14.   +----------------------------------------------------+

在上面的图中Ulm到Koblenz的边和Bautzen到Berlin的边发生了交叉；另外一个看起来更好的方式是穿过Bonn到Berlin的边，但是由于这个边非常短，因此并不会被交叉。

Edge Joints

当两个或者更多的边共享一个起点（不仅仅指同一个方向）的时候，它们可能在某个地方发生分叉；同样，如果两个或者更多的边共享一个终点，那么它们有可能在某个地方汇聚在一起。

  1.  [ Potsdam ], [ Mannheim ]
  2.    --> { end: back,0; }
  3.  [ Weimar ]
  4.    --> { start: front,0; } [ Finsterwalde ], [ Aachen ]

布局器 - 图2

  1. +----------+           +--------+          +--------------+
  2. | Mannheim | ------+-> | Weimar | -+-----> | Finsterwalde |
  3. +----------+       |   +--------+  |       +--------------+
  4.                    |               |
  5.                    |               |
  6.                    |               |
  7. +----------+       |               |       +--------------+
  8. | Potsdam  | ------+               +-----> |    Aachen    |
  9. +----------+                               +--------------+

请查阅hinting这一章获取更详细的内容。

多单元格的节点

默认情况下，一个节点就占据一个单元格；布局器会通过边来适当调整单元格的大小；也可以通过[size][2]属性来指定某个单元格最小的大小。

  1. ...........................................
  2. :     :     :     :     :     :     :     :
  3. : 0,0 :North:North: 3,0 : 4,0 : 5,0 : 6,0 :
  4. :     :     :     :     :     :     :     :
  5. ...........................................
  6. :     :+---------+:     :     :     :     :
  7. :West :|    A    |: East: 4,1 : 5,1 : 6,1 :
  8. :     :+---------+:     :     :     :     :
  9. ...........................................
  10. :     :     :     :     :     :     :     :
  11. : 0,2 :South:South: 3,2 : 4,2 : 5,2 : 6,2 :
  12. :     :     :     :     :     :     :     :
  13. ...........................................
  1. ...........................................
  2. :     :     :     :     :     :     :     :
  3. : 0,0 :North:North: 3,0 : 4,0 : 5,0 : 6,0 :
  4. :     :     :     :     :     :     :     :
  5. ...........................................
  6. :     :+---------+:     :     :     :     :
  7. :West :|         |: East: 4,1 : 5,1 : 6,1 :
  8. :     :|         |:     :     :     :     :
  9. .......|    A    |.........................
  10. :     :|         |:     :     :     :     :
  11. :West :|         |: East: 4,2 : 5,2 : 6,2 :
  12. :     :+---------+:     :     :     :     :
  13. ...........................................
  14. :     :     :     :     :     :     :     :
  15. : 0,3 :South:South: 3,3 : 4,3 : 5,3 : 6,3 :
  16. :     :     :     :     :     :     :     :
  17. ...........................................

路径寻找

要找出从一个节点到另外一个阶段的路径（有可能是同一个），布局器有两种方式进行：

  • 启发式的寻找（捷径），下面的情况会使用启发式算法寻径：
    • 如果一个节点可以通过直线到达的时候
    • 如果可以通过最多一个转折可以找到的时候
    • 是自循环的时候
  • 对于其他的所有情况，启发式算法无法寻找路径；会使用通用的A星搜索算法。

请查询A星搜索算法进一步了解。