導語：簡析開源Boost庫在網絡的應用論文一文來源于網友上傳，不代表本站觀點，若需要原創文章可咨詢客服老師，歡迎參考。

隨著地理信息產業的建立和數字化信息產品的普及，地理信息系統(GIS)已經深入到各行各業，成為人們生產、生活、學習和工作中不可缺少的工具和助手。GIS技術的發展，離不開信息技術的革新。隨著信息技術的發展，很多新概念、新理念提出并得到應用后，很快就會被GIS軟件吸納進去。

地理網絡分析是地理信息系統的核心功能，也是地理信息系統與其他計算機系統的根本區別。數學上的網絡圖在地理網絡建模以及網絡分析運算中仍具有重要的作用。同時，其相對的獨立性更容易形成獨立的模塊化、組件化的軟件包。目前，已經有很多這樣的軟件包或獨立的類庫存在，既有商業版本的，也有開源性質的，也包括基于不同操作平臺和利用各種程序語言開發的，這其中開源的boostC++類庫就是其中優秀的代表之一。

1GIS系統開發語言與BoostC++庫

在地理信息系統(GIS)的開發過程中，程序語言的選擇具有重要的意義。雖然隨著軟件開發平臺和編譯技術的不斷發展，程序語言有著相互借鑒和融合的趨勢，但不同的程序語言在軟件成果的運行效率、可移植性、可復用性以及與軟件設計平臺的結合等方面存在很大的差異。C++作為GIS軟件開發的主要程序語言，是專門為擴展性而設計的，語言為泛型構造提供的便利極為強大，目前仍然具有不可或缺的作用。隨著C++語言的高級工具和技術不斷涌現，開發復雜應用軟件正變得更簡單、更高效。同時，開放源代碼軟件運動的興起和發展，不但推動了C++語言自身的不斷完善，也推動了GIS開發技術的快速發展和GIS應用領域的不斷拓寬。Boost庫是一個可移植、開放源代碼的C++庫，作為標準庫的后備，是C++標準化進程的發動機之一。Boost是由C++標準委員會庫工作組成員發起的一個C++準標準庫，相當于C++標準模板庫(Standertemlatelibrary，STL)的延續和擴充，它的設計理念和STL比較接近，都是利用泛型讓復用達到最大化，對比STL，Boost更加實用。STL主要集中在算法部分，而Boost包含了不少工具類，可以完成比較具體的工作。Boost庫覆蓋了廣泛的應用領域，從數學應用庫到智能指針，從模板元編程庫到預處理器庫，從線程到lambda表達式等。Boost可以在目前存在的絕大多數操作系統(Windows，Unix，Linux，Solaris，MacOSX等)平臺上使用，同時可以應用目前使用的各種C++程序開發平臺進行編譯和連接，還為很多目前流行的程序語言(Java，Python，Basic，C#等)提供相對統一的接口，方便了其他語言的應用。基于Boost庫進行程序設計和開發，使得利用C++語言進行GIS開發更為優雅、有活力、高效。

2Boost在地理網絡分析中的作用

地理網絡分析是空間分析的一個重要方面，是依據地理網絡拓撲關系，并通過考察地理網絡元素的空間、屬性數據，對網絡的性能特征進行多方面的分析計算。地理網絡分析主要包括路徑分析、服務中心范圍的確定、可達性分析等，其核心是對最短路徑的求解。地理網絡分析作為GIS應用最主要的功能之一，其主要目的是對地理網絡(如交通網絡)、城市基礎設施網絡(如各種網線、電力線、電話線、供排水管線等)進行地理分析和模型化。

按照數學意義上的看法，可以把地理網絡看作圖，因而可以按照圖論的理論基礎來描述地理網絡，并可以利用圖論的研究成果來解決地理網絡中的網絡分析問題，圖論中的網絡概念和一些分析算法在地理網絡的表示和網絡分析中具有重要的意義。BGL作為Boost的工具類之一，是一個處理圖數據結構的庫，可以應用于地理網絡分析的很多領域。1)BGL的設計受到STL的重要影響，包括多個不同的泛型圖數據結構:鄰接鏈表、鄰接矩陣和邊列表等，作為網絡表示和存貯的基礎。同時BGL提供了一個標準化的用來訪問圖數據結構的通用接口和遵照這套接口的通用類。這套接口不但隱藏了繁雜的內部實現，同時作為一套開放的規范化的接口，一些用其它圖庫實現的接口也能夠使用BGL中的各種通用算法。

2)BGL提出了基于泛型的圖算法，其算法由一組核心算法模型(用泛型算法實現)和一組較大的圖算法組成。核心算法模型包括廣度優先搜索、深度優先搜索、均勻開銷搜索。BGL中的圖算法被寫成了一種把具體數據結構細節抽象出來的接口，本身并不進行任何有意義的計算，僅僅是為了構建圖算法而已。每一個算法都是用數據結構無關的方法寫出的，允許一個單獨的函數模版處理多種不同的容器類。同時BGL中的圖算法是可擴展的，用戶能夠通過函數對象改寫和定制算法，以處理特定領域的問題。BGL中的圖算法當前包括:Dijkstra最短路徑、Bellman-Ford最短路徑、Johnson任意兩點間最短路徑、Kruskal最小生成樹、Prim最小生成樹、連通分支、強連通分支、動態連通分支(使用不相交集合)、拓撲排序、轉置、逆CuthillMckee排序、拓撲邏輯排序等算法。

3)BGL可以實現適應圖的附加屬性，這在地理網絡分析中有著重要的意義。地理網絡雖然一般可以用純數學意義論文上的圖論上的“網絡”來描述和模擬，但它又是一個既具有空間分布特征，又具有其本身的許多描述性特征，即空間數據和屬性數據相互結合的網絡系統，因此，必須給數學意義上的“網絡”添加屬性才能更好地模擬地理網絡。BGL中的圖數據結構類也有模板參數作為邊、點的屬性，一個屬性詳細說明了該屬性的參數化類型，并且分配了標識該屬性的標簽，用來區分邊或點的多重屬性，附著到特定的點或邊的屬性能夠通過屬性映射(proper-tymap)獲得。BGL在圖算法中可以為圖結構添加兩種屬性:外在存貯屬性和內在存貯屬性，并且為這兩種圖的附加屬性提供了一致的訪問接口。公務員之家

3BGL在地理網絡分析中的應用實例分析

3.1最短路徑在地理網絡分析中的應用

最短路徑問題是地理網絡分析中的基本問題，作為資源分配、線路規劃、流量分析等網絡優化問題的基礎，很多網絡相關問題，如最優路徑問題、最可靠路徑問題、網絡最大流問題以及各種流量分析問題均可納入最短路徑研究的范疇，各種網絡分析技術實現的關鍵在于網絡拓撲結構的建立和高效的最短路徑算法。

最短路徑算法是圖論中的一個經典問題，經典的圖論與不斷發展完善的計算機數據結構及算法的有效結合使得新的最短路徑算法不斷涌現。針對不同的網絡特征、應用需求及具體的軟硬件環境，各種最短路徑算法在空間復雜度、時間復雜度、易實現性及應用范圍等方面各具特色。目前，大家的研究工作主要集中于算法實現的優化改進與應用方面，一般用于路徑最短求解的經典算法有Dijkstra算法、Floyd算法、啟發式算法及其它算法。在圖論中，圖的存儲方式有鄰接矩陣和鄰接表兩種基本方法。地理網絡一般可以看成是帶權有向不完全稀疏圖，對于大型稀疏地理網絡，如道路網而言，利用鄰接矩陣存儲，其數據冗余度過大，因而是不適宜的。鄰接表是一種常用且對稀疏圖效率非常高的存儲結構，鄰接表存儲結構的最差運行時間復雜度比鄰接矩陣法存儲結構低一階。綜合比較起來，鄰接表存儲結構占優。BoostBGL提供了基于模板的無向圖和有向圖的鄰接表存儲方式的構造方法，以及各種經典的最短路徑算法，基本能夠滿足地理網絡分析的應用。

3.2基于BGL的最短路徑的實現

利用BGL實現最短路徑的基本步驟如下:1)構造網絡圖結構。利用BGL提供的模板可以定義各種網絡圖結構，可以在這些模板的基礎上創建自己的類型，如下所示即定義了一個基于鄰接表的無向圖結構，且其邊的權值(邊的屬性)為雙精度浮點性。typedefadjacency_list<listS，vecS，undi-rectedS，no_property，property<edge_weight_t，double>>graph_t;2)創建網絡圖實例。//首先定義網絡節點和邊。typedefgraph_traits<graph_t>::vertex_descriptorvertex_descriptor;typedefgraph_traits<graph_t>::edge_de-scriptoredge_descriptor;定義邊的屬性表:typedefproperty_map<graph_t，edge_weight_t>::typeweight_map;//得到邊的屬性表:weight_mapweightmap=get(edge_weight，g);從網絡數據文件或數據庫中得到網絡圖的拓撲數據，并循環插入:graph_tg;for(;;){edge_descriptore;boolinserted;tie(e，inserted)=add_edge(ss，ee，g);weightmap[e]=fLength;}3)運行最短路徑算法(以Dijkstra算法為例)。//定義dijkstra算法的訪問算子:template<classVertex>classdijkstra_os_visitor:publicboost::de-fault_dijkstra_visitor{public:dijkstra_os_visitor(Vertexgoal):m_goal(goal){}template<classGraph>voidexamine_vertex(Vertexu，Graph&g){if(u==m_goal)throwfound_goal();}private:Vertexm_goal;};//運行Dijkstra算法std::vector<vertex_descriptor>p(num_ver-tices(g));std::vector<double>d(num_vertices(g));vertex_descriptors=vertex(N1，g);vertex_descriptorgoal=vertex(N2，g);property_map<graph_t，vertex_index_t>::typeindexmap=get(vertex_index，g);dijkstra_shortest_paths(g，s，&p[0]，&d[0]，weightmap，indexmap，std::less<double>()，closed_plus<double>()，(std::numeric_limits<double>::max)()，0.0，dijkstra_os_visitor<vertex_descriptor>(goal));4)得到路徑分析結果。//得到最短路徑鏈段:vertex_descriptorvv=goal;while(p[vv]!=vv){vv=p[vv];…;}vv=vertex(goal，g);//得到最短路徑的長度:doublefLentgh=d[vv]3.3試驗結果與分析利用Boost庫，建立一個獨立于系統之外的地理網絡分析軟件包，隨著Boost的更新而更新(僅僅可以通過替換Boost的動態鏈接庫及其相應頭文件即可)。該軟件包已經應用于軍隊及地方的很多重大課題，取得很好的效果。同時，為保證軟件包應用的穩定性、可靠性以及對其實際應用性能進行檢驗，作者在基于PentiumIII700MH和256M內存的微機上，對于27619個節點和36066條邊的某地區的實際道路網進行單對節點間的最短路徑分析，其運行時間一般為3s，運行以后的效果如圖1所示。根據應用和試驗效果以及對BGL源代碼的分析可以得到，Boost圖庫的算法是高效和易用的，利用Boost圖庫完全可以滿足GIS中地理網絡分析的應用。可提高系統開發效率，而且最新的BGL還提供了基于圖結構的并行算法，可以滿足未來地理網絡分析中海量數據分析的需要。圖1最短路徑分析的運行效果

4結束語

目前，隨著開放源代碼軟件運動的興起和發展，利用一些優秀的開源代碼，可以使GIS開發人員更好地關注GIS設計過程，將一些GIS的底層模塊(例如網絡分析、數學運算、異常處理等)分離開來并獨立開發，可以提高系統的開發效率和模塊化程度。作為一種優秀的編程范式，功能強大的C++BoostBGL類庫為基于地理網絡的空間分析提供了一個新的解決框架，可以幫助用戶模擬現實世界中的網絡條件與情景。這使得程序設計代碼更加簡潔，改進程序性能，同時使程序員花費更少的時間重寫相同的代碼，為不同過程提供更好的可復用性、封裝性和互操作性，便于程序維護和擴展。