请按任意键继续...

  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  21 随笔 :: 0 文章 :: 2 评论 :: 0 Trackbacks

1, 泛型接口:语法、语用、时空间复杂度, 而不仅是一个函数

2, 分别用vertex edge descriptor 处理 点和边, 且可被graph_traits 类访问, 仅定义了最基本的类操作

3, Source(e, g) target(e, g)分别 veretx_descriptor 类型的源和终点

4, 图模型可以解决很多现实问题是因为点和边可以表示很多对象和性质(property),用property map 概念来描述, 类似于STLmap,key value.有三个函数:get(p_map, key), put(p_map, k, v), p_map[k],

5, 图的抽象结构主要由集合vertices ,edges(相对于图) out_edges,   in_edges, adjacent vertices(相对于点)组成。对应五个集合有五种迭代器:vertex iterator(解引用为vertex descriptor), edge iterator(edge descriptor),  out-edge iterator, in-edge iterator, adjacent iterator.这些迭代器和descriptor 一样可被graph_traits<Graph> 访问。

6, Std::pair<iter, iter>接受一对迭代器,如stl分别表示上边五个集合的范围。Vertices(g) 返回边的范围。使用在boost/tuple/tuple.hpp定义的tiefirst, last= edges(g)可绑定范围.类似的,out_edge(s, g), in_edge(t, g), adjacent_verties(s, g) 可返回相应集合范围的一对iterator

7, Add_vertex(g):返回verex_descriptor, add_edge(vS, vT, g):返回pair<edge_descriptor, bool>

8, Algorithm visitor: 类似于Stl algorithm 中使用的函数对象,提供定制算法的可能,但有多个函数对象(multiple funtor,是通过event points实现的

9, Graph type 有两种:graph classes(用内存来存放图) graph adaptors(用其它类型的行为来创建图的接口)

10,    图类类型有基本的两种:adjacency_matrix(用于稠密图) adjacency_list(主要的,存储点集合,点结构里有出边对象集合, 模板参数有:EdgeList, VertexList, Directed, VertexProperties, EdgePropertiesGraphProperties), 点和边的类型影响图的增删操作。

11,  图适配器类型有revese_graph, filtered_graph

12, 和STL一样,BGL的算法也是泛型实现

posted on 2012-10-26 14:23 星哥 阅读(312) 评论(0)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理