BGL的用途是给某些图的结构提供接口，而隐藏其内部细节
不需要built，但是编译程序一定要--optimized
三种方式得到STL：
- 算法/数据结构
每种算法都以数据结构无关的方式写，允许在不同类的容器中使用。代码量为O（m+n），m是算法数，n是容器数。 - 函数对象扩展
用户可以通过函数对象自行修改STL。 - 元素类型参数化
像std：：list<T>，
BGL采用了类似STL的方式 - 算法/数据结构互通
首先，将BGL的图形算法写入一个可以抽出特定图形数据结构细节的接口。 像STL一样，BGL使用迭代器来定义数据结构遍历的接口。 有三种不同的图形遍历模式：遍历图形中的所有顶点，遍历所有边缘，并沿着图形的相邻结构（从顶点到其每个邻居）。 每个遍历模式都有独立的迭代器
该通用接口允许诸如breadth_first_search（）之类的模板函数可以处理各种图形数据结构，从使用指针链接节点的图形到以数组编码的图形。 这种灵活性在图形领域尤为重要。 图形数据结构通常是针对特定应用程序定制的。 传统上，如果程序员想要重用算法实现，他们必须将它们的图形数据转换/复制到图形库的规定的图形结构中。 图书馆如LEDA，GTL，Stanford GraphBase; 在Fortran中编写的图形算法尤其如此。 这严重限制了图形算法的重用。
相比之下，使用外部自适应的BGL通用图形算法可以按照原样使用定制（或甚至遗留的）图形结构（参见“如何将现有图形转换为BGL”）。 外部自适应围绕数据结构包装一个新界面，而不需要复制，而不将数据放在适配器对象内。 BGL界面经过精心设计，使之适应性变得容易。 为了证明这一点，我们在BGL图算法中建立了使用各种图形结构（LEDA图，Stanford GraphBase图，甚至Fortran样式阵列）的接口代码。 - 通过访客实现扩展
BGL的图算法是可扩展的。 BGL引入了一个访问者的概念，它只是一个具有多种方法的函数对象。 在图形算法中，通常有几个关键的“事件点”可用于插入用户定义的操作。 访问对象具有在每个事件点调用的不同方法。 特定的事件点和相应的访问者方法取决于具体的算法。 它们通常包括start_vertex（），discover_vertex（），inspect_edge（），tree_edge（）和finish_vertex（）等方法。 - 顶点和边缘属性多参数化
BGL通用的第三种方法类似于STL容器中的元素类型的参数化，但是对于图形来说，故事再复杂一些。 我们需要将值（称为“属性”）与图形的顶点和边缘相关联。 另外，通常需要将多个属性与每个顶点和边缘相关联; 这是我们通过多参数化的意思。 STL std :: list <T>类的元素类型有一个参数T。 类似地，BGL图类具有顶点和边缘“属性”的模板参数。 属性指定属性的参数化类型，并为属性分配标识标签。 该标签用于区分边缘或顶点可能具有的多个属性。 附加到特定顶点或边缘的属性值可以通过属性映射获取。 每个属性都有一个单独的属性映射。
传统图形库和图形结构在图形属性的参数化方面下降。 这是图表数据结构必须为应用程序定制的主要原因之一。 BGL图类中属性的参数化使它们非常适合重复使用。
算法
核心算法模式和一系列图算法：
核心算法模式：
- Breadth First Search
- Depth First Search
- Uniform Cost Search
BGL不会用核心算法模式在图上计算数值，只是为图算法构建块。而图算法包括以下： - Dijkstra's Shortest Paths
- Bellman-Ford Shortest Paths
- Johnson's All-Pairs Shortest Paths
- Kruskal's Minimum Spanning Tree
- Prim's Minimum Spanning Tree
- Connected Components
- Strongly Connected Components
- Dynamic Connected Components (using Disjoint Sets)
- Topological Sort
- Transpose
- Reverse Cuthill Mckee Ordering
- Smallest Last Vertex Ordering
- Sequential Vertex Coloring
数据结构
提供两种图类型一种边列表适配器
邻接表；邻接矩阵；边列表；
其中最通用的是邻接表；高度参数化，可以针对不同情况优化
int main(int,char*[])
{
// create a typedef for the Graph type
typedef adjacency_list<vecS, vecS, bidirectionalS> Graph;//使用vector来存出边和顶点集的数据结构，双向
// Make convenient labels for the vertices
enum { A, B, C, D, E, N };
const int num_vertices = N;
const char* name = "ABCDE";
// writing out the edges in the graph
typedef std::pair<int, int> Edge;
Edge edge_array[] =
{ Edge(A,B), Edge(A,D), Edge(C,A), Edge(D,C),
Edge(C,E), Edge(B,D), Edge(D,E) };
const int num_edges = sizeof(edge_array)/sizeof(edge_array[0]);
// declare a graph object
Graph g(num_vertices);
// add the edges to the graph object
for (int i = 0; i < num_edges; ++i)
add_edge(edge_array[i].first, edge_array[i].second, g);
...
return 0;
}
除了使用add_edge()接口，也可以使用迭代器：
Graph g(edge_array, edge_array + sizeof(edge_array) / sizeof(Edge), num_vertices);`
此外，点数也是不固定的，可以使用 add_vertex() & remove_vertex()
边集访问：edges()返回的迭代器，source()和target()为被该边连接的点
int main(int,char*[])
{
// ...
std::cout << "edges(g) = ";
graph_traits<Graph>::edge_iterator ei, ei_end;
for (boost::tie(ei, ei_end) = edges(g); ei != ei_end; ++ei)
//tie接口将返回的pair分离为两个变量。在本例中为ei和ei_end;
std::cout << "(" << index[source(*ei, g)]
<< "," << index[target(*ei, g)] << ") ";
std::cout << std::endl;
// ...
return 0;
}
邻接结构：
std::for_each(vertices(g).first, vertices(g).second, exercise_vertex<Graph>(g));
使用 exercise_vertex是为了在运行遍历时保留对图像的引用。将其模板化以便在不同的图类型中重用
顶点描述符是由每个图形类型提供的，可用于通过以下部分中描述的out_edges（），in_edges（），adjacent_vertices（）和属性映射函数来访问有关图形的信息。 vertex_descriptor类型通过graph_traits类获得。下面使用的typename关键字是必需的，因为scope :: operator（graph_traits <Graph>类型）左侧的类型取决于模板参数（Graph类型）。这是我们如何定义函子的应用方法：
template <class Graph> struct exercise_vertex {
//...
typedef typename graph_traits<Graph>
::vertex_descriptor Vertex;
void operator()(const Vertex& v) const
{
//...
}
//...
};
边描述：out_edges()函数，两个参数：定点和图对象。返回pair迭代器，提供该顶点所有出边的接口，出边迭代器dereference其中之一给出边描述符对象。（类似顶点描述符）
template <class Graph> struct exercise_vertex {
//...
void operator()(const Vertex& v) const
{
typedef graph_traits<Graph> GraphTraits;
typename property_map<Graph, vertex_index_t>::type index = get(vertex_index, g);
std::cout << "out-edges: ";
typename GraphTraits::out_edge_iterator out_i, out_end;
typename GraphTraits::edge_descriptor e;
for (boost::tie(out_i, out_end) = out_edges(v, g);
out_i != out_end; ++out_i) {
e = *out_i;
Vertex src = source(e, g), targ = target(e, g);
std::cout << "(" << index[src] << ","
<< index[targ] << ") ";
}
std::cout << std::endl;
//...
}
//...
};
in_edges()与之类似，（前提是双向图，且仅用于邻接表结构）
有时，算法不需要查看图形的边，只关心顶点。 因此，图形界面还包括AdjacencyGraph接口的adjacent_vertices（）函数，它提供对相邻顶点的直接访问。 此函数返回一对邻接迭代器。 dereference邻接迭代器给出相邻顶点的顶点描述符。
涂色：加权。由于一般一个算法只用到一个属性,因此属性和图对象应当分别存储.属性有两类:内部存储属性/外部存储属性.内部属性通常采用模板插件,外部属性方法较多.直接存储的方法:点或者边映射的映射.对于vecS(即vector,参见某章),这种映射型容器会自己分配索引,用vertex_index_t来查找,而边不可以(废话太多了不就加个索引么)
用访问者扩展算法
一般来讲lib中的算法足够使用,但很有可能不完全相同.比如Dij算法通常记录最短距离,但是有可能我们需要用到最短路径树.一种方法是在最短路径树中记录每个节点的前导.
在STL中,这种计算通过functor实现.这是每个算法的可选参数.在BGL中这个由游客来实现.一个游客就是一个functor,它有多种方法被调用
(会在vistor章节详细介绍.)每一个方法都可以在算法的某一个点被调用.BGL提供了一些常用任务的访问者.可以自己创建BGL到visitor,本处先介绍前缀记录的实现和使用.以Dijkstra为例,创建一个Dijkstra visitor
前缀记录访问者的功能分为两部分.为了存储可访问前缀属性,我们使用属性映射.而后,前缀访问者只对要记录的父负责.创建了一个record_predecessor属性类及模板在前缀属性映射上,由于这个访问者只有一种方法,我们继承dijkstra_visitor,为其余提供空白方法.构造函数将使用属性映射对象并将其保存在数据成员中.
回顾:m_开头说明是类成员变量,构造函数的意图是把p存进m_这个protected里去.
然后又是一个模板函数
template <class PredecessorMap>
class record_predecessors : public dijkstra_visitor<>
{
public:
record_predecessors(PredecessorMap p)
: m_predecessor(p) { }
template <class Edge, class Graph>
void edge_relaxed(Edge e, Graph& g) {
// set the parent of the target(e) to source(e)
put(m_predecessor, target(e, g), source(e, g));
}
protected:
PredecessorMap m_predecessor;
};
将source记录为目标顶点的前身,每次relax时覆盖之前的值,使用put来记录前缀.访客的edge_filter通知算法什么时候启用explore(),该情况下我们只在最短路径树中通知边所以制定tree_edge_tag.
为了方便的创建前缀访问,启用helper如下
//类模板外函数？总之定义了make_,返回了record_的结果
template <class PredecessorMap>
record_predecessors<PredecessorMap>
make_predecessor_recorder(PredecessorMap p) {
return record_predecessors<PredecessorMap>(p);
}
现在可以像下文一样使用:
vector<Vertex> p(num_vertices(G), graph_traits<G>::null_vertex());
//容器(大小,迭代器)
dijkstra_shortest_paths(G, s, distance_map(&d[0]).
visitor(make_predecessor_recorder(&p[0])));
//计算最短路径,添加visitor并存储 参数是数组的位置
cout << "parents in the tree of shortest paths:" << endl;
for(vi = vertices(G).first; vi != vertices(G).second; ++vi) {
cout << "parent(" << *vi;
if (p[*vi] == graph_traits<G>::null_vertex())
cout << ") = no parent" << endl;
else
cout << ") = " << p[*vi] << endl;
}
邻接矩阵：一般用于密集图表
边列表：可以使用任意边迭代和实现
网友评论