1<HTML> 2<!-- 3 Copyright (c) Jeremy Siek, Lie-Quan Lee, and Andrew Lumsdaine 2000 4 5 Distributed under the Boost Software License, Version 1.0. 6 (See accompanying file LICENSE_1_0.txt or copy at 7 http://www.boost.org/LICENSE_1_0.txt) 8 --> 9<Head> 10<Title>Boost Graph Library: FAQ</Title> 11<BODY BGCOLOR="#ffffff" LINK="#0000ee" TEXT="#000000" VLINK="#551a8b" 12 ALINK="#ff0000"> 13<IMG SRC="../../../boost.png" 14 ALT="C++ Boost" width="277" height="86"> 15 16<BR Clear> 17 18<h1>Frequently Asked Questions</h1> 19 20<ol> 21 22<li> 23How do I perform an early exit from an algorithm such as BFS?<br> 24 25<p> 26Create a visitor that throws an exception when you want to cut off the 27search, then put your call to <tt>breadth_first_search</tt> inside of 28an appropriate try/catch block. This strikes many programmers as a 29misuse of exceptions, however, much thought was put into the decision 30to have exceptions has the preferred way to exit early. See boost 31email discussions for more details. 32</p> 33 34<li> 35Why is the visitor parameter passed by value rather than reference 36in the various BGL algorithms?<br> 37 38<p> 39One of the usage scenarios that we wanted to support with the 40algorithms was creating visitor objects on the fly, within the 41argument list of the call to the graph algorithm. In this situation, 42the visitor object is a temporary object. Now there is a truly 43unfortunate rule in the C++ standard that says a temporary cannot be 44bound to a non-const reference parameter. So we had to decide whether 45we wanted to support this kind of usage and call-by-value, or not and 46call-by-reference. We chose call-by-value, following in the footsteps 47of the STL (which passes functors by value). The disadvantage of this 48decision is that if your visitor contains state and changes that state 49during the algorithm, the change will be made to a copy of the visitor 50object, not the visitor object passed in. Therefore you may want the 51visitor to hold this state by pointer or reference. 52</p> 53 54<li>Why does the BGL interface use friend functions (or free functions) 55 instead of member functions?<br> 56<p> 57For the most part, the differences between member functions and free 58functions are syntactic, and not very important, though people can get 59religious about them. However, we had one technical reason for 60favoring free functions. A programmer can overload a free function for 61a type coming from a 3rd party without modifying the source 62code/definition of that type. There are several uses of this in the 63BGL. For example, Stanford GraphBase and LEDA graphs can both be used 64in BGL algorithms because of overloads in <tt>stanford_graph.hpp</tt> 65and <tt>leda_graph.hpp</tt>. One can even use 66<tt>std::vector<std::list></tt> as a graph due to the overloads 67in <tt>vector_as_graph.hpp</tt>. 68</p> 69<p> 70Of course, there is a way to adapt 3rd party classes into an interface 71with member functions. You create an adaptor class. However, the 72disadvantage of an adaptor class (compared to overloaded functions) is 73that one has to physically wrap and unwrap the objects as they go 74into/out of BGL algorithms. So the overloaded function route is more 75convenient. Granted, this is not a huge difference, but since there 76weren't other strong reasons, it was enough for us to choose free 77functions. 78</p> 79 80<p> 81Our religious reason for choosing free functions is to send the message 82that BGL is a generic library, and not a traditional object-oriented 83library. OO was hip in the 80s and 90s, but its time we moved beyond! 84</p> 85</li> 86 87 88 89 90<li>How do I create a graph where the edges are sorted/ordered? <br> 91 <p>The example <a href="../example/ordered_out_edges.cpp"> 92 <tt>ordered_out_edges.cpp</tt></a> shows how to do this.</p> 93 </li> 94 95<li>Why does the algorithm X work with <tt>adjacency_list</tt> where 96 <tt>VertexList=vecS</tt> but not when <tt>VertexList=listS</tt>? <br><br> 97 Often the reason is that the algorithm expects to find the 98 <tt>vertex_index</tt> property stored in the graph. When 99 <tt>VertexList=vecS</tt>, the <tt>adjacency_list</tt> automatically 100 has a <tt>vertex_index</tt> property. However, when <tt>VertexList=listS</tt> 101 this is not the case, and the <tt>vertex_index</tt> property must be 102 explicitly added, and initialized. For example, 103<pre> 104 // specify the graph type 105 typedef adjacency_list<listS, listS, undirectedS, 106 property<vertex_index_t, std::size_t>, 107 no_property 108 > graph_t; 109 110 // construct a graph object 111 graph_t G(num_nodes); 112 // obtain a property map for the vertex_index property 113 property_map<graph_t, vertex_index_t>::type 114 index = get(vertex_index, G); 115 // initialize the vertex_index property values 116 graph_traits<graph_t>::vertex_iterator vi, vend; 117 graph_traits<graph_t>::vertices_size_type cnt = 0; 118 for(boost::tie(vi,vend) = vertices(G); vi != vend; ++vi) 119 put(index, *vi, cnt++); 120</pre> 121</li> 122 123<li>When using algorithm X, why do I get an error about a property 124not being found, such as: 125<pre> 126../../../boost/concept_check.hpp:209: no match for 127`boost::detail::error_property_not_found & == 128 boost::detail::error_property_not_found &' 129</pre> 130or a message such as: 131<pre> 132../../..\boost/graph/depth_first_search.hpp(78) : error C2664: 'white' 133: cannot convert parameter 1 from 134 'struct boost::detail::error_property_not_found' 135 to 'enum boost::default_color_type' 136</pre> 137 138The reason is that the algorithm expected to find some property (like color or 139weight) attached to the vertices or edges of the graph, but didn't 140find it. You need to either add an interior property to the graph, or 141create an exterior property map for the property and pass it as an 142argument to the algorithm.</li> 143 144 145 146</ol> 147<!-- LocalWords: gif ALT BGL std const STL GraphBase LEDA BFS stanford hpp OO 148 --> 149<!-- LocalWords: leda cpp VertexList vecS listS undirectedS num cnt struct 150 --> 151<!-- LocalWords: enum 152 --> 153
