Sugiyama 布局算法

我们一直在使用层次图...没错，我确实经常用。无论是老板要的公司员工组织架构图，还是我项目的 UML 图，我都是这种布局的热心用户，因为它能清晰地展示关系和/或流程（我用正交图来画电路图...但那是另一篇博文了）。所以想象一下，当我意识到层次算法实际上是计算机科学中一个叫做图绘制的话题的一部分时，我有多震惊。总之，我花了很多时间研究和开发 Java 代码来实现一种常见的层次算法——Sugiyama 布局算法，并且我意识到以下 3 件事：

Sugiyama 布局算法实际上是一组算法的集合。 组成 Sugiyama 算法的各种算法多年来经过了评审和更新。
集合论是理解 Sugiyama 算法的关键。 似乎很多作者（包括 Sugiyama 本人...）都使用集合论符号来表示 Sugiyama 中的各种算法。我已经两年没用过集合论了，你能想象我在集合论符号方面重新复习时的压力吗...其实也没那么糟...只是拖慢了我一点进度。
很多人在理解 Sugiyama 布局算法方面有困难，所以我希望这篇博文能让大家轻松迈出快速理解 Sugiyama 布局算法的第一步。

在这篇博文中，我将尝试揭开被称为 Sugiyama 的层次布局算法的神秘面纱，让使用高级文献的人更容易理解 Sugiyama 算法到底是什么。

1、什么是 Sugiyama 布局算法？

Sugiyama 布局算法实际上是由 Sugiyama 等人在 80 年代末定义的一组算法。组成 Sugiyama 布局算法的这组算法背后的思想是实现节点（有时称为顶点）和边的自动层次化布局。如果想象一下带有继承类的 UML 图表，那么节点（或顶点）就是带有各种属性和方法的类图，而边就是连接各种顶点/节点的线。为了让这篇博文更容易理解，我将尽可能避免使用集合论。很简单...

虽然人类创建一个视觉上吸引人的层次图很容易，但让计算机软件自动完成这件事就是另一回事了，而这正是 Sugiyama 算法帮助完成的任务。

Sugiyama 布局算法定义了哪些条件来定义视觉上吸引人的层次图应该满足：

向上指的边的数量应该最小化（层次性）
顶点应该被放置在层中，并且在这些层中尽可能均匀分布（均匀分布）
边跨越的层数应该尽可能最小化（边长度最小化）
边交叉应该尽可能最小化（边交叉最小化）
同构图应该被相同地绘制（相同绘制）
在每一层上，顶点之间应该用最小可能的距离分隔（最小间隔）
相邻层中的相邻顶点应该尽可能靠近放置（紧密性）
每个顶点应该放置在相邻顶点的重心位置（平衡性）
弯折应该最小化，边应该尽可能直（线性度）

如果上面的规则现在看起来不太明白，别担心。随着你阅读博文，"重心"或"同构图"这些术语的含义会变得清晰。

2、 Sugiyama 算法到底是什么

你会注意到，上面我只提到了 Sugiyama 算法要做什么，即自动以层次化方式布局节点...但没有明确解释这是如何发生的！嗯，这就是本节的内容...在我深入使用源代码提供更详细解释之前，先解释 Sugiyama 算法是如何工作的。

Sugiyama 算法将图中的顶点（这个图恰好必须是无环有向图，即有向图（边有箭头或方向）并且没有边形成循环）布局分为四个阶段：

使图无环（即移除图中由边形成的任何循环）。下面会详细介绍如何完成
将顶点分配到图中的层
确定每层中顶点的顺序，以尽可能减少边交叉
确定每层中重新排序后顶点的位置，以增强平衡性和紧密性。

四个神秘的阶段（或算法）...这就是组成 Sugiyama 的全部！

显然，你需要更多地理解上面四个步骤中的每一个，才能清晰地想象 Sugiyama 的内部结构。我将使用 Java 源代码来详细解释 Sugiyama 的四个步骤及其工作原理。

3、Sugiyama 是如何工作的？

在继续之前...

你可以自由地按照自己的方式在软件中编码节点/顶点和边。我会解释我使用的方式（我将在整篇博文中使用的模型），但一旦下面的阶段清晰了，你可以自由地将其调整为你的源代码。

包含所有节点和边的图由实例表示：

Graph graph = graphFrame.getGraph();

边通过以下代码从所有边的数组列表中获取：

Edge e = (Edge)graphEdges.get(i); // i 定义当前检索边的索引/计数器

顶点通过以下代码获取：

Node n = (Node) graphNodes.get(t) // t 是当前检索节点的计数器

3.1 使图无环

我会做个坏人，让你自己去弄清楚这个。原因如下。当我在实现 Sugiyama 代码时，我知道软件的使用场景...是布局 UML 图，如果你想一想，你会发现很难创建循环，但我承诺以后会回来补充如何完成的代码。

3.2 将顶点分配到层

这一步实际上包含两个部分：将顶点分配到图中的层，以及插入虚拟顶点。虚拟顶点...那是什么？好吧，事情是这样的。图中的边（根据 Sugiyama 算法）应该只有 1 的跨度，即它应该连接相邻层中的两个顶点。然而，一个顶点可能在第 2 层，却连接到第 4 层的顶点；这样边的跨度就是 2。因此这一步不仅涉及将顶点分配到层，还包括向跨度大于 1 的边插入虚拟顶点。那么问题来了...使用什么标准来将顶点/节点分配到层？

首先选择根节点。这些是有边流出但没有边流入的节点。然后从每个根节点递归地遍历图中的所有节点，递增图应该具有的层级，并将此层级分配给图。如果遇到已分配层级的节点/顶点，检查建议分配给它的层级是否小于当前层级。如果是这种情况，则分配建议的层级（即大于初始节点层级的层级）

private Node getNodeChildren(Node n, ArrayList graphEdges, Integer startCounter)
{
    ArrayList endNodes = new ArrayList();
    if(n.getLayer()==-1||startCounter > n.getLayer())
    {
       n.setLayer(startCounter);
    }
    
    for(int i = 0 ; i < graphEdges.size(); i++)
    {
        Edge e = (Edge) graphEdges.get(i);
        if(e.getStart() == n)
        {
            endNodes.add(e.getEnd());
        }
    }
    if(endNodes.size() > 0)
    {
        startCounter += 1;
        for(int k = 0 ; k< endNodes.size(); k++)
        {                
            getNodeChildren((Node) endNodes.get(k),graphEdges, startCounter);
        }
    }
    return n;
}

一旦所有节点都分配了层级（或层号），接下来就是下一步；当边的跨度大于 1 时添加虚拟顶点。为此，这里有一个简单的方法来获取所有边的最大跨度：

public int getMaxSpan(ArrayList edges)
{
    int maxSpan = 0;
    for(int i=0;i<edges.size();i++)
    {
        Edge e = (Edge)edges.get(i);
        int startNodeLayer = e.getStart().getLayer();
        int endNodeLayer = e.getEnd().getLayer();
        maxSpan = ((endNodeLayer-startNodeLayer)>maxSpan)?(endNodeLayer-startNodeLayer):maxSpan;
    }
    return maxSpan;
}

一旦确定了所有边的跨度，接下来就是有趣的部分，添加虚拟顶点（和边）：

public void insertDummyVerticesAndEdges(Edge g)
{
    Node startNode = g.getStart();
    Node endNode = g.getEnd();
    int span = endNode.getLayer()-startNode.getLayer();
    if(span>1)
    {
        double xIncrement = (endNode.getBounds().getCenterX()
                                    - startNode.getBounds().getCenterX())/span;
        double yIncrement = (endNode.getBounds().getCenterY()
                                    - startNode.getBounds().getCenterY())/span ;
        
        int noDummyVertices = span -1;
        Node previousNode = startNode;
        
        for(int i = 0 , currLayer = startNode.getLayer() + 1
                ; i < noDummyVertices
                ; i++ , currLayer++)
        {
            PointNode d = new PointNode();
            d.setLayer(currLayer);
            d.setDummy(); 

            final double xCoord = previousNode.getBounds().getCenterX()
                                + xIncrement;
            final double yCoord = previousNode.getBounds().getCenterY()
                                + yIncrement;

            graph.add(d, new Point2D.Double(xCoord,yCoord));

            ClassRelationshipEdge r = new ClassRelationshipEdge();
            graph.connect(r, previousNode, d);

            if(i==noDummyVertices-1)
            {
                ClassRelationshipEdge lastEdge = new ClassRelationshipEdge();
                graph.connect(lastEdge, d, endNode);
            }

            previousNode = d;
        }
        graph.removeEdge(g);
    }
    else
    {
        return;
    }
}

3.3 对顶点排序以减少边交叉数量

现在所有节点都已分配到特定层，虚拟节点（以及扩展的虚拟边）也已添加。然而，每层中的顶点可能以某种方式排序，导致连接相邻层顶点（包括虚拟节点）的许多边大量交叉。这是完全不可接受的，从下面的美学考虑列表中可以看出，减少边交叉是算法的一个关键特性。

那么我们如何重新排序每层中的顶点以确保边交叉尽可能减少呢？

相邻层中顶点的边交叉数量是通过获取相邻层中边的邻接矩阵、计算这些邻接矩阵的重心，并重新排序节点使节点的重心从最小到最大排列来获得的。一旦发生重新排序，就重新计算重心并重新排序，直到获得最少的边交叉数量。

原文链接: The Sugiyama Layout Algorithm (Hierarchical Algorithm) for dummies

汇智网翻译整理，转载请标明出处