圖的抽象:概念與模型的構建

語言: CN / TW / HK

最近的業餘時間裏,一直在研究圖相關的領域,順便構建出 feakin 圖形引擎。在研究了 Mermaid、Cytoscape、Drawio/MxGraph/MaxGraph、Excalidraw 等圖形庫之後,大概寫了兩個 PoC(概念驗證):

  • 數據的處理。即將文本轉換為可渲染的數據模型。即結合語法解析、圖算法來對數據進行處理。
  • 圖形的渲染。即基於 Konva.js 的 Canvas 方式來渲染圖形。

在這個過程中,因為研究時間比較分散,一些概念相對比較模糊。所以,便想抽空重新梳理一下其中的思路,方便於後續繼續研究。

什麼是圖,什麼是圖表?

開始之前,我們需要定義一下什麼是圖(Graph),以及本文所指的圖形是什麼?我們這裏所指的是圖是指:

圖是計算機科學的一個大主題,可用於抽象表示交通運輸系統、人際交往網絡和電信網絡等。對於訓練有素的程序員而言,能夠用一種形式來對不同的結構建模是強大的力量之源。 —— Steven S. Skiena《算法設計指南》

簡單來説,我們這裏所指的圖是用來表示網絡關係的,通常會採用的是節點(Node)來表示實體,使用線條(Edge)來表示關係。諸如於,我們繪製的流程圖,便是這裏的圖;而我們通常所見的曲線圖等,可以劃到圖表裏。當然了,要準確區分兩者的定義是一件非常困難的事,諸如於 Echarts、D3.js 這一類的圖形庫, 可以同時表示兩種圖和圖表。

也因此,我們這裏説裏的圖,就是提網絡及其關係。

圖的模型與概念

作為一個圖領域的新手,在當前的版本里,我構建的模型來源於不同的圖形庫的實現。而正是這種參考了不同的圖形庫,使得我對於什麼是正確的概念充滿了迷惑性。比如,什麼是 Geometry(幾何),如果從 維基百科 定義上來説,它主要研究形狀(shape)、大小(size)、圖形的相對位置(position)、距離(distance)等 空間 區域 關係以及空間形式的度量。

而在 maxGraph(MxGraph 的 TypeScript 版本里),Geometry 下包含了節點(Node)和線條( Edge),在這時可以認為是他們的子類。

尋找基礎的概念:Node 與 Edge

現在,讓我們嘗試回到標準的定義之下,如果我們基於標準的 Wikimedia 的定義的話,那麼 Graph 是這麼呈現的:

In mathematics, and more specifically in graph theory, a graph is a structure amounting to a set of objects in which some pairs of the objects are in some sense "related". The objects correspond to mathematical abstractions called vertices (also called nodes or points ) and each of the related pairs of vertices is called an edge (also called link or line ). Typically, a graph is depicted in diagrammatic form as a set of dots or circles for the vertices, joined by lines or curves for the edges. Graphs are one of the objects of study in discrete mathematics.

基於它,我們可以構建一個構建出一個基本的圖的模型:

  • Graph 是一個包含了一系列對象的數據結對,這些對象由表示關係的 Edge(線條)和表示節點的 Node(節點,或者 Vertex,即頂點) 組成。
  • Node 可以用 Dot (點)和 Circle (圓圈)的形狀來表示。
  • Edge 可以用 Line (線)和 Curve(曲線)來表示。

這裏的 Dot 和 Circle 可以用 Shape 來進行抽象,而 Line 和 Curve 在實例畫之後,就是一系列的 Points (點)。

然後,再讓我們打開 Vertex 的定義:

In a diagram of a graph, a vertex is usually represented by a circle with a label, and an edge is represented by a line or arrow extending from one vertex to another.

在這裏,我們又進一步展開了 Node 和 Edge 的定義:

  • Node 通常是帶有標籤的,這裏的標籤通常是指文本。
  • Edge 除了 Line ,還可以帶有箭頭(arrow),即它是有方向性的。

而如果我們定義的是 Node,那麼參考 Node 的定義:

A node is a basic unit of a data structure, such as a linked list or tree data structure. Nodes contain data and also may link to other nodes. Links between nodes are often implemented by pointers. It is a computer connected to the internet that participates in the peer to peer network.

進一步地,因為它是一個樹型結構,所以我們需要強化一個 Node 的定義:

  • Node 包含 children、parent、depth、degree 等屬性。

綜上所述,一個 Node 會包含一系列的屬性,一個包含大量屬性的模型,顯然是不利於我們建模的,我們應該怎麼辦?

引入概念降低認識負載: Geometry

為了更好地描述這些屬性,我們就可以考慮引入 Geometry,通過 組合的方式 解決這個問題。

It is concerned with properties of space such as the distance, shape, size, and relative position of figures.

對於距離、大小、相對位置,我們比較好理解,而 Shape(形狀) 同樣也是一個非常有意思的概念。

A shape or figure is a graphical representation of an object or its external boundary, outline, or external surface, as opposed to other properties such as color, texture, or material type.

所以 Shape 也需要再次展示,它包含了一些有意思的屬性。在我們使用 SVG 或者 Canvas 表示的時候,分別可以對應於:

  • Stroke 。如 Width 等。
  • Fill 。如 透明度 (Opaciyy)等。
  • Scale。縮放

而從定義上,我們會發現顏色、材質等屬性,似乎不應該放在 Shape 中。那麼,我們是否需要一些額外的概念來放置它們呢?或者是直接扔到 Node 中,採用 Properties ,諸如於 Graph Database 的做法:

Propertiesare information associated to nodes.

在這時,就會有 Node Properties 和 Edge Properties 。在構建了基本的模型之後,就可以將模型可視化出來 。

數據與模型的渲染:Drawing

當我們拿到了模型及其數據之後,就可以對其進行渲染了,而在 Wiki 中 Rendering 講述的是 3D 圖形的渲染,對應於 2D 則是 Graph Drawing 。對於繪製來説,我們關注於兩點:

  • Layout Strategies。佈局策略,即各類不同的佈局方式。基於佈局方式選擇不同的算法。
  • Renderer。如基於 SVG、Canvas 等的 Renderer。

Layout 策略

關於圖算法相關的內容,已經有蠻多的內容可以參考了,也有一系列的代碼庫可以使用。諸如於:

  • Mermaid 採用的是 dagre.js,並使用 dagre-d3 + D3 進行渲染。
  • D3.js 也包含了一系列常用的 Layout 策略,如 Force-Layout、Hierarchy-Layout 等。
  • Cytoscape.js 也內置了 Breadthfirst、Circle、CoSE 等佈局策略,也支持通過擴展的方式來進行。

而隨着 AI 的流行,人們也開始在上面探索機器學習的可能性。

Renderer

對於 Renderer 來説,如果我們不加入 Animation 的話,並不存在太複雜的點 —— 只是將數據拿過來,然後在渲染介質上表示出來即可。而如果加上動畫的話,就又是一個有意思的問題了 —— 等以後再研究了。

小結

本文主要是針對於自己編碼過程中的理解,重新對建模進行了思考。如果你有相關的經驗,歡迎留言\~。

相關的參考內容:

  • 《圖數據庫》
  • 《數據分析之圖算法》