圖形是數學抽象概念，對於解決電腦科學中的許多問題非常有用。因此，這些抽象概念也必須在電腦程式中表示。標準化的通用圖形遍歷介面對於鼓勵圖形演算法和資料結構的重複使用至關重要。Boost 圖形函式庫的一部分是一個通用介面，允許存取圖形的結構，但隱藏了實作的細節。這是一個「開放」介面，任何實作此介面的圖形函式庫都將與 BGL 通用演算法以及其他使用此介面的演算法相容。BGL 提供了一些符合此介面的通用圖形類別，但它們並非要成為「唯一」的圖形類別；在某些情況下，肯定會有其他更好的圖形類別。我們認為 BGL 的主要貢獻在於此介面的制定。
BGL 圖形介面和圖形元件是通用的，與標準樣板函式庫 (STL) [2] 的概念相同。在以下章節中，我們將回顧通用程式設計在 STL 中扮演的角色，並將其與我們在圖形環境中應用通用程式設計的方式進行比較。
當然，如果您已經熟悉通用程式設計，請直接開始！這是目錄。對於分散式記憶體平行處理，您也可以查看平行 BGL。
BGL 的原始碼是 Boost 發行版的一部分，您可以從這裡下載。
別建置！ Boost 圖形函式庫是一個僅標頭檔的函式庫，不需要建置即可使用。唯一的例外是 GraphViz 輸入解析器和 GraphML 解析器。
編譯使用 BGL 的程式時，請務必使用最佳化進行編譯。例如，在 Microsoft Visual C++ 中選擇「發行」模式，或提供旗標-O2或-O3給 GCC。
STL 在三個方面是通用的。
首先，每個演算法都以資料結構中立的方式編寫，允許單個樣板函式在許多不同類別的容器上運作。迭代器的概念是演算法和資料結構解耦的關鍵要素。此技術的影響是將 STL 的程式碼大小從 O(M*N) 減少到 O(M+N)，其中 M 是演算法的數量，而 N 是容器的數量。考慮到有 20 個演算法和 5 個資料結構的情況，這將是編寫 100 個函式與僅編寫 25 個函式之間的差異！而且，隨著演算法和資料結構數量的增加，差異會持續快速增長。
STL 通用的第二個方面是其演算法和容器具有可擴充性。使用者可以透過使用函式物件來調整和自訂 STL。這種靈活性使 STL 成為解決實際問題的絕佳工具。每個程式設計問題都會帶來自己的一組實體和互動，必須對其進行建模。函式物件提供了一種擴充 STL 以處理每個問題域的具體細節的機制。
STL 通用的第三個方面是其容器基於元素類型進行參數化。雖然非常重要，但這也許是 STL 通用性中最不「有趣」的一方面。通用程式設計通常會以參數化清單的簡短描述來概括，例如std::list<T>。這幾乎只是觸及表面而已！
與 STL 類似，BGL 在三個方面是通用的。
首先，BGL 的圖形演算法是根據介面編寫的，該介面抽象化了特定圖形資料結構的細節。與 STL 類似，BGL 使用迭代器來定義資料結構遍歷的介面。有三種不同的圖形遍歷模式：遍歷圖形中的所有頂點、遍歷所有邊，以及沿著圖形的相鄰結構（從一個頂點到其每個相鄰頂點）。每種遍歷模式都有單獨的迭代器。
此通用介面允許諸如 breadth_first_search() 之類的樣板函式在各種圖形資料結構上運作，從使用指標連結節點實作的圖形到以陣列編碼的圖形。這種靈活性在圖形領域尤其重要。圖形資料結構通常是為特定應用量身訂製的。傳統上，如果程式設計師想要重複使用演算法實作，他們必須將圖形資料轉換/複製到圖形函式庫規定的圖形結構中。LEDA、GTL、Stanford GraphBase 等函式庫就是這種情況；對於以 Fortran 編寫的圖形演算法來說尤其如此。這嚴重限制了圖形演算法的重複使用。
相反地，自訂（甚至舊有）圖形結構可以與 BGL 的通用圖形演算法一起直接使用，方法是使用外部調整（請參閱如何將現有圖形轉換為 BGL 一節）。外部調整在資料結構周圍封裝一個新介面，而無需複製且不將資料置於調整器物件內。BGL 介面經過精心設計，使此調整變得容易。為了演示這一點，我們建立了介面程式碼，用於在 BGL 圖形演算法中使用各種圖形結構（LEDA 圖形、Stanford GraphBase 圖形，甚至 Fortran 風格的陣列）。
其次，BGL 的圖形演算法是可擴充的。BGL 引入了訪問者的概念，它只是一個具有多個方法的函式物件。在圖形演算法中，通常有幾個關鍵的「事件點」，在這些事件點插入使用者定義的操作會很有用。訪問者物件具有一個不同的方法，該方法會在每個事件點被呼叫。特定的事件點和相應的訪問者方法取決於特定的演算法。它們通常包含如下方法start_vertex(), discover_vertex(), examine_edge(), tree_edge()和finish_vertex().
BGL 通用的第三個方面類似於 STL 容器中元素類型的參數化，但對於圖形而言，情況又稍微複雜一些。我們需要將值（稱為「屬性」）與圖形的頂點和邊相關聯。此外，通常需要將多個屬性與每個頂點和邊相關聯；這就是我們所說的多參數化。STL 的std::list<T>class 有一個參數T用於其元素類型。同樣，BGL 圖形類別具有頂點和邊「屬性」的樣板參數。屬性指定屬性的參數化類型，並將識別標籤指派給該屬性。此標籤用於區分邊或頂點可能具有的多個屬性。附加到特定頂點或邊的屬性值可以透過屬性映射取得。每個屬性都有一個單獨的屬性映射。
在圖形屬性的參數化方面，傳統的圖形函式庫和圖形結構都無法滿足要求。這是圖形資料結構必須為應用量身訂製的主要原因之一。BGL 圖形類別中屬性的參數化使其非常適合重複使用。
BGL 演算法由一組核心演算法模式（實作為通用演算法）和一組更大的圖形演算法組成。核心演算法模式包括
演算法模式本身並不會計算圖形上的任何有意義的量；它們只是建構圖形演算法的基礎。BGL 中的圖形演算法目前包括
BGL 目前提供兩個圖形類別和一個邊列表調整器
的adjacency_list類別是圖形類別的通用「瑞士刀」。它經過高度參數化，可以針對不同情況進行最佳化：圖形是有向還是無向、允許或不允許平行邊、有效存取僅輸出邊或也存取輸入邊、快速插入和移除頂點，但代價是額外的空間開銷等。
的adjacency_matrix類別將邊儲存在 |V| x |V| 矩陣中（其中 |V| 是頂點的數量）。此矩陣的元素表示圖形中的邊。相鄰矩陣表示法特別適合非常密集的圖形，即邊數接近 |V|2 的圖形。
的edge_list類別是一個調整器，它接收任何類型的邊迭代器並實作 邊列表圖形。
| 版權所有 © 2000-2001 |
Jeremy Siek，印第安納大學 (jsiek@osl.iu.edu) Lie-Quan Lee，印第安納大學 (llee@cs.indiana.edu) Andrew Lumsdaine，印第安納大學 (lums@osl.iu.edu) |
