 |
圖數據結構和算法在某些方面比它們的容器更加複雜。STL中使用的抽像迭代器不能完全適用於圖算法中的各種遍歷方法。因此，我們專門有一個抽像接口給圖使用，該接口就像基本容器中的迭代器（迭代器仍然佔有很重要的角色）。為此，圖1對BGL和STL做了比較。
圖的抽像表示是由一組頂點（或稱：節點）和一組鏈接頂點的邊（或稱：弧）組成的。 圖2 表示的是一個由5個頂點（標號：0－4）和11條邊組成的有向圖。從一個頂點出去的邊叫做該頂點的出邊。邊{(0,1),(0,2),(0,3), (0,4)}全都是頂點0的出邊。進入一點的邊叫做該點的入邊。邊{(0,4),(2,4),(3,4)}全都是頂點4的入邊。
在接下去的部分中，我們將會用BGL來構建這個例子，並且用多種方法去操作它。這個例子的全部代碼在 examples/quick_tour.cpp文件中。接下去的每部分將會討論該例子文件中的程序片段。程序的輸出內容我們也會列出來。
在該例中我們將使用BGL的 adjacency_list 類來示範一下BGL接口的主要思想。adjacency_list 類給傳統的「鄰接列表」數據結構提供了一個范型版本。adjacency_list 是一個有六個參數的模版類，在該例中我們只使用前三個參數，其餘三個參數都用默認值。前兩個模版參數（vecS，vecS）分別表示每個頂點出邊集合的數據 結構和圖中頂點集合的數據結構（參考：邊列表和頂點列表的選擇 ：不同數據結構的折中方案）。第三個參數：bidirectionalS，它表示一個既有出邊也有入邊的有向圖。第三個參數另外的選項是：directedS，它表示選擇一個僅有出邊的有向圖；undirectedS 表示一個無向圖。
一旦我們確定了圖的類型，我們就能夠創建 圖2 表示的圖了，首先聲明一個圖對象，然後用MutableGraph接口（它是adjacency_list實現的）中的add_edge() 函數來添加圖中的邊。在這個例子中，我們使用一對edge_array 數組僅僅是為了能夠簡單直接的創建邊。
#include <iostream> // for std::cout
#include <utility> // for std::pair
#include <algorithm> // forstd::for_each
#include <boost/graph/graph_traits.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/dijkstra_shortest_paths.hpp>
using namespace boost;
int main(int,char*[])
{
// typedef圖類型
typedef adjacency_list<vecS, vecS, bidirectionalS> Graph;
// 便於標記各頂點
enum { A, B, C, D, E, N };
const int num_vertices = N;
const char* name = "ABCDE";
// 表示圖中的邊
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]);
// 聲明一個圖對像
Graph g(num_vertices);
// 給圖對像增加邊
for (int i = 0; i < num_edges; ++i)
add_edge(edge_array[i].first, edge_array[i].second, g);
...
return 0;
}
我們可以使用 edge iterator constructor來替代add_edge() 函數，該函數比add_edge()函數更有效率。edge_array 中的指針可以被看作是迭代器，所以我們可以用該數組中的頭元素和尾元素來創建一個迭代器。
Graph g(edge_array, edge_array + sizeof(edge_array) / sizeof(Edge), num_vertices);
可以用add_vertex() 函數和remove_vertex() 函數來增加、刪除頂點的方法來替換創建圖的時候就帶固定頂點個數的方法，那兩個函數也是 MutableGraph接口中的。
現在我們已經建立了一個圖，我們可是通過相關圖接口使用各種方法來訪問圖中數據。首先，我們可以使用 VertexListGraph接口中的vertices()函 數來訪問圖中各頂點。該函數函數返回一個頂點迭代器對(std::pair of vertex iterators)(第一個iterator指向頂點的開始元素，第二個迭代器指向最後元素的下一位置)，通過一個頂點迭代器來間接引用一個頂點對象。 頂點迭代器的類型在graph_traits類中給出。注意：不同的圖類跟不同的頂點迭代器相關聯，這就是需要graph_traits類的原因。給定正 確的圖類型，graph_traits類就能給出正確的vertex_iterator類型。
下面的例子打印出圖中每個頂點的序號。所有頂點和邊的屬性，包括序號在內，全都通過屬性映射（property_map）對像訪問。property_map類被用來得到具體的屬性（比如：vertex_index_t，它是BGL預定義的一個屬性）或者通過調用具體函數得到相關的屬性映射對象。
// ...輸出是：
int main(int,char*[])
{
// ...
// 得到頂點索引的屬性映射
typedef property_map<Graph, vertex_index_t>::type IndexMap;
IndexMap index = get(vertex_index, g);
std::cout << "vertices(g) = ";
typedef graph_traits<Graph>::vertex_iterator vertex_iter;
std::pair<vertex_iter, vertex_iter> vp;
for (vp = vertices(g); vp.first != vp.second; ++vp.first)
std::cout << index[*vp.first] << " ";
std::cout << std::endl;
// ...
return 0;
}
vertices(g) = 0 1 2 3 4
圖中邊集合能夠通過EdgeListGraph接口的edges()函數訪問。與vertices()函數類似，該函數也返回一個迭代器對，不過這次返回的是邊迭代器(edge iterators)，通過邊迭代器對像能夠訪問到邊對象。source()函數和target()函數返回鏈接一條邊的首、尾頂點。這次我們用tie()輔助函數來替換std::pair迭代器對，這個函數把std::pair中的兩部分拆分到了兩個變量當中去，本例中是ei和ei_end。這種方法比創建std::pair更簡單，所以在BGL中我們經常使用這種方法。
// ...輸出是：
int main(int,char*[])
{
// ...
std::cout << "edges(g) = ";
graph_traits<Graph>::edge_iterator ei, ei_end;
for (tie(ei, ei_end) = edges(g); ei != ei_end; ++ei)
std::cout << "(" << index[source(*ei, g)]
<< "," << index[target(*ei, g)] << ") ";
std::cout << std::endl;
// ...
return 0;
}
edges(g) = (0,1) (0,2) (0,3) (0,4) (2,0) (2,4) (3,0)
(3,1) (3,4) (4,0) (4,1)
//...我們使用仿函數－－exercise_vertex來替代一般的函數，因 為我們存取頂點信息的時候需要圖對象，使用仿函數能夠在執行std::for_each()期間一直引用圖對象。並且，我們使用模版函數來定義圖類型，這 樣能夠在不同圖類的情況下復用代碼。下面是exercise_vertex仿函數的開始部分：
int main(int,char*[])
{
//...
std::for_each(vertices(g).first, vertices(g).second,
exercise_vertex<Graph>(g));
return 0;
}
template <class Graph> struct exercise_vertex {
exercise_vertex(Graph& g_) : g(g_) {}
//...
Graph& g;
};
template <class Graph> struct exercise_vertex {
//...
typedef typename graph_traits<Graph>
::vertex_descriptor Vertex;
void operator()(const Vertex& v) const
{
//...
}
//...
};
通過IncidenceGraph接口的out_edges()函數能夠訪問一個頂點的出邊。out_edges()函 數有2個參數：第一個參數是該出邊所對應的頂點，第二個參數是邊所在的圖對象。這個函數提供一個迭代器對，這個迭代器對允許訪問該頂點的所有出邊(與 vertices()函數返回一個迭代器對相類似)。這個迭代器叫做「出邊迭代器」(out-edge iterators)，能夠通過某個迭代器得到對應的邊描述符(edge descriptor)對象。一個邊描述符起到的作用和頂點描述符相類似，它是一個由圖提供的黑盒。
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 (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;
//...
}
//...
};
頂點0的輸出:
out-edges: (0,1) (0,2) (0,3) (0,4)
BidirectionalGraph接口的in_edges()函數通過入邊迭代器訪問一個頂點所有的入邊。in_edges()函數僅當bidirectionalS作為adjacency_list的模版參數的時候才有效。相對於單向圖，雙向圖佔用更多的空間。
template <class Graph> struct exercise_vertex {
//...
void operator()(const Vertex& v) const
{
//...
std::cout << "in-edges: ";
typedef typename graph_traits<Graph> GraphTraits;
typename GraphTraits::in_edge_iterator in_i, in_end;
for (tie(in_i, in_end) = in_edges(v,g);
in_i != in_end; ++in_i) {
e = *in_i;
Vertex src = source(e, g), targ = target(e, g);
std::cout << "(" << index[src] << "," << index[targ] << ") ";
}
std::cout << std::endl;
//...
}
//...
};
頂點0的輸出:
in-edges: (2,0) (3,0) (4,0)
給定一個頂點的出邊，該邊的目標頂點就是源頂點的相鄰頂點。有時候，一個算法不關心圖中的邊而是僅需關心圖中頂點。因此，圖接口中提供了AdjacencyGraph接口，該接口中的 adjacent_vertices()函數能夠直接訪問頂點的相鄰頂點。這個函數返回一個鄰接迭代器對，通過間接引用鄰接迭代器能夠得到鄰接頂點的頂點描述符。
template <class Graph> struct exercise_vertex {
//...
void operator()(Vertex v) const
{
//...
std::cout << "adjacent vertices: ";
typename graph_traits<Graph>::adjacency_iterator ai;
typename graph_traits<Graph>::adjacency_iterator ai_end;
for (tie(ai, ai_end) = adjacent_vertices(v, g);
ai != ai_end; ++ai)
std::cout << index[*ai] << " ";
std::cout << std::endl;
}
//...
};
頂點4的輸出是:
adjacent vertices: 0 1
BBGL試圖盡可能靈活的提供圖的相關附屬屬性。一個屬性，比如邊的權重，可能需要貫穿圖對象的整個生命週期，因此圖對象就需要管理該屬性的存儲。 另一方面，頂點顏色屬性有可能僅在一個單獨的算法中被用到，那麼最好是把該屬性和圖對像分開存儲。前一種屬性被稱作內部存儲屬性，而第二種屬性被稱作外部 存儲屬性。BGL提供統一的機制來訪問這兩種屬性，該機制叫作：屬性影射(property map)，內部算法實現是property map接口，該接口在Property Map Concepts一章中被介紹PropertyGraph概念定義了一個接口，該接口用來訪問所得圖映射對象的內部存儲屬性。
BGL的adjacency_list類允許用戶通過圖類的模版參數規定內部存儲屬性。具體的實現在Internal Properties一 節中講解。有多種方法能夠創建外部存儲屬性，但是這些方法最終都是傳遞給圖算法一個模版參數而已。一個直觀的存儲屬性的辦法是根據點或邊的索引創建一個索 引數組。在adjacency_list類中vecS模版參數，頂點自動給它賦值對應序號，頂點序號能夠通過屬性映射得到vertex_index_t 值。邊不進行自動賦值索引值。然而屬性機制能夠被用來把索引綁定到需要把索引作為外部存儲屬性的邊上。
下面的例子中，我們使用dijkstra_shortest_paths()函數建立一個圖。這個例子的完整的源代碼在examples/dijkstra-example.cpp文件中。Dijkstra算法計算從一點到圖中其它頂點的最短路徑。
Dijkstra算法需要給邊添加一個權重屬性，並且給頂點添加一個距離屬性。這裡，我們把權重作為內部屬性，把距離作為外部屬性。我們使用屬性類來表示 權重屬性，並且規定權重的類型為整型(int)，使用edge_weight_t作為屬性標記(它是BGL預定義的一個屬性標記)。然後，權重屬性作為 adjacency_list的模版參數使用。TlistS和vecS是adjacency_list內部數據結構的類型(參考：Choosing the Edgelist and VertexList 選擇邊列表和頂點列表)。directedS類型規定了該圖必須是一個有向圖(與無向圖相對)。下面的代碼詳細說明了圖類型以及它的初始化部分。邊和權重以迭代器的被傳入圖的構造函數(一個RandomAccessIterator)。
typedef adjacency_list<listS, vecS, directedS,我們使用std::vector來存儲距離這個外部屬性。BGL處理隨機迭代器像處理屬性映射一樣，所以我們僅需傳的distance vector的開始迭代器到Dijkstra算法既可。繼續我們上面的例子，下面的代碼展示的是創建一個distance vector，以及調用Dijkstra算法(隱式的使用了內部屬性－－權重)，然後輸出結果。
no_property, property<edge_weight_t, int> > Graph;
typedef graph_traits<Graph>::vertex_descriptor Vertex;
typedef std::pair<int,int> E;
const int num_nodes = 5;
E edges[] = { E(0,2),
E(1,1), E(1,3), E(1,4),
E(2,1), E(2,3),
E(3,4),
E(4,0), E(4,1) };
int weights[] = { 1, 2, 1, 2, 7, 3, 1, 1, 1};
Graph G(edges + sizeof(edges) / sizeof(E), weights, num_nodes);
// vector為了給distance屬性排序輸出是:
std::vector<int> d(num_vertices(G));
// 得到第一個頂點
Vertex s = *(vertices(G).first);
// 調用Dijkstra算法
dijkstra_shortest_paths(G, s, distance_map(&d[0]));
std::cout << "distances from start vertex:" << std::endl;
graph_traits<Graph>::vertex_iterator vi;
for(vi = vertices(G).first; vi != vertices(G).second; ++vi)
std::cout << "distance(" << index(*vi) << ") = "
<< d[*vi] << std::endl;
std::cout << std::endl;
distances from start vertex:
distance(0) = 0
distance(1) = 6
distance(2) = 1
distance(3) = 4
distance(4) = 5
最好是不重寫Dijkstra算法，僅僅增加記錄前驅節點的代碼即可[1]。在STL中，這種擴展能力被仿函數提供，它是一個每個算法的可選參數。在BGL中扮演相同角色的是Visitor。
Visitor類似於仿函數，但是與仿函數僅有一個可用方法不同，visitor有多個方法可用。它的每個方法都能夠被算法內部預先定義好的指針調用。visitor的方法在Visitor Concepts一 節中詳細講解。BGL為一般任務提供了一系列visitor，其中包括記錄前驅節點的visitor。希望用戶能夠使用visitor為BGL擴展。在這 裡，我們將會快速的看一看visitor的實現方法，以及記錄前驅節點的visitor的使用。因為我們使用 dijkstra_shortest_paths()算法，所以我們必須創建一個Dijkstra Visitor。
record_predecessors visitor的泛函性被分為兩個部分。我們使用property map來存儲和訪問前驅節點屬性。然後，predecessor visitor將僅負責記錄前驅節點。為了實現這些，我們創建模版類record_predecessors。以後就可以調用該visitor的方法了，因為我們繼承子dijkstra_visitor類，所以這個類沒有提供其它方法。predecessor_recorder的構造函數將接受一個屬性影射對象並且把它保存到數據成員。
template <class PredecessorMap>記錄前驅節點非常簡單。當Dijkstra算法走到一條邊(意味著把它放入最短路徑樹中)的時候，我們把源點作為目標頂點的前驅節點記錄下來。然後如果這 條邊再被訪問，那麼前驅屬性將會被新的前驅節點改寫。我們使用put()函數把屬性影射關聯到記錄的前驅節點。visitor的edge_filter告 訴算法何時調用explore()方法。我們僅僅想通知在最短路徑樹中的邊，所以規定使用tree_edge_tag標記。
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) {
// 把源頂點設置成目標頂點的父節點
put(m_predecessor, target(e, g), source(e, g));
}
protected:
PredecessorMap m_predecessor;
};
template <class PredecessorMap>
record_predecessors<PredecessorMap>
make_predecessor_recorder(PredecessorMap p) {
return record_predecessors<PredecessorMap>(p);
}
我們準備在Dijkstra算法中使用record_predecessors了。幸運的是，BGL中的Dijkstra算法已經配備了一個
visitor句柄，所以我們只需要傳入新的visitor即可。在這個例子中我們只需要使用一個visitor，但是BGL中一個算法經常配備多個
visitor句柄(參考Visitor Concepts一節)。
using std::vector;輸出為：
using std::cout;
using std::endl;
vector<Vertex> p(num_vertices(G)); //the predecessor array
dijkstra_shortest_paths(G, s, distance_map(&d[0]).
visitor(make_predecessor_recorder(&p[0])));
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] == Vertex())
cout << ") = no parent" << endl;
else
cout << ") = " << p[*vi] << endl;
}
parents in the tree of shortest paths:
parent(0) = no parent
parent(1) = 4
parent(2) = 0
parent(3) = 2
parent(4) = 3
| Copyright c 2000 | Jeremy Siek, Indiana University (jsiek@osl.iu.edu) |