Crossroads - Spring 2011

struct Vertex Info { string name; }; typedef adjacency_list<vecS,vecS, ...

V v = 0/* get vertex descriptor */; g[v].name = “Vertex name”;

Figure 1: all the edges are labeled in the order they are discovered by the DFs. the drawing was produced with GraphViz library.

Vrt. #5

Vrt. #4

One can also assign properties to edges and to the graph as a whole.

6

7

extending algorithms with visitors

Vrt. #0

Several of the more generic BGL algorithms, such as BFS and DFS, can be easily extended in such a way that custom actions will be performed at predefined event points in the algorithm. So let us take DFS for example. There are several “event points” defined, such as when a vertex, a tree edge or a back edge is discovered. We will “plug into“ the examine_edge event and assign each edge a unique number indicating the order of discovery by the DFS. One way to do this is to implement a class inheriting from default_dfs_visitor and override the appropriate method. However, a question arises: where to put the above unique number? The answer is provided by the idea of property maps: our visitor will be parametrized by a type which should implement a property map interface, and it will receive the map object in the constructor. We will assume that the property value for every edge is initialized to - 1. (Note that get() and put() methods are part of the the property map ``interface”.)

2

Vrt. #3

0

3

1

Vrt. #7

Vrt. #2

struct EdgeInfo { int order; }; typedef adjacency_list<vecS, vecS, ...

First we need to initialize the order of each edge to - 1.

template<class OrderMap>
class dfs_edge_recorder : public
default_dfs_visitor {
public:
dfs_edge_recorder(OrderMap m) :
m_order(0), m_map(m) {}
typedef property_map<Graph, int
EdgeInfo::*>::type
EdgeOrderMap;

template <class E, class G> void examine_edge(E e, G g)

EdgeOrderMap order_map =get (&
EdgeInfo::order, g);
graph_traits<Graph>::
edge_iterator ei, ei_end;
for (tie(ei, ei_end) = edges(g);
ei != ei_end; ++ei)
put(order_map, *ei, - 1);

{ if (get(m_map,e) == - 1) put(m_map, e, m_order++);

Finally, let us run the DFS.

}
private:
int m_order;
OrderMap m_map;

dfs_edge_recorder<EdgeOrderMap> edge_recorder(order_map);

depth_first_search(g, visitor( edge_recorder));

};

One possibility is to store the number
in a bundled edge property. So we define
As you can see, the decoupling of
algorithms from storage is very powerful
concept. Our dfs_edge_recorder is
completely generic and can be used with
any graph type and any property map

5

4

Vrt. #1

Vrt. #6

indexed by edge descriptor type.

Conclusion

The BGL design takes some time to learn. Also, the C++ template mechanism and syntax might be disliked by some people. Despite all these, the BGL is ever-growing and constantly improving repository of reusable graph algorithms, and so it is definitely worth the effort. The documentation is very good, together with lots of examples.