简析开源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类库为基于地理网络的空间分析提供了一个新的解决框架，可以帮助用户模拟现实世界中的网络条件与情景。这使得程序设计代码更加简洁，改进程序性能，同时使程序员花费更少的时间重写相同的代码，为不同过程提供更好的可复用性、封装性和互操作性，便于程序维护和扩展。