C++ Boost

The Boost Graph Library (BGL) BGL Book

在計算機科學中,圖是一些用來解決各種問題的數學抽像概念。所以,這些抽像的概念一定可以用計算機程序表示。一個標準化的用來遍歷圖的通用接口,對 於圖的算法和數據結構來說是相當重要的。Boost圖庫中專門有一些用來訪問圖數據結構的通用接口,它們隱藏了繁雜的內部實現。這是一套開放的接口,一些 用其它圖庫實現的接口也能夠使用BGL中的通用算法,而且這套接口也能使用BGL中其它算法。BGL提供了一些遵照這套接口的通用類,但是不要以為這是唯 一的圖形類;BGL中當然還有一些能夠更好解決特定問題的類。我們相信BGL最大的貢獻就是規範話了這套接口。

與STL[2]相類似,BGL中的接口和組件也是范型的。接下來的幾節,我們將回顧一下范型編程在STL中扮演的角色,以及比較一下我們如何把范型編程應用到圖的環境中。 

當然如果你已經對范型編程很熟悉了那麼請跳到目錄繼續閱讀下面章節。

BGL的源代碼是隨著Boost一起發佈的,到這下載

如何編譯BGL

不能!Boost圖庫僅僅是一些頭文件,所以不需要編譯。唯一的例外是: GraphViz input parser

當編譯的時候,別忘了開啟編譯優化選項。比如,在Ms Visual C++中選擇「Release」模式;在GCC中使用-o2或者-o3標誌。

STL中的范型

STL中用三中方法來實現范型化

算法/數據結構互通性

首先,每一個算法都是用數據結構無關的方法寫出的,允許一個單獨的函數模版處理多種不同容器類。迭代器的概念是實現算法和數據結構解藕的關鍵因素。 這個方法最明顯的效果就是縮小的STL的代碼尺寸,使其從O(M*N)變成了O(M+N),其中M是算法個數,N是容器個數。試想,如果有20個算法、5 個數據結構,採用范型編程與不採用的區別是:由寫100個函數編程寫25個函數!隨著算法和數據結構數量的增加這個差距會越來越大。

通過函數對像擴展

STL范型化的第二種方法是算法和容器可擴展。用戶能夠通過函數對像改寫和定制STL。這樣的靈活性使STL成為解決現實問題的有利工具。每一個編程問題對應它自己的一組實體和被規範化的接口。函數對像提供了一種機制,它能夠對STL擴充以處理特定領域問題的。

元素類型參數化

STL范型化的第三種方法使參數化元素類型。相對於其它兩種方法,STL中使用這種方法的次數比較少。范型編程中經常簡寫參數化列表,例如:std::list<T>。以上僅僅是范型編程的冰山一角。

Boost圖庫中的范型

與STL一樣,BGL中也有3種范型方法

算法/數據結構互通性

第一種,BGL中的圖算法被寫成了一種把具體數據結構細節抽像出來的接口。與STL相同,BGL也是用迭代器(iterator)來定義遍歷相關數 據結構的接口。有3種完全不同的遍歷模式:遍歷圖中所有的點,遍歷圖中所有的邊,以及沿相鄰結構進行遍歷(從一丁點到它的每一相鄰頂點)。每一種遍歷方式 需要一種迭代器。

這種范型接口能夠使模版函數(例如: breadth_first_search() 函數)接受各種圖數據結構,從鏈表表示的圖到數組表示的圖都可以。在圖領域這種靈活性是相當重要的。圖數據結構經常為了某些特殊需求而定制。傳統上,如果 程序員想要復用一個算法,他們一定要把自己的數據結構進行轉換(或拷貝)成圖庫的規定數據結構才行。比如LEDA,GTL,Stanford GraphBase就是這種情況;特別是用Fortan寫成的圖算法更需要這種轉換。這種轉換嚴格的限制了圖算法的復用性。

與之相反,定制的圖數據結構能夠被BGL中的范型算法統一對待,BGL使用一種叫做外部適配(external adaptation)(參考 如何把非BGL圖轉換到BGL中一 節)的方法來實現該技術。外部適配封裝了一個新的接口,使數據結構不用進行拷貝,也不用替換內部適配對象。BGL相關接口使這種轉換變得很容易。舉個來 說,在BGL中,我們已經用各種圖數據結構(比如:LEDA圖,Stanford GraphBase圖,甚是還有Fortan風格的數組)建立了一套接口。

用遍歷器(vistitor)進行擴展

第二種,BGL中的圖算法是可擴展的。BGL引入了遍歷器(visitor)的概念,遍歷器就是一個有多個方法的功能實體。在圖算法中,經常會有幾 個關鍵的「事件點」使用戶插入一些操作。在每個「事件點」,遍歷器對像會有不同的方法被調用。 「事件點」以及對應的遍歷器方法都依賴於相應的算法。遍歷器經常包括的方法有:
start_vertex(), discover_vertex(), examine_edge(), tree_edge(), 以及finish_vertex().

點、邊屬性多重參數化

BGL中的第三種范型方法與STL容器中的元素類型參數化相似,雖然這點對於圖來說有些複雜。我們需要給圖的邊、點賦予相關含義(屬性)。另外,有 時候需要給各個點、邊賦予多重屬性;這意味這需要多重參數化。STL的 std::list<T>類有一個參數T作為它的元素類型。類似,BGL中的圖類也有模版參數作為邊、點的屬性。一個屬性詳細說明了該屬性的 參數類型,並且分配了標識該屬性的標籤。標籤用來區分邊或點的多重屬性。與特性點或邊相對應的屬性能夠通過屬性映射(property map)獲得。每一個屬性有一個單獨的屬性映射。

傳統的圖庫和圖數據結構在圖屬性參數化方面做的不是很好。這也是圖數據結構一定要為應用定制的主要原因。BGL中的屬性參數化能夠使BGL中的圖類很好的復用。

算法

BGL中的算法由一組核心算法模型(用范型算法實現)和一組較大的圖算法組成。核心算法模型是:

圖算法模型本身並不進行任何有意義的計算,它們僅僅是為了構建圖算法而已。BGL中的圖算法當前包括:

數據結構

BGL當前提供2種圖類和一個邊列表適配器:

adjacency_list類好比圖類中的「瑞士軍刀」。它高度參數化,以致於能夠為各種情況優化,例如:有向圖還是無向圖,允許還是不允許平行邊,僅外邊能有效訪問還是內外邊都可以,是否以空間為代價進行快速頂點插入或移出,等等。

adjacency_matrix類把邊存儲在一個|V|x|V|的矩陣中(其中,|V|表示頂點個數)。矩陣元素表示圖中的邊。鄰接矩陣尤其適合表示稠密圖(dense graphs),比如,有|V|2條邊的圖。


edge_list類是一個能接受任何邊迭代器的適配器,實現了一個邊列表圖(Edge List Graph)。


Copyright c 2000-2001 Jeremy Siek, Indiana University (jsiek@osl.iu.edu)
Lie-Quan Lee, Indiana University (llee@cs.indiana.edu)
Andrew Lumsdaine, Indiana University (lums@osl.iu.edu)