`
utensil
  • 浏览: 152373 次
  • 性别: Icon_minigender_1
  • 来自: 深圳
社区版块
存档分类
最新评论

[翻译]Boost Graph库简介

阅读更多
转载请注明:
作者:Utensil
博客:http://utensil.iteye.com/
邮箱:utensilcandel@gmail.com

本章为Boost Graph Library的在线文档的第一章(参见http://www.boost.org/doc/libs/1_36_0/libs/graph/doc/table_of_contents.html )。前段时间研究编译原理中的属性计算时,看到拓扑排序,突然对Boost中的这个库有了兴趣,就翻译了这篇简介。

Boost 图类库(BGL)

图(graph)是一种数学抽象,可用于解决计算机科学领域的多种问题。因此,这种抽象必须也由计算机程序表达出来。一个用于遍历图的标准化的范型接口,对于促进对图算法和数据结构的重用,具有无可比拟的重要性。Boost 图类库(BGL)的一部份是一个可用于访问图的结构的范型接口,同时隐藏了其实现细节。这是一个开放的接口,这意味着任何实现了该接口的图类库,都将可以与BGL范型算法(或是其他使用了该接口的算法)相互协作。BGL提供了一些遵循该接口的通用目的的图类,但它们并不企图成为唯一的图类;肯定会有其他图类更适合于特定场合。我们相信,BGL的主要贡献将是对该接口的规划。
BGL图接口和图组件是范型的(generic ),如同标准模板库(STL)[2 ]。在下一节中我们将回顾范型编程在STL中扮演的角色,并将其与我们如何在图的背景下应用范型编程相比较。
当然,如果你已经熟悉范型编程,大可以跳过这一节!这里是目录
BGL的源代码是Boost分发包的一部份,你可以在这里 下载。

如何构建BGL

 

根本不用! Boost 图类库是一个仅有头文件(header-only)的类库,并不需要构建后才能使用。唯一的例外是GraphViz输入分析器
当编译使用BGL的程序时,记住开启优化 。例如,在Microsoft Visual C++中选择Release模式,或给GCC加上-O2或-O3选项。

STL中的范型

 

STL以三种方式体现出它是范型的。

Algorithm/Data-Structure Interoperability

算法/数据结构互操作性

首先,每个算法都是以一种数据结构中性的方式写成的,允许一个单独的模板函数在许多不同类型的容器施行操作。迭代器的概念是降低算法和数据结构耦合程度的关键因素。这项技术的影响在于将STL的代码规模从O(M*N) 降低到O(M+N) ,其中是M 算法的数量而N 是容器的数量。考虑有20种算法和5种数据结构的情形,这将是写100个函数与仅写25个函数的区别!而且这种区别将随着算法和数据结构数目的增多而变得更大。

 

Extension through Function Objects

可扩展性(通过函数对象)

其次,STL的算法和数据结构是可扩展的。通过使用函数对象,用户可以改造和定制STL。正是这种弹性使得STL成为解决现实问题的优秀工具。每个编程问题都会带来它自己的实体集合和需要建模的交互。函数对象提供了这样一种机制来扩展STL使其能处理每个问题领域的细节。

 

Element Type Parameterization

元素类型的参数化

第三,STL容器的元素类型是参数化的。虽然这点非常重要,但它可能是最不有趣的一种方式。范性编程常常被简单地总结为参数化的列表,如std::list<T> 。这仅仅挠到了问题的皮毛!

 

Boost Graph库中的范型

 

如同STL,BGL也以三种方式体现出它是范型的。

Algorithm/Data-Structure Interoperability

算法/数据结构互操作性

首先,BGL的图算法是按照一个抽象掉了特定的图结构的细节的接口写成的。和STL一样,BGL使用迭代器来定义数据结构遍历的接口。有三种不同的图遍历模式:遍历图的所有顶点,经过所有的边,以及沿着图的邻接结构(从一个顶点到它的邻居)。对每一种遍历模式,都有一种专门的迭代器。
该范型接口使得像breadth_first_search() 这样的模板函数可以工作于多种多样的图结构之上,无论是以指针链接的节点实现的图,还是编码在数组里的图。这种弹性对于图论领域尤其重要。图结构常常是为特定的应用定制的。在以前,如果程序员想要重用一个算法实现他们必须将他们的图数据转换/复制到图类库的规定的图结构。在使用像LEDA, GTL, Stanford GraphBase这样的库的时候,正是这样;对于用Fortran写成的图算法,就更是如此。这严重地限制了它们的图算法的重用。
相反,通过外部适配(external adaptation, 参见小节如何将既有的图转换为BGL ),定制的(或者甚至是遗留的)图结构可以原封不动地与BGL范型图算法共同使用。外部适配将一个新的接口包裹在一个数据结构外面,无需复制,也无需将数据放在适配对象里。BGL的接口经过仔细的设计,以使这个适配的过程尽可能简单。为了演示这一点,在BGL图算法中,我们为多种图结构(LEDA图、Stanford GraphBase图,甚至 Fortran风格的数组)构建了接口连接代码。

 

Extension through Visitors

可扩展性(通过Visitor)

其次,BGL的图算法是可扩展的。BGL引入了visitor (访问子)的概念,其实它只是一个有多个方法的函数对象。在图算法中,常常需要在一些关键点(event points )插入用户定义的操作。访问子对象有一个不同的、只在关键点才调用的方法。具体的关键点以及相应的访问子方法依具体的算法而定。它们通常包括像start_vertex() , discover_vertex() , examine_edge() , tree_edge() , and finish_vertex()这样的方法。

 

Vertex and Edge Property Multi-Parameterization

顶点和边属性的多重参数化

BGL的第三种范型方式,类似于STL容器中的元素类型的参数化,可是情况比STL容器要复杂一些。我们既需要将值(称为“属性”)关联于图的顶点,也需要关联于边。另外,常常需要将多重属性关联于每个顶点和每条边;这正是所谓的多重参数化。STL的std::list<T> 类有一个参数T指定它的元素类型。相似地,BGL图类有对应于顶点和边的属性的模板参数。一个属性参数 指定属性的参数化的类型,同时给该属性分派一个识别标签。这个标签用于区分开一个顶点或边所具有的多个属性。关联于一个特定的顶点或边的 属性值,可以经由一个属性映射表(property map )获得。对每一个属性,都有一张单独的属性映射表。
传统的图库和图结构会在遇到图属性参数化时变得无能为力。这是图结构必须为具体应用定制的一个主要原因。BGL中的图类中属性的参数化使得它们非常适合于重用。

 

Algorithms 算法

 

BGL算法包括一个算法模式(实现为范型算法)的核心集合,以及大量的图算法。核心的算法模式有:

 

  • 广度优先搜索(Breadth First Search )
  • 深度优先搜索(Depth First Search )
  • 成本一致搜索(Uniform Cost Search )
这些算法模式自身并不对图计算任何有意义的量;他们仅仅为构造图算法建筑基石。BGL中现有的图算法包括:
  • Dijkstra最短路径(Dijkstra's Shortest Paths)
  • Bellman-Ford最短路径(Bellman-Ford Shortest Paths)
  • Johnson所有节点对间最短路径(Johnson's All-Pairs Shortest Paths)
  • Kruskal最小生成树(Kruskal's Minimum Spanning Tree)
  • Prim最小生成树(Prim's Minimum Spanning Tree)
  • 连通区域(Connected Components)
  • 强连通区域(Strongly Connected Components)
  • 动态连通区域(使用不相交集合)(Dynamic Connected Components (using Disjoint Sets) )
  • 拓扑排序(Topological Sort)
  • 转置(Transpose)
  • 逆Cuthill Mckee排序(Reverse Cuthill Mckee Ordering)
  • 最小最后顶点排序(Smallest Last Vertex Ordering)
  • 顺序顶点染色(Sequential Vertex Coloring)

 

Data Structures 数据结构

 

BGL目前提供两个图类和一个边链表适配器。
adjacency_list类是通用目的的,是图类中的瑞士军刀。它是高度参数化的,因此它可以为不同场合进行优化:图是有向的还是无向的,是否允许平行边,只可以高效访问出边还是也可高效访问入边,快速顶点插入与删除的额外空间开销等等。

adjacency_matrix将边储存在一个|V| x |V| 矩阵中(其中|V| 是顶点数)。这个矩阵的元素代表图中的边。邻接矩阵表示特别适合于非常密集的图,即边的数目接近|V|2

edge_list类是一个适配器,它接受任何类型的边迭代器实现一个边链表图( E dge List Graph )。
分享到:
评论
1 楼 听说名字可以很长 2013-12-15  

相关推荐

    Boost Graph库简介.pdf

    "Boost Graph库简介" Boost Graph库(BGL)是Boost C++ Libraries中的一部分,提供了一种标准化的图遍历接口,用于解决计算机科学领域的多种问题。该库提供了一个可用于访问图结构的范型接口,同时隐藏了其实现细节...

    Boost Graph库简介.docx

    【Boost Graph库简介】 Boost Graph Library (BGL) 是一个强大的C++库,专注于图的抽象和算法。它提供了一套通用的接口和组件,使得程序员可以方便地使用各种图结构,而无需关心具体实现的细节。BGL的灵活性允许...

    Boost Graph库简介 (2).pdf

    Boost Graph 库简介 Boost Graph 库(BGL)是一个专门用于图计算的库,它提供了一个标准化的范型接口,用于遍历图和访问图结构。该库的主要贡献是对该接口的规划,隐藏了实现细节,提供了一个开放的接口,使得任何...

    Boost Graph库简介 (2).docx

    【Boost Graph库简介】 Boost Graph Library (BGL) 是一个强大的C++库,专注于图的抽象和算法。它提供了一套通用的接口和组件,使得程序员可以方便地使用各种图结构,而无需关心具体实现的细节。BGL的灵活性允许...

    Boost Graph Library: The User Guide and Reference Manual(解密pdf)

    Boost图形库是Boost库的一部分,它是一个广泛使用的C++库,旨在为图论算法提供高效的实现。 在详细地介绍这本书之前,我们需要先了解几个关键概念。首先,“图形”在这里指的是一个抽象数学概念,它由顶点...

    Boost Graph Library:The User Guide and Reference Manual.pdf

    1. Boost Graph Library(BGL)是一个为C++语言设计的图论库。这个库提供了一系列的数据结构和算法,专门用于图的表示和处理。图是一种数据结构,它由节点(也称为顶点)和连接这些节点的边组成,常用于建模网络、...

    the boost graph library.pdf

    boost graph说明文档

    Boost Graph Library

    Boost Graph Library(简称 BGL)是一个基于 C++ 的图形处理库,它提供了丰富的图形算法实现,使得用户能够方便地对图形数据进行操作与分析。BGL 是 Boost 库的一部分,Boost 库是 C++ 社区中一个非常著名的开源项目...

    boost graph library

    boost graph library

    Boost Graph Library快速入门

    Boost Graph Library (BGL) 是一个功能强大且灵活的库,旨在提供高级图形算法和数据结构。与STL的抽象迭代器接口相比,BGL针对图领域设计了更加专用的接口,能够更有效地处理图中的复杂路径和操作。本文将深入探讨...

    Boost C++ 库 简介(中文)

    Boost库不仅在学术界受到广泛认可,在工业界也被广泛应用,成为许多其他软件项目的基础,比如C++标准库的部分内容。 Boost库包含的组件多种多样,涵盖了算法、数据结构、模板元编程、并行计算、图形算法、字符串...

    Matlab_Boost_Graph_Library工具箱.rar

    《Matlab_Boost_Graph_Library工具箱》是专为MATLAB用户设计的一个扩展库,旨在帮助用户在MATLAB环境中处理复杂网络问题。这个工具箱结合了Boost Graph Library(BGL)的强大功能,使得MATLAB用户能够利用C++库的...

    Boost程序库完全开发指南

    Boost库中的内容主要由C++标准委员会库工作组的成员开发,并被广泛地接受为未来C++标准的一部分。 这本书详细介绍了Boost中的关键库,比如: 1. **Boost.Asio**:用于网络和低层I/O编程的库,广泛应用于网络服务端...

    Boost Graph Library:User Guide and Reference Manual

    Boost Graph Library是Boost库中的一个C++图形处理库,它提供了丰富的图论算法和数据结构,适用于多种不同的图的表示和操作。这本书不仅包含了用户指南,还提供了详尽的参考手册,是学习和使用Boost Graph Library不...

    boost graph library user guide and reference manual

    Boost Graph Library(BGL)是Boost库中的一个子项目,旨在提供一套高效、灵活且易于使用的图算法实现。它由Jeremy Siek、Lie-Quan Lee和Andrew Lumsdaine等人共同开发完成,并于2002年由Pearson Education出版了...

    C++ boost库,最新版本

    Boost库由Boost社区组织开发、维护。其目的是为C++程序员提供免费、同行审查的、可移植的程序库。Boost社区的发起人Dawes本人就是C++标准委员会的成员之一。大部分boost库功能的使用只需包括相应头文件即可,少数...

    Boost程序库完全开发指南_深入Cpp.准标准库及库详解

    《Boost程序库完全开发指南》是一本深度探索C++编程领域的权威著作,专注于介绍Boost库这一强大工具集。Boost库是C++社区公认的高质量、跨平台的开源库,它为C++程序员提供了许多实用的工具,包括算法、数据结构、...

    Boost程序库探秘——深度解析C++准标准库

    数学和算法方面,Boost库包含了如Boost.Graph、Boost.Random等组件。Boost.Graph提供了图数据结构和算法,适用于解决各种复杂的网络问题;Boost.Random提供了高质量的随机数生成器,满足科学研究和模拟仿真等领域的...

    A graph library for Matlab based on the boost graph library.zip

    标题 "A graph library for Matlab based on the boost graph library" 提供了一个关键信息,即这是一个针对Matlab环境开发的图库,其设计灵感来源于著名的C++图形库Boost Graph Library(BGL)。Boost BGL是一个...

Global site tag (gtag.js) - Google Analytics