（有向）圖是由節點以箭頭（邊）連接而成的集合。節點和邊都可以帶有資料。以下是幾個圖的範例：

圖在軟體工程中無所不在：

1. 套件的相依關係會形成有向圖，模組的 import 也是如此。
2. 網際網路就是由網頁之間的連結所構成的圖。
3. 模型檢查器（model checker）會透過探索所有可能組態的「狀態空間」來分析軟體。節點代表狀態，邊則是狀態之間合法的轉換。
4. 關聯式資料庫就是一種圖，其中節點是資料記錄，邊是外部鍵（foreign key）。
5. 圖是鏈結串列、二元樹和雜湊表（hash table）的一般化。¹

圖在商業邏輯中也隨處可見。附有參考文獻的白皮書會形成引用的圖；交通網路是路線構成的圖；社群網路則是人際連結構成的圖。只要在軟體開發領域待得夠久，總會在某個地方碰到圖。

我到處都能看到圖，也常用圖來分析各種系統。但同時，我又很怕真的在程式碼裡使用圖。幾乎沒有任何主流語言對圖有完整的支援。沒有任何語言把它當作內建型別，只有極少數語言在標準函式庫中提供圖，很多語言的生態系甚至連堪用的第三方函式庫都沒有。多數時候，我都得從頭自己刻圖。軟體工程師實際上能用到圖的機會，和程式語言生態系對圖的支援程度之間，存在著巨大的落差。那些圖的型別到底都去哪了？

隨著工作中遇到越來越多圖，這個問題對我來說也越來越有意思。所以去年底我終於決定尋找答案。我在電子報上發了一則徵求啟事，希望具備相關專業的人——圖演算法的發明者、語言委員會的成員、圖函式庫的維護者——能與我聯繫。我原本預期會訪談十幾個人，但最後只談了四位就夠了：

1. Zayenz：Gecode 約束求解器的前核心開發者，自稱「各種圖演算法都實作過」
2. Bradford：Nosey Parker 安全掃描函式庫的作者，並發明了數種新的圖演算法
3. Nicole：前圖資料庫工程師
4. Kelly：NetworkX 這個 Python 圖函式庫的維護者，同時也是編譯器開發者。

這四個人給出了相似的答案後，我就停止訪談，開始動筆。

原因

設計上的選擇太多了

到目前為止我談的都是有向圖。另外還有無向圖，其中的邊沒有方向。不論是有向還是無向圖，又都可以是簡單圖——任兩個節點之間最多只有一條邊——或是多重圖——兩個節點之間可以有多條邊。而上述每一種類型，又還可以衍生出超圖（hypergraph，一條邊可以連接三個以上的節點）和超級圖（ubergraph，邊可以指向其他邊）。針對每一種可能的變體，你還得做更多抉擇：是要幫邊加上 id，還是只幫節點加？節點可以存放什麼資料，邊又可以存放什麼？對一個函式庫來說，這實在有太多決定要做！

但等等，這些區分真的有那麼重要嗎？簡單圖不過是多重圖的退化情況，而無向邊也可以無損地轉換成兩條有向邊。一個語言大可只提供有向超級多重超圖（directed hyperubermultigraph），然後讓使用者自行限縮使用方式就好。

這樣做有兩個問題。首先，它會改變介面，例如某些操作究竟該回傳單一值還是清單。其次，如我稍後會談到的，圖演算法的效能是個非常重要的考量，而這些特殊情況真的很重要。Kelly 舉了最大權重匹配（maximum weight matching）的例子。如果你知道自己的圖是「二分圖」（bipartite），就可以用一種特別快的演算法來找出匹配；但對於其他圖，就得使用較慢、更通用的演算法。

這又回到了「演算法分派問題」。給定一個問題 P、一張圖 G，以及用來解 P 的演算法 A、B、C……你該跑哪一個？如果我們不知道 G 是不是二分圖，而演算法 C 只適用於二分圖，那我們願意花多少時間來判斷 G 到底是不是二分圖？ — Kelly

理想的圖函式庫應該要支援許多不同種類的圖。但那會排擠掉支援使用者真正想用圖來做的事情的時間。圖演算法出了名的難以正確實作。在這篇文章中，Python 的發明者自己實作了一個 find_shortest_path 演算法，結果前後修正了五次才正確！

我比對過的每一份 pagerank 實作都是錯的。 — Nicole

那麼，函式庫到底該內建哪些演算法呢？Kelly 告訴我：「大家想拿圖來做的事情多到荒謬。」這和我的經驗吻合，也和我所有受訪者的經驗一致。圖有時候似乎太過強大，其可能性之多超乎我的理解。Kelly 說：「問題在於，」 「你要在哪裡劃下那條線？」

對 NetworkX 而言，「那條線」大約是 500 種不同的圖演算法，光是這些演算法本身就佔了將近 60,000 行程式碼。相比之下，整個 Python 標準函式庫由 300 個套件組成，總共也才不到 600,000 行。²

有鑑於此，標準函式庫裡看不到圖也就不足為奇了。語言的維護者必須決定要支援哪幾種圖、要針對哪些拓撲做特化、又要納入哪些演算法。把這些維護工作推給第三方是很合理的。這本來就是語言發展的主流趨勢；就連以「內建電池」（batteries included）著稱的 Python，也正在移除 20 顆電池。

第三方則可以在圖的設計方式和要收錄哪些演算法上做出有主見的抉擇。但接著他們又會面臨下一個問題：一旦有了圖的介面，要怎麼在內部表示它？

實作上的選擇也太多了

假設我們只支援最陽春的簡單有向圖：節點有識別身份，邊沒有，兩者都不帶任何附加資料。我們該如何編碼這樣一張圖？

以下是程式語言在內部儲存它的四種可能方式：

1. 邊清單（Edge list）：[[a, b], [b, c], [c, a], [c, b]]
2. 鄰接清單（Adjacency list）：[[b], [c], [a, b]]
3. 鄰接矩陣（Adjacency matrix）：[0 1 0; 0 0 1; 1 1 0]
4. 由三個互相參照的 struct 組成的集合

不同的圖操作在不同的表示法上有不同的效能特性。假設有一張有 100 個節點、200 條邊的有向圖。如果用鄰接矩陣來表示，就需要一個 100×100 的矩陣，裡面有 200 個 1 和 9,800 個 0。如果改用邊清單，則只需要 200 對節點。視你使用的程式語言和最佳化程度而定，兩者的記憶體差距可能達到 20 倍以上。

現在再想像一張有 100 個節點、8,000 條邊的圖，要判斷節點 0 和節點 93 之間是否存在一條邊。在矩陣表示法中，只要用 graph[0][93] 做一次 O(1) 的查詢就行。但在邊清單表示法中，就得對全部 8,000 條邊做一次 O(|edge|) 的遍歷。³

只有少量邊的圖是稀疏的，而幾乎包含所有可能邊的圖則是稠密的。同一個程式可能需要在兩種圖拓撲上執行上述兩種操作：如果你正從外部資料建構圖，一開始可能是稀疏圖，之後卻可能變得稠密。對於圖的內部表示法，根本沒有「最佳選項」。

而這些麻煩還只是針對最陽春的有向圖！那要怎麼實作節點資料？邊資料？不同類型的節點和邊？大多數第三方函式庫大致可分為兩類：

1. 提供單一、功能豐富的資料型別，涵蓋所有使用情境，但犧牲效率。NetworkX 就是把圖存成 dict of dicts of dicts，讓節點和邊都能帶有任意資料。⁴

2. 為每種表示法提供各自獨立的圖型別，並仰賴使用者將節點和邊的資料另外與圖型別分開儲存。

第二類的一個例子是 Petgraph，這是 Rust 最受歡迎的圖函式庫。Petgraph 針對不同使用情境提供了 graph、graphmap 和 matrix_graph。Bradford 在 Nosey Parker 中就用了 Petgraph，這是一套會掃描整個 git 儲存庫歷史紀錄以尋找機敏資訊的安全工具。他的效能測試圖是 CPython，擁有 25 萬次 commit 和 130 萬個物件，但每個 commit 節點只有少數幾條邊。他選擇了鄰接清單。

支援多種表示法的缺點很明顯：要新增演算法就得做更多工。如果你為每種圖表示法各寫一份演算法版本，維護負擔就會變成三、四倍。如果改為寫一個跨多型型別的通用抽象層，函式庫的效能又會變差。一位受訪的程式設計師估計，手刻的圖演算法可以比通用演算法快上 20 倍甚至更多。

而這就牽涉到每一位受訪者共同抱怨的最大痛點。

效能太重要了

「通用的」圖實作往往不夠用。— Bradford

這才是最關鍵的一點。

有非常多圖演算法是 NP-complete 甚至更難的。⁵ 雖然 NP-complete 的問題在大規模下常常還是可解的，但圖本身就可能是極其龐大的問題。表示法的選擇對執行速度有很大的影響，演算法實作的細節也是如此。

我訪談的每個人都有這方面的故事。在 Nosey Parker 中，Bradford 需要為每一次 commit 重建檔案系統的快照，這意味著要遍歷物件圖。Petgraph 提供的四種圖遍歷器沒有一個能擴展到他的使用情境。相反地，他必須臨時設計出一套「半原創的」圖遍歷演算法，將記憶體用量降低了上千倍。

我用 [petgraph] 很快就做出了一個可行的概念驗證，但接著……這就是那種效能限制終究會碰上現實的案例。— Bradford

Zayenz 則提出了另一個問題：如果圖大到根本無法處理怎麼辦？他舉了尋找 15 拼圖（15 puzzle）解法的例子。這是透過在狀態空間上執行 A* 搜尋來完成的。而那個狀態空間擁有超過 20 兆個狀態。

如果你把所有節點都產生出來，就已經輸了。— Zayenz

Zayenz 曾督導一項在 Gecode 約束求解器中加入圖的研究計畫。他們最終發現，通用的圖型別根本無法與針對問題量身挑選的表示法相抗衡。

就連完全圍繞著執行複雜圖演算法而設計的圖資料庫，也為這個問題所苦。圖資料庫工程師 Nicole 跟我談了一些即使是基本圖操作在最佳化上的挑戰。

如果你在做遍歷，要嘛得限制深度，不然就得接受會走訪整張圖。當你做深度搜尋，像是「從這裡出發走三步，看看是否存在路徑」時，就等於承諾要存取相當大量的資料。— Nicole

離開那份工作後，她轉任圖查詢效能顧問。這通常意味著要把系統從圖資料庫遷移出去。她跟我分享了其中一個專案：為了加速圖查詢，她保留了一項計算不動，其餘的則全部重寫為 MapReduce 程序。她說：「那樣雖然難懂得多，」 「但真的能在隔天早上之前跑完。」

這一切都意味著，如果你有圖的問題想要解決，就必須對資料表示法和演算法的細節有很大的掌控度。你根本無法承擔浪費效能的代價。

大家的結論一致

所以，我們之所以沒有普及的圖支援，原因在於：

• 圖的種類太多了
• 每一種圖的表示方式也太多了
• 圖演算法的種類也太多了
• 圖演算法的效能對圖的表示法和實作細節非常敏感
• 人們會在非常大的圖上執行非常昂貴的演算法。

這解釋了為何語言不在標準函式庫中支援圖：太多設計決策、太多取捨、以及太重的維護負擔。這也解釋了為何程式設計師可能會避開第三方的圖函式庫，因為它們不是太受限就是太慢。也解釋了為何程式設計師除非在極端情況下，否則可能根本不想用圖來思考問題：處理圖實在太困難了。

自從開始這項研究以來，我在工作中又碰到了幾個新的圖問題。我依然喜歡把系統當作圖來分析，也依然害怕實際去實作它們。但現在我明白為什麼其他人也都對它們望而生畏了。感謝你的閱讀！

感謝 Predrag Gruevski 協助研究，感謝 Lars Hupel、Predrag Gruevski、Dan Luu 以及 Marianne Bellotti 提供的回饋，也感謝所有願意接受訪談的人。如果你喜歡這篇文章，歡迎加入我的電子報！我每週都會在那裡發表新的文章。

我為企業提供形式化方法（formal methods）培訓，協助讓軟體開發更快、更便宜、更安全。歡迎在這裡了解更多。

附錄：具備圖型別的語言

圖查詢語言

圖查詢語言（GQLs）⁶之於圖資料庫，就如同 SQL 之於關聯式資料庫。目前還沒有被廣泛使用的標準，但其中最熱門的兩個是 SPARQL（用於查詢 RDF triples）和 Neo4j 的 Cypher。諷刺的是，GraphQL 並不是一種圖查詢語言，而是因其與 Facebook Graph Search 的關聯而得名。我認為圖資料庫本身與程式語言中的圖大多是不同的東西，但它們的查詢語言確實展示了圖在程式語言中可以如何運作。

所有 GQL 和 SQL 最主要的差異在於，「join」（關聯）是一級實體。想像一個包含電影與人物的資料集，其中人物會演出、導演或製作電影。在 SQL 中，你會把每種關係都實作成多對多（many-to-many）的資料表，這讓查詢「誰演了電影 X」變得容易，卻讓查詢「誰在電影 Y 中擔任過任何角色、又是擔任什麼角色」變得很困難。在 SPARQL 中，關係就只是邊，讓同樣的查詢變得輕而易舉。

PREFIX mv: <your_movie_ontology_URL>
SELECT ?person ?role
WHERE {
    ?person ?role mv:casablanca.
}

Cypher 也有類似的結構。GQL 還能操作邊：反轉邊、將邊組合在一起、取遞移閉包（transitive closure）等等。如果我們想找出所有與 Kevin Bacon 有不同程度關聯的演員，可以這樣寫

PREFIX mv: <your_movie_ontology_URL>
SELECT ?a
WHERE {
    mv:kbacon (:acted_in/^:acted_in)+ ?a.
    # a/b = join two lookups
    # ^a = reverse a
    # a+ = transitive closure
}

SPARQL 無法給出路徑的長度，也無法在路徑上進行運算，例如收集串連兩位演員的電影鏈。支援這類功能的 GQL 則要複雜得多。

我研究 GQL 後得到的主要心得是，一個支援圖的程式語言需要提供一組有用的遍歷原語。有趣的是，形式化規格語言 Alloy 在其「關聯」（relation）資料型別上就具備所有這些原語。正因如此，我發現用 Alloy 處理圖的表示比在正規的程式語言中容易得多。話雖如此，這些操作都是針對帶有標籤的邊，未必適用於其他圖的表示法。

標準函式庫中內建圖的主流語言

Python 在 2020 年新增了 graphlib。根據這裡的討論，原因是拓撲排序（topological sorting）是「基礎演算法」，而且它對「純 Python 實作的 MRO（Method Resolution Order，方法解析順序）邏輯」會很有用。Graphlib 除了 TopologicalSorter 之外沒有其他方法，而且它只接受以節點字典（node dict）表示的圖。特別的是，節點字典的方向是反過來的：圖 a -> b 會被表示為 {b: [a]}。

截至 2023 年，CPython 沒有任何地方用到 graphlib，在 GitHub 上也只有不到 900 個檔案有引用它。相比之下，另一個同樣在 2020 年加入的套件 zoneinfo 出現了超過 6,000 個檔案，而 def topological_sort( 這個詞則出現了 4,000 次。我猜其中很多都是在 2020 年之前的程式碼。粗略瀏覽後發現，所有這些自行實作的拓撲排序所接受的圖表示法都和 graphlib 不同，所以無論如何都無法直接轉換。圖的表示法真的很重要。

我還發現另外兩個具有圖型別的語言：Erlang 和 SWI-Prolog。我對這兩種語言都不熟悉，也無法判斷它們是何時加入的；至少就 Erlang 而言，是在 2008 年之前。我曾聯繫一位 Erlang 核心語言委員會的成員，但沒有收到回覆。

圖語言

這類程式語言中「一切皆是圖」，就像在 bash 中一切皆是字串、在 Lisp 中一切皆是清單一樣。一些例子包括 GP2 和 Grape。根據我與該領域人士的一些通信，目前這仍然是高度學術性的研究。

數學軟體語言

Mathematica、MATLAB、Maple 等都以某種形式提供了圖函式庫。我可不會為了多了解一點就去付那數千美元的授權費。

更新 2024-03-18

我已將收到關於這篇文章的一些評論整理在這裡。

1. 不是開玩笑，雜湊表就是二分圖。這曾被用來證明 cuckoo hashing 各項操作的效能。^[return]
2. 我用 cloc 1.96 計算出這兩個數字。我在 networkx/networkx/algorithms（56989）和 cpython/Lib（588167）上執行 cloc。整個 networkX 函式庫約有 90,000 行程式碼。^[return]
3. 你可以透過保持邊清單為已排序狀態並進行 O(log(|e|)) 的二分搜尋來提高效率，代價是讓邊的插入變得更昂貴。^[return]
4. NetworkX 提供了將圖轉換為其他表示法的函式，但並未提供直接操作這些表示法的方式。^[return]
5. 21 個經典 NP-complete 問題中有 14 個是圖問題。^[return]
6. 請勿與仍在開發中的提議標準 GQL 語言 GQL 混淆。^[return]