摘要：由此觀之，實(shí)現(xiàn)?；鶊D的核心在于計(jì)算出以上的這些點(diǎn)坐標(biāo)。減少邊交叉當(dāng)數(shù)據(jù)量到一定程度的時(shí)候，?；鶊D中的邊會(huì)出現(xiàn)重疊現(xiàn)象，造成一定的視覺(jué)混亂。綜上，桑基圖是一個(gè)展現(xiàn)數(shù)據(jù)流非常好用的視圖，感興趣的同學(xué)可以自己實(shí)現(xiàn)一個(gè)試試。

原文地址：https://geekplux.com/2018/08/28/how-to-implement-sankey-diagram.html

Google 搜索桑基圖，可以搜到一大堆定義。簡(jiǎn)而言之，?；鶊D是一種數(shù)據(jù)流圖，展示了數(shù)據(jù)是如何從左到右流向最后的節(jié)點(diǎn)，每條邊代表一條數(shù)據(jù)流，寬度代表數(shù)據(jù)流的大小。桑基圖常用于流量分析，可以很清楚的看出數(shù)據(jù)是如何漸漸分流的。本文著重講解如何實(shí)現(xiàn)，理論方面的東西各位可以自行了解。

關(guān)鍵點(diǎn)有兩個(gè)：

?；鶊D要展現(xiàn)的數(shù)據(jù)流，算是圖（拓?fù)漕?、網(wǎng)絡(luò)型或關(guān)系型）數(shù)據(jù)的一種。實(shí)現(xiàn)一個(gè)數(shù)據(jù)可視化圖，最重要的就是拆解元素。而實(shí)現(xiàn)一個(gè)圖數(shù)據(jù)可視化，則最重要的是分清“節(jié)點(diǎn)”和“邊”。

拆解元素之后，最重要的便是坐標(biāo)的計(jì)算，這里包括點(diǎn)和邊的坐標(biāo)。而圖形中，任何的元素都可以看作是點(diǎn)連線而成，所以元素坐標(biāo)的計(jì)算實(shí)際上就成了點(diǎn)坐標(biāo)的計(jì)算。比如?；鶊D中，節(jié)點(diǎn)是一個(gè)矩形，那么只需計(jì)算兩個(gè)點(diǎn)（左上和右下）的坐標(biāo)(x0, y0),(x1, y1)便可確定；邊是一個(gè)帶形，需要計(jì)算四個(gè)端點(diǎn)才能確定，帶形的弧度則可由簡(jiǎn)單的三次貝塞爾曲線計(jì)算得來(lái)。

由此觀之，實(shí)現(xiàn)?；鶊D的核心在于計(jì)算出以上的這些點(diǎn)坐標(biāo)。其實(shí)實(shí)現(xiàn)任意一種可視化都是計(jì)算點(diǎn)的坐標(biāo)。

當(dāng)數(shù)據(jù)量到一定程度的時(shí)候， ?；鶊D中的邊會(huì)出現(xiàn)重疊現(xiàn)象，造成一定的視覺(jué)混亂。如何減少可以閱讀本文第二節(jié)。

經(jīng)典的圖數(shù)據(jù)結(jié)構(gòu)一般是鄰接矩陣和鄰接表，我們也可以自己設(shè)計(jì)。我在做拓?fù)鋽?shù)據(jù)可視化的時(shí)候，會(huì)先和后端或數(shù)據(jù)同學(xué)商定好我需要拿到的數(shù)據(jù)結(jié)構(gòu)，通常是這個(gè)樣子：

{
    nodes: [
        { foo: bar },
        { foo: baz },
        ...
    ],
    links: [
        { source: 0, target: 1, value: 100 },
        { source: 1, target: 2, value: 10 },
        ...
    ]
}

而我拿到之后要做的第一步就是先把 nodes 和 links 串聯(lián)起來(lái)，這里每個(gè) link 的 source 和 target 分別是 nodes 的下標(biāo)，當(dāng)然你也可以設(shè)置其他的引用（指針），總之通過(guò)引用講兩者串聯(lián)起來(lái)，變成：

{
    nodes: [
        {
            foo: bar,
            column: 0, // 節(jié)點(diǎn)所在第幾列
            row: 0, // 節(jié)點(diǎn)所在第幾行
            value: 100, // 節(jié)點(diǎn)數(shù)據(jù)流大小
            sourceLinks: [
                {
                    source: 0,
                    target: 1,
                    ...
                }
            ],
            targetLinks: [
                ...
            ]
        },
        ...
    ],
    links: [
        {
            source: 0,
            target: 1,
            value: 100,
            sourceNode: {
                foo: bar,
                column: 0,
                row: 0,
                ...
            },
            targetNode: {
                ...
            }
        },
        ...
    ]
}

這樣，對(duì)于某個(gè)節(jié)點(diǎn)來(lái)說(shuō)，可以直接用 O(1) 的時(shí)間復(fù)雜度訪問(wèn)到它的任意相鄰節(jié)點(diǎn)。

這里的計(jì)算方法可自己定，通常是取該節(jié)點(diǎn)入邊和出邊的數(shù)據(jù)流大小之和的最小值。

在?；鶊D的計(jì)算中，我們還需要進(jìn)行一個(gè)關(guān)鍵的計(jì)算——計(jì)算節(jié)點(diǎn)在?；鶊D中的第幾行第幾列。

第幾列的計(jì)算，即為節(jié)點(diǎn)在圖中的深度計(jì)算：

入度為 0 的節(jié)點(diǎn)深度為 0，在第一列

出度為 0 的節(jié)點(diǎn)深度最大，在最后一列

其余節(jié)點(diǎn)的深度為他相連源節(jié)點(diǎn)的最大深度加 1

第幾行的計(jì)算，涉及到排序的問(wèn)題，通常某一列中的節(jié)點(diǎn)都是按節(jié)點(diǎn)數(shù)據(jù)流大小，從大到小排序。

剛才我們說(shuō)過(guò)，坐標(biāo)計(jì)算可以分為兩部分：節(jié)點(diǎn)和邊。其中，邊的坐標(biāo)位置依賴于節(jié)點(diǎn)的坐標(biāo)，所以應(yīng)該先計(jì)算節(jié)點(diǎn)坐標(biāo)。

但在計(jì)算坐標(biāo)之前，首先要明確一個(gè)問(wèn)題：是否限定視圖的寬高。這個(gè)問(wèn)題引申出兩種節(jié)點(diǎn)坐標(biāo)的計(jì)算方式。

如果不限定寬高，那么節(jié)點(diǎn)坐標(biāo)的計(jì)算步驟很簡(jiǎn)單：

設(shè)置一個(gè)節(jié)點(diǎn)的寬度

設(shè)置節(jié)點(diǎn)的水平間距

從左至右，根據(jù)剛才計(jì)算出的節(jié)點(diǎn)所在第幾列，計(jì)算出節(jié)點(diǎn)的橫坐標(biāo)（x0, x1)，初始的 x0 為 0

設(shè)定一個(gè)比例尺函數(shù)（多大的數(shù)據(jù)流對(duì)應(yīng)屏幕上的多少像素，通常是首先設(shè)定一個(gè)節(jié)點(diǎn)最小高度和一個(gè)節(jié)點(diǎn)最大高度，然后找出所有節(jié)點(diǎn)數(shù)據(jù)流的最小和最大值，映射成一個(gè)定義域?yàn)楣?jié)點(diǎn)數(shù)據(jù)流大小，值域?yàn)楣?jié)點(diǎn)高度的函數(shù)）

通過(guò)比例尺計(jì)算出節(jié)點(diǎn)高度

設(shè)置一個(gè)節(jié)點(diǎn)垂直間距

從上至下，根據(jù)剛才計(jì)算出的節(jié)點(diǎn)所在第幾行，計(jì)算出節(jié)點(diǎn)的縱坐標(biāo) (y0, y1)，初始的 y0 為 0

大致是這個(gè)思路，橫坐標(biāo)的計(jì)算取決于兩個(gè)值，節(jié)點(diǎn)寬度和 節(jié)點(diǎn)水平間距；縱坐標(biāo)的計(jì)算取決于 節(jié)點(diǎn)的數(shù)據(jù)流大小 和 節(jié)點(diǎn)垂直間距。

具體的計(jì)算代碼，可根據(jù)你自己的數(shù)據(jù)結(jié)構(gòu)來(lái)調(diào)整。

如果限定寬高，那么計(jì)算步驟需要換個(gè)思路：

節(jié)點(diǎn)的寬度和節(jié)點(diǎn)的水平間距需要根據(jù)節(jié)點(diǎn)的列數(shù)和視圖寬度來(lái)計(jì)算，你可以自己手動(dòng)調(diào)整也可以設(shè)計(jì)個(gè)算法來(lái)算

從左只有，根據(jù)節(jié)點(diǎn)寬度和節(jié)點(diǎn)水平間距，計(jì)算出節(jié)點(diǎn)橫坐標(biāo)

設(shè)定一個(gè)比例尺函數(shù)，計(jì)算出節(jié)點(diǎn)的高度

設(shè)置一個(gè)節(jié)點(diǎn)垂直間距

通過(guò)高斯－賽德?tīng)柕℅auss–Seidel method）計(jì)算出縱坐標(biāo)（大致的思路是，先根據(jù)前兩步的數(shù)值算出一個(gè)初始節(jié)點(diǎn)坐標(biāo)，如果總體布局超出視圖的下界，則節(jié)點(diǎn)高度和節(jié)點(diǎn)垂直間距都按比例縮?。ㄈ?0.95），并同時(shí)上移 n 個(gè)像素，如果總體布局超出視圖上界，則節(jié)點(diǎn)高度和垂直間距都按比例縮小，并同時(shí)下移 n 個(gè)像素，直到總體的桑基圖布局適應(yīng)一開(kāi)始限定的視圖寬高）

這個(gè)思路是 d3-sankey 的實(shí)現(xiàn)思路。如果你有限定視圖寬高的需求，那么可以直接使用 d3-sankey。

只要確定了節(jié)點(diǎn)坐標(biāo)，邊的坐標(biāo)可以根據(jù)它源節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn)的坐標(biāo)來(lái)算出：

對(duì)于一個(gè)節(jié)點(diǎn)，將它的出邊和入邊進(jìn)行排序（排序方法通常是根據(jù)相連節(jié)點(diǎn)在第幾行從上到下排，也可以通過(guò)一些其他排序方法減少邊的交叉，具體在第二節(jié)介紹）

計(jì)算每個(gè)節(jié)點(diǎn)中單位數(shù)據(jù)流占節(jié)點(diǎn)高度的比例

根據(jù)出邊入邊的數(shù)據(jù)流大小，乘上一步計(jì)算出的比例，則可得到每條邊左右兩邊的高度

從上到下，計(jì)算每條邊的縱坐標(biāo)

每條邊四個(gè)端點(diǎn)的橫坐標(biāo)分別對(duì)應(yīng)源節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn)的橫坐標(biāo)

以上操作可以通過(guò)遍歷每個(gè) node 的 sourceLinks 和 targetLinks 來(lái)計(jì)算。得到邊的四個(gè)端點(diǎn)以后，就可以算出三次貝塞爾曲線的控制點(diǎn)了：

通常要減少邊的交叉，可以采用下面兩種方法：

均值排序

sugiyama 算法

均值排序這個(gè)名字是我自己起的。。不過(guò)這個(gè)方法很實(shí)用有效。

對(duì)于每個(gè)源節(jié)點(diǎn)來(lái)說(shuō)，都有相連的目標(biāo)節(jié)點(diǎn)。這里的“均值”指的是所有相連目標(biāo)節(jié)點(diǎn)所在行數(shù)的平均值（所有目標(biāo)節(jié)點(diǎn)的行數(shù)相加，除以目標(biāo)節(jié)點(diǎn)個(gè)數(shù)），這個(gè)平均值可以大致描述該節(jié)點(diǎn)每個(gè)出邊的位置。每條出邊都有這樣一個(gè)值，這個(gè)值越小，則說(shuō)明該出邊要連接的目標(biāo)節(jié)點(diǎn)的位置越靠上，反之越靠下。所以可根據(jù)這個(gè)值，從小到大排出出邊在該節(jié)點(diǎn)上從上到下的位置。

我參與的 UBA (User Behavior Analytics 內(nèi)部項(xiàng)目) 項(xiàng)目中，正好用到了?；鶊D。除了上述的圖形繪制之外，主要復(fù)雜的是交互。

如圖所示，除了基本的 hover 交互之外，項(xiàng)目中主要還有

minimap 拖拽和刷選

主視圖的拖拽和縮放

左下角的過(guò)濾器

點(diǎn)擊交互，高亮只經(jīng)過(guò)選中節(jié)點(diǎn)的路徑，并且邊上高亮的部分由最后一個(gè)選中節(jié)點(diǎn)懈怠的數(shù)據(jù)流值確定，其余部分半透明

整個(gè)?；鶊D實(shí)現(xiàn)下來(lái)發(fā)現(xiàn)繪制只是一些計(jì)算，交互才是更難抽象和處理的部分。

綜上，?；鶊D是一個(gè) 展現(xiàn)數(shù)據(jù)流非常好用的視圖，感興趣的同學(xué)可以自己實(shí)現(xiàn)一個(gè)試試。除了我文章中這些基本的桑基圖布局，你還可以試試其他變種，另外交互方面也可以突破剛才我提到的那些，比如我之前實(shí)現(xiàn)過(guò)點(diǎn)擊節(jié)點(diǎn)進(jìn)行折疊/展開(kāi)的交互?？傮w來(lái)說(shuō)可視化還是一個(gè)比較有意思的方向。

本作品采用知識(shí)共享 署名-非商業(yè)性使用-禁止演繹 4.0 國(guó)際 許可協(xié)議進(jìn)行許可。