Frequently Asked Questions

  1. How do I perform an early exit from an algorithm such as BFS?

    Create a visitor that throws an exception when there is need to cut off the search, then put the call to     breadth_first_search inside of an appropriate try/catch block. This strikes many programmers as a misuse of exceptions, however, much thought was put into the decision to have exceptions has the preferred way to exit early. See boost email discussions for more details.
     
  2. Why is the visitor parameter passed by value rather than reference in the various BGL algorithms?

    One of the usage scenarios that we wanted to support with the algorithms was creating visitor objects on the fly, within the argument list of the call to the graph algorithm. In this situation, the visitor object is a temporary object. Now there is a truly unfortunate rule in the C++ standard that says a temporary cannot be bound to a non-const reference parameter. So we had to decide whether we wanted to support this kind of usage and call-by-value, or not and call-by-reference. We chose call-by-value, following in the footsteps of the STL (which passes functors by value). The disadvantage of this decision is that if the visitor contains state and changes that state during the algorithm, the change will be made to a copy of the visitor object, not the visitor object passed in. Therefore the user may want the visitor to hold this state by pointer or reference.
     

  3. Why does the BGL interface use friend functions (or free functions) instead of member functions?

    For the most part, the differences between member functions and free functions are syntactic, and not very important, though people can get religious about them. However, we had one technical reason for favoring free functions. A programmer can overload a free function for a type coming from a 3rd party without modifying the source code/definition of that type. There are several uses of this in the BGL. For example, Stanford GraphBase and LEDA graphs can both be used in BGL algorithms because of overloads in stanford_graph.hpp and leda_graph.hpp. One can even use std::vector<std::list> as a graph due to the overloads in vector_as_graph.hpp.

    Of course, there is a way to adapt 3rd party classes into an interface with member functions. Create an adaptor class. However, the disadvantage of an adaptor class (compared to overloaded functions) is that one has to physically wrap and unwrap the objects as they go into/out of BGL algorithms. So the overloaded function route is more convenient. Granted, this is not a huge difference, but since there weren't other strong reasons, it was enough for us to choose free functions.

    Our religious reason for choosing free functions is to send the message that BGL is a generic library, and not a traditional object-oriented library. OO was hip in the 80s and 90s, but its time we moved beyond!
     

  4. How do I create a graph where the edges are sorted/ordered?

    The example ordered_out_edges.cpp shows how to do this.
     

  5. Why does the algorithm X work with adjacency_list where VertexList=vecS but not when VertexList=listS?

    Often the reason is that the algorithm expects to find the vertex_index property stored in the graph. When VertexList=vecS, the adjacency_list automatically has a vertex_index property. However, when VertexList=listS this is not the case, and the vertex_index property must be explicitly added, and initialized. For example, 
      // specify the graph type
  typedef adjacency_list<listS, listS, undirectedS,
                         property<vertex_index_t, std::size_t>,
                         no_property
                        > graph_t;

  // construct a graph object
  graph_t G(num_nodes);
  // obtain a property map for the vertex_index property
  property_map<graph_t, vertex_index_t>::type
    index = get(vertex_index, G);
  // initialize the vertex_index property values
  graph_traits<graph_t>::vertex_iterator vi, vend;
  graph_traits<graph_t>::vertices_size_type cnt = 0;
  for(tie(vi,vend) = vertices(G); vi != vend; ++vi)
    put(index, *vi, cnt++);
  6. When using algorithm X, why do I get an error about a property not being found, such as: 
    ../../../boost/concept_check.hpp:209: no match for
`boost::detail::error_property_not_found & == 
 boost::detail::error_property_not_found &'
    or a message such as: 
    ../../..\boost/graph/depth_first_search.hpp(78) : error C2664: 'white'
: cannot convert parameter 1 from 
 'struct boost::detail::error_property_not_found'
 to 'enum boost::default_color_type'

The reason is that the algorithm expected to find some property (like color or
weight) attached to the vertices or edges of the graph, but didn't
find it. 
Either add an interior property to the graph, or
create an exterior property map for the property and pass it as an
argument to the algorithm.
  Top