| 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> |
|---|
| 23 | How do I perform an early exit from an algorithm such as BFS?<br> |
|---|
| 24 | |
|---|
| 25 | <p> |
|---|
| 26 | Create a visitor that throws an exception when you want to cut off the |
|---|
| 27 | search, then put your call to <tt>breadth_first_search</tt> inside of |
|---|
| 28 | an appropriate try/catch block. This strikes many programmers as a |
|---|
| 29 | misuse of exceptions, however, much thought was put into the decision |
|---|
| 30 | to have exceptions has the preferred way to exit early. See boost |
|---|
| 31 | email discussions for more details. |
|---|
| 32 | </p> |
|---|
| 33 | |
|---|
| 34 | <li> |
|---|
| 35 | Why is the visitor parameter passed by value rather than reference |
|---|
| 36 | in the various BGL algorithms?<br> |
|---|
| 37 | |
|---|
| 38 | <p> |
|---|
| 39 | One of the usage scenarios that we wanted to support with the |
|---|
| 40 | algorithms was creating visitor objects on the fly, within the |
|---|
| 41 | argument list of the call to the graph algorithm. In this situation, |
|---|
| 42 | the visitor object is a temporary object. Now there is a truly |
|---|
| 43 | unfortunate rule in the C++ standard that says a temporary cannot be |
|---|
| 44 | bound to a non-const reference parameter. So we had to decide whether |
|---|
| 45 | we wanted to support this kind of usage and call-by-value, or not and |
|---|
| 46 | call-by-reference. We chose call-by-value, following in the footsteps |
|---|
| 47 | of the STL (which passes functors by value). The disadvantage of this |
|---|
| 48 | decision is that if your visitor contains state and changes that state |
|---|
| 49 | during the algorithm, the change will be made to a copy of the visitor |
|---|
| 50 | object, not the visitor object passed in. Therefore you may want the |
|---|
| 51 | visitor 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> |
|---|
| 57 | For the most part, the differences between member functions and free |
|---|
| 58 | functions are syntactic, and not very important, though people can get |
|---|
| 59 | religious about them. However, we had one technical reason for |
|---|
| 60 | favoring free functions. A programmer can overload a free function for |
|---|
| 61 | a type coming from a 3rd party without modifying the source |
|---|
| 62 | code/definition of that type. There are several uses of this in the |
|---|
| 63 | BGL. For example, Stanford GraphBase and LEDA graphs can both be used |
|---|
| 64 | in BGL algorithms because of overloads in <tt>stanford_graph.hpp</tt> |
|---|
| 65 | and <tt>leda_graph.hpp</tt>. One can even use |
|---|
| 66 | <tt>std::vector<std::list></tt> as a graph due to the overloads |
|---|
| 67 | in <tt>vector_as_graph.hpp</tt>. |
|---|
| 68 | </p> |
|---|
| 69 | <p> |
|---|
| 70 | Of course, there is a way to adapt 3rd party classes into an interface |
|---|
| 71 | with member functions. You create an adaptor class. However, the |
|---|
| 72 | disadvantage of an adaptor class (compared to overloaded functions) is |
|---|
| 73 | that one has to physically wrap and unwrap the objects as they go |
|---|
| 74 | into/out of BGL algorithms. So the overloaded function route is more |
|---|
| 75 | convenient. Granted, this is not a huge difference, but since there |
|---|
| 76 | weren't other strong reasons, it was enough for us to choose free |
|---|
| 77 | functions. |
|---|
| 78 | </p> |
|---|
| 79 | |
|---|
| 80 | <p> |
|---|
| 81 | Our religious reason for choosing free functions is to send the message |
|---|
| 82 | that BGL is a generic library, and not a traditional object-oriented |
|---|
| 83 | library. 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(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 |
|---|
| 124 | not 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> |
|---|
| 130 | or 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 | |
|---|
| 138 | The reason is that the algorithm expected to find some property (like color or |
|---|
| 139 | weight) attached to the vertices or edges of the graph, but didn't |
|---|
| 140 | find it. You need to either add an interior property to the graph, or |
|---|
| 141 | create an exterior property map for the property and pass it as an |
|---|
| 142 | argument 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 | --> |
|---|
