圖 (抽象資料類型)
圖係電腦科學裏頭嘅一種抽象數據類型,旨意實現數學嘅圖論領域啲無向圖同有向圖嘅概念喺電腦當中。
圖數據結構包括一個有限嘅(又可能變得嘅)集含有啲「頂點」(亦都喊做「綟」或者「點」),同埋一個集含有啲頂點𠵿,啲𠵿喺無向圖就係無序𠵿、喺有向圖就係有序𠵿。啲𠵿喊做「檠」(亦都喊做「紷」或者「線」)。對於有向圖又喊做「檠」,但有時亦都喊做「箭咀」或者「弧」(arcs)。啲頂點可以係圖結構嘅一部分,又可以係啲外部實體、攞整數嘅索引或者參照表示返嘅。
圖數據結構仲可以捉某啲檠值戥每條檠相關聯,例如符號標籤或者數字屬性(成本、容量、長度等)。
操作
編輯圖數據結構G提供有嘅基本操作通常包括:[1]
adjacent
(G, x, y):測試從綟x到綟y有檠冇;neighbors
(G, x):列嗮啲綟y,係有一條檠從綟x到綟y嘅;add_vertex
(G, x):添綟x,若果粒綟嘸存在;remove_vertex
(G, x):剷綟x,若果粒綟存在;add_edge
(G, x, y):添檠從綟x到綟y,若果條檠嘸存在;remove_edge
(G, x, y):剷檠從綟x到綟y,若果條檠存在;get_vertex_value
(G, x):get個戥綟x關聯嘅值;set_vertex_value
(G, x, v):set個戥綟x關聯嘅值成v。
對於啲結構,啲檠加有值嘅,通常仲提供埋:[1]
get_edge_value
(G, x, y):get個戥檠(x, y)關聯嘅值;set_edge_value
(G, x, y, v):set個戥檠(x, y)關聯嘅值成v。
圖表示嘅常用數據結構
編輯- 鄰接表[2]
- 啲綟儲成記錄或者對象,每粒綟儲一版相鄰綟嘅列表。種數據結構允許喺綟度儲埋啲附加數據。若果檠亦都儲成對象,就儲得附加數據,喺種情況下,每粒綟儲住佢條搭配檠,每條檠儲住佢粒搭配綟。
- 鄰接矩陣[3]
- 二維矩陣,其中行代表住源綟,列代表住目標綟。檠同綟上高嘅數據必須儲喺外部。只有一條檠嘅成本儲得喺每副綟之間。
- 關聯矩陣[4]
- 二維矩陣,行代表住綟,列代表住檠。一欄表示行綟同列檠之間嘅關聯。
下表寫有啲時間複雜度成本畀喺圖上執行各種操作嘅,對於啲表示裏頭嘅每一個,用|V|綟數同|E|檠嘅數量。 喺矩陣表示當中,啲欄編碼有成本畀爬檠。對於嘸存在嘅啲檠,成本着假定為∞。
鄰接表 | 鄰接矩陣 | 關聯矩陣 | |
---|---|---|---|
存圖 | |||
添綟 | |||
添檠 | |||
剷綟 | |||
剷檠 | |||
綟x同y係相鄰冇?(假設已知佢哋所儲位置) | |||
註 | 剷綟、檠好慢,因為要搵嗮啲綟或者檠 | 添、剷綟好慢,因為要調整矩陣大細/複製矩陣 | 添、剷綟、檠都好慢,因為要調整矩陣大細/複製矩陣 |
鄰接表通常係首選,因為可以有效噉表示得到啲稀疏圖。首選鄰接矩陣嘅情況係,若果幅圖係密集嘅(即檠數|E|接近綟數嘅平方|V|2),或者若果有檠連接兩粒綟嘅必須快速搵得到。[5][6]
平行表示
編輯圖相關問題嘅平行化有返啲重大挑戰:數據驅動計算、非結構化問題、局部性差,高數據訪問/計算比。[7][8]圖啲表示使喺平行架構嘅喺應對啲挑戰方面發揮到重要作用。揀啲表示嘸啱可能會增加多餘嘅通訊成本畀個演算法,會降低佢個可擴展性。下便會考慮共享同分佈式嘅內存架構。
共享內存
編輯共享內存模型嘅情況下,攞嚟平行處理嘅圖表示戥順序情況下嘅相同,[9]因為喺共享內存度平行噉只讀訪問個圖表示(例如鄰接表)都仲算高效。
分佈式內存
編輯喺分佈式內存模型裏頭,通常嘅做法係捉幅圖個綟集 進行分墢,轉成 套 ,其中 係可用嘅等處理元素(processing elements,PE)數量。然之後,綟集啲墢着分佈到有匹配索引嘅PE,佮埋相應嘅檠。每個PE都有自己嘅子圖表示,其中喺另一墢裏頭有端點嘅檠需要特別注意。對於似MPI(Message Passing Interface)噉嘅標準通訊接口,擁有另一個端點嘅PE,佢個ID必須係識別得到嘅。喺分佈式圖演算法嘅計算過程裏頭,沿住啲檠傳遞訊息即係通訊。[9]
圖分墢(Graph partition)有必要謹慎,低通訊度戥大細分得均勻兩者係需要權衡嘅[10];圖分墢係一個NP難題,所以計算係嘸行得嘅。相反,以下啲啟發式方法就有使到。
1D分墢:每個處理器都得到 綟同相應嘅輸出檠。呢個可以理解為鄰接矩陣嘅行或者列分解。對於喺此表示上運行嘅演算法,需要一個All-to-All通訊步驟同埋 消息緩衝區嘅大細,因為每個PE可能有到每個其他PE嘅傳出檠。[11]
2D分墢:每個處理器獲得鄰接矩陣嘅一個子矩陣。假設處理器喺一個矩形裏頭對齊 ,其中 同 分別係每行同每列裏頭處理元素嘅數量。然之後每個處理器得到維數鄰接矩陣嘅一個子矩陣 。呢層可以可視化成矩陣入面嘅棋盤圖案。[11]所以,每個處理單元只能有出到同行同列啲PE嘅檠。噉每個PE嘅通訊搭檔數量就着限制為 種可能性當中嘅 。
壓縮表示
編輯喺機器學習、社交網絡分析同其他領域有啲圖係有數万億條檠嘅。壓縮過嘅圖表示經已有開發出嚟,着攞嚟減少I/O同內存嘅要求。Huffman編碼等通用技術都適用,但可以透過特定方式處理啲鄰接表或者鄰接矩陣嚟提高效率。[12]
睇埋
編輯考
編輯- ↑ 1.0 1.1 See, e.g. Goodrich & Tamassia (2015), Section 13.1.2: Operations on graphs, p. 360. For a more detailed set of operations, see Mehlhorn, K.; Näher, S. (1999), "Chapter 6: Graphs and their data structures", LEDA: A platform for combinatorial and geometric computing, Cambridge University Press, pp. 240–282.
- ↑ Cormen et al. (2001), pp. 528–529; Goodrich & Tamassia (2015), pp. 361-362.
- ↑ Cormen et al. (2001), pp. 529–530; Goodrich & Tamassia (2015), p. 363.
- ↑ Cormen et al. (2001), Exercise 22.1-7, p. 531.
- ↑ Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001), "Section 22.1: Representations of graphs", Introduction to Algorithms (第Second版), MIT Press and McGraw-Hill, pp. 527–531, ISBN 0-262-03293-7.
- ↑ Goodrich, Michael T.; Tamassia, Roberto (2015), "Section 13.1: Graph terminology and representations", Algorithm Design and Applications, Wiley, pp. 355–364.
- ↑ Bader, David; Meyerhenke, Henning; Sanders, Peter; Wagner, Dorothea (January 2013). Graph Partitioning and Graph Clustering. Contemporary Mathematics (英文).第588卷. American Mathematical Society. doi:10.1090/conm/588/11709. ISBN 978-0-8218-9038-7.
- ↑ LUMSDAINE, ANDREW; GREGOR, DOUGLAS; HENDRICKSON, BRUCE; BERRY, JONATHAN (March 2007). "Challenges in Parallel Graph Processing". Parallel Processing Letters. 17 (1): 5–20. doi:10.1142/s0129626407002843. ISSN 0129-6264.
- ↑ 9.0 9.1 Sanders, Peter; Mehlhorn, Kurt; Dietzfelbinger, Martin; Dementiev, Roman (2019). Sequential and Parallel Algorithms and Data Structures: The Basic Toolbox (英文). Springer International Publishing. ISBN 978-3-030-25208-3.
- ↑ "Parallel Processing of Graphs" (PDF). 原著 (PDF)喺2021年8月25號歸檔. 喺2021年7月12號搵到.
- ↑ 11.0 11.1 "Parallel breadth-first search on distributed memory systems | Proceedings of 2011 International Conference for High Performance Computing, Networking, Storage and Analysis" (英文). doi:10.1145/2063384.2063471.
{{cite journal}}
: Cite journal requires|journal=
(help) - ↑ Besta, Maciej; Hoefler, Torsten (27 April 2019). "Survey and Taxonomy of Lossless Graph Compression and Space-Efficient Graph Representations". arXiv:1806.01799.
{{cite journal}}
: Cite journal requires|journal=
(help)