簡析開源Boost庫在網(wǎng)絡(luò)的應(yīng)用論文

導(dǎo)語：簡析開源Boost庫在網(wǎng)絡(luò)的應(yīng)用論文一文來源于網(wǎng)友上傳，不代表本站觀點，若需要原創(chuàng)文章可咨詢客服老師，歡迎參考。

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

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

1GIS系統(tǒng)開發(fā)語言與BoostC++庫

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

2Boost在地理網(wǎng)絡(luò)分析中的作用

地理網(wǎng)絡(luò)分析是空間分析的一個重要方面，是依據(jù)地理網(wǎng)絡(luò)拓?fù)潢P(guān)系，并通過考察地理網(wǎng)絡(luò)元素的空間、屬性數(shù)據(jù)，對網(wǎng)絡(luò)的性能特征進(jìn)行多方面的分析計算。地理網(wǎng)絡(luò)分析主要包括路徑分析、服務(wù)中心范圍的確定、可達(dá)性分析等，其核心是對最短路徑的求解。地理網(wǎng)絡(luò)分析作為GIS應(yīng)用最主要的功能之一，其主要目的是對地理網(wǎng)絡(luò)(如交通網(wǎng)絡(luò))、城市基礎(chǔ)設(shè)施網(wǎng)絡(luò)(如各種網(wǎng)線、電力線、電話線、供排水管線等)進(jìn)行地理分析和模型化。

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

2)BGL提出了基于泛型的圖算法，其算法由一組核心算法模型(用泛型算法實現(xiàn))和一組較大的圖算法組成。核心算法模型包括廣度優(yōu)先搜索、深度優(yōu)先搜索、均勻開銷搜索。BGL中的圖算法被寫成了一種把具體數(shù)據(jù)結(jié)構(gòu)細(xì)節(jié)抽象出來的接口，本身并不進(jìn)行任何有意義的計算，僅僅是為了構(gòu)建圖算法而已。每一個算法都是用數(shù)據(jù)結(jié)構(gòu)無關(guān)的方法寫出的，允許一個單獨的函數(shù)模版處理多種不同的容器類。同時BGL中的圖算法是可擴展的，用戶能夠通過函數(shù)對象改寫和定制算法，以處理特定領(lǐng)域的問題。BGL中的圖算法當(dāng)前包括:Dijkstra最短路徑、Bellman-Ford最短路徑、Johnson任意兩點間最短路徑、Kruskal最小生成樹、Prim最小生成樹、連通分支、強連通分支、動態(tài)連通分支(使用不相交集合)、拓?fù)渑判颉⑥D(zhuǎn)置、逆CuthillMckee排序、拓?fù)溥壿嬇判虻人惴ā?/p>

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

3BGL在地理網(wǎng)絡(luò)分析中的應(yīng)用實例分析

3.1最短路徑在地理網(wǎng)絡(luò)分析中的應(yīng)用

最短路徑問題是地理網(wǎng)絡(luò)分析中的基本問題，作為資源分配、線路規(guī)劃、流量分析等網(wǎng)絡(luò)優(yōu)化問題的基礎(chǔ)，很多網(wǎng)絡(luò)相關(guān)問題，如最優(yōu)路徑問題、最可靠路徑問題、網(wǎng)絡(luò)最大流問題以及各種流量分析問題均可納入最短路徑研究的范疇，各種網(wǎng)絡(luò)分析技術(shù)實現(xiàn)的關(guān)鍵在于網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的建立和高效的最短路徑算法。

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

3.2基于BGL的最短路徑的實現(xiàn)

利用BGL實現(xiàn)最短路徑的基本步驟如下:1)構(gòu)造網(wǎng)絡(luò)圖結(jié)構(gòu)。利用BGL提供的模板可以定義各種網(wǎng)絡(luò)圖結(jié)構(gòu)，可以在這些模板的基礎(chǔ)上創(chuàng)建自己的類型，如下所示即定義了一個基于鄰接表的無向圖結(jié)構(gòu)，且其邊的權(quán)值(邊的屬性)為雙精度浮點性。typedefadjacency_list<listS，vecS，undi-rectedS，no_property，property<edge_weight_t，double>>graph_t;2)創(chuàng)建網(wǎng)絡(luò)圖實例。//首先定義網(wǎng)絡(luò)節(jié)點和邊。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);從網(wǎng)絡(luò)數(shù)據(jù)文件或數(shù)據(jù)庫中得到網(wǎng)絡(luò)圖的拓?fù)鋽?shù)據(jù)，并循環(huán)插入: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)得到路徑分析結(jié)果。//得到最短路徑鏈段:vertex_descriptorvv=goal;while(p[vv]!=vv){vv=p[vv];…;}vv=vertex(goal，g);//得到最短路徑的長度:doublefLentgh=d[vv]3.3試驗結(jié)果與分析利用Boost庫，建立一個獨立于系統(tǒng)之外的地理網(wǎng)絡(luò)分析軟件包，隨著Boost的更新而更新(僅僅可以通過替換Boost的動態(tài)鏈接庫及其相應(yīng)頭文件即可)。該軟件包已經(jīng)應(yīng)用于軍隊及地方的很多重大課題，取得很好的效果。同時，為保證軟件包應(yīng)用的穩(wěn)定性、可靠性以及對其實際應(yīng)用性能進(jìn)行檢驗，作者在基于PentiumIII700MH和256M內(nèi)存的微機上，對于27619個節(jié)點和36066條邊的某地區(qū)的實際道路網(wǎng)進(jìn)行單對節(jié)點間的最短路徑分析，其運行時間一般為3s，運行以后的效果如圖1所示。根據(jù)應(yīng)用和試驗效果以及對BGL源代碼的分析可以得到，Boost圖庫的算法是高效和易用的，利用Boost圖庫完全可以滿足GIS中地理網(wǎng)絡(luò)分析的應(yīng)用。可提高系統(tǒng)開發(fā)效率，而且最新的BGL還提供了基于圖結(jié)構(gòu)的并行算法，可以滿足未來地理網(wǎng)絡(luò)分析中海量數(shù)據(jù)分析的需要。圖1最短路徑分析的運行效果

4結(jié)束語

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