Algorithms and Visitors in the Boost Graph Library (BGL)

Algorithms in the Boost Graph Library

Extending Algorithms with Visitors

Often times an algorithm in a library almost does what you need, but not quite. For example, in the previous section we used Dijkstra's algorithm to calculate the shortest distances to each vertex, but perhaps we also wanted to record the tree of shortest paths. One way to do this is to record the predecessor (parent) for each node in the shortest-paths tree.

It would be nice if we could avoid rewriting Dijkstra's algorithm, and just add that little bit extra needed to record the predecessors. In the STL, this kind of extensibility is provided by functors, which are optional parameters to each algorithm. In the BGL this role is fulfilled by visitors.

A visitor is like a functor, but instead of having just one apply method, it has several. Each of these methods get invoked at certain well-defined points within the algorithm. The visitor methods are explained in detail in Visitor Concepts. The BGL provides a number of visitors for some common tasks including a predecessor recording visitor. The user is encouraged to write his or her own visitors as a way of extending the BGL. Here we will take a quick look at the implementation and use of the predecessor recorder. Since we will be using the dijkstra_shortest_paths() algorithm, the visitor we create must be a Dijkstra Visitor.

The functionality of the record_predecessors visitor is separated into two parts. For the storage and access of the predecessor property, we will use a property_map. The predecessor visitor will then only be responsible for what parent to record. To implement this, we create a record_predecessors class and template it on the predecessor property map PredecessorMap. Since this visitor will only be filling in one of the visitor methods, we will inherit from dijkstra_visitor, which will provide empty methods for the rest. The constructor of the predecessor_recorder will take the property map object and save it away in a data member.

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;
  };

The job of recording the predecessors is quite simple. When Dijkstra's algorithm relaxes an edge (potentially adding it to the shortest-paths tree) we record the source vertex as the predecessor of the target vertex. Later, if the edge is relaxed again the predecessor property will be overwritten by the new predecessor. Here we use the put() function associated with the property map to record the predecessor. The edge_filter of the visitor tells the algorithm when to invoke the explore() method. In this case we only want to be notified about edges in the shortest-paths tree so we specify tree_edge_tag.

As a finishing touch, we create a helper function to make it more convenient to create predecessor visitors. All BGL visitors have a helper function like this.

template <class PredecessorMap>
  record_predecessors<PredecessorMap>
  make_predecessor_recorder(PredecessorMap p) {
    return record_predecessors<PredecessorMap>(p);
  }

We are now ready to use the record_predecessors in Dijkstra's algorithm. Luckily, BGL's Dijkstra's algorithm is already equipped to handle visitors, so we just pass in our new visitor. In this example we only need to use one visitor, but the BGL is also equipped to handle the use of multiple visitors in the same algorithm (see Visitor Concepts).

  using std::vector;
  using std::cout;
  using std::endl;
  vector<Vertex> p(num_vertices(G), graph_traits<G>::null_vertex()); //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] == graph_traits<G>::null_vertex())
      cout << ") = no parent" << endl;
    else
      cout << ") = " << p[*vi] << endl;
  }

The output is:

parents in the tree of shortest paths:
  parent(0) = no parent
  parent(1) = 4
  parent(2) = 0
  parent(3) = 2
  parent(4) = 3

Visitors in the Boost Graph Library

The visitor concept plays the same role in BGL as functors play in the STL. Functors provide a mechanism for extending an algorithm; for customizing what is done at each step of the algorithm. Visitors allow the user to insert their own operations at various steps within a graph algorithm. Unlike the STL algorithms, graph algorithms typically have multiple event points where one may want to insert a call-back via a functor. Therefore visitors do not have a single operator() method like a functor, but instead have several methods that correspond to the various event points. Each algorithm has a different set of event points, which are described by the following visitor concepts:

BFS Visitor
DFS Visitor
Dijkstra Visitor
Bellman Ford Visitor
A* Visitor
Event Visitor
Planar Face Visitor
TSP Tour Visitor

In the following example we print out the Internet routers in breadth-first order by extending the breadth_first_search() function with a visitor. The visitor prints the vertex name on the discover vertex event. The visitor class is defined according to the interface described by the BFSVisitor concept.

template <var class='type'name VertexNameMap>
class bfs_name_printer : public default_bfs_visitor {
// inherit default (empty) event point actions
public:
  bfs_name_printer(VertexNameMap n map) : m_name_map(n_map) { }
  template <var class='type'name Vertex, typename Graph>
  void discover_vertex(Vertex u, const Graph& ) const {
    std::cout << get(m_name_map, u) << ' ';
  }
private:
  VertexNameMap m_name_map;
};

We then create a visitor object of type bfs_name_printer and pass it to breadth_first_search().

bfs_name_printer<VertexNameMap> vis(name map);
std::cout << "BFS vertex discover order: ";
breadth first search(g, a, visitor(vis));
std::cout << std::endl;

BFS Visitor

This concept defines the visitor interface for breadth_first_search(). Users can define a class with the BFS Visitor interface and pass and object of the class to breadth_first_search(), thereby augmenting the actions taken during the graph search.

Refinement of

Copy Constructible (copying a visitor should be a lightweight operation).

Notation

V: A type that is a model of BFS Visitor.
vis: An object of type V.
G: A type that is a model of Graph.
g: An object of type G.
e: An object of type boost::graph_traits<G>::edge_descriptor.
s,u: An object of type boost::graph_traits<G>::vertex_descriptor.

Valid Expressions

Initialize Vertex

vis.initialize_vertex(s, g)

return type: void

This is invoked on every vertex of the graph before the start of the graph search.

Discover Vertex

vis.discover_vertex(u, g)

return type: void

This is invoked when a vertex is encountered for the first time.

Examine Vertex

vis.examine_vertex(u, g)

return type: void

This is invoked on a vertex as it is popped from the queue. This happens immediately before examine_edge() is invoked on each of the out-edges of vertex u.

Examine Edge

vis.examine_edge(e, g)

return type: void

This is invoked on every out-edge of each vertex after it is discovered.

Tree Edge

vis.tree_edge(e, g)

return type: void

This is invoked on each edge as it becomes a member of the edges that form the search tree.

Non-Tree Edge

vis.non_tree_edge(e, g)

return type: void

This is invoked on back or cross edges for directed graphs and cross edges for undirected graphs.

Gray Target

vis.gray_target(e, g)

return type: void

This is invoked on the subset of non-tree edges whose target vertex is colored gray at the time of examination. The color gray indicates that the vertex is currently in the queue.

Black Target

vis.black_target(e, g)

return type: void

This is invoked on the subset of non-tree edges whose target vertex is colored black at the time of examination. The color black indicates that the vertex has been removed from the queue.

Finish Vertex

vis.finish_vertex(u, g)

return type: void

This invoked on a vertex after all of its out edges have been added to the search tree and all of the adjacent vertices have been discovered (but before the out-edges of the adjacent vertices have been examined).

Algorithms and Visitors in the Boost Graph Library (BGL)

Algorithms in the Boost Graph Library

Extending Algorithms with Visitors

Visitors in the Boost Graph Library

BFS Visitor

Refinement of

Notation

Valid Expressions

DFS Visitor*

Dijkstra Visitor*

Bellman Ford Visitor*

A* Visitor*

Event Visitor*

Planar Face Visitor*

TSP Tour Visitor*