ceph/src/boost/libs/graph/doc/faq.html

   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&lt;std::list&gt;</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&lt;listS, listS, undirectedS,
 106                          property&lt;vertex_index_t, std::size_t&gt;,
 107                          no_property
 108                         &gt; 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&lt;graph_t, vertex_index_t&gt;::type
 114     index = get(vertex_index, G);
 115   // initialize the vertex_index property values
 116   graph_traits&lt;graph_t&gt;::vertex_iterator vi, vend;
 117   graph_traits&lt;graph_t&gt;::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
 124 not being found, such as:
 125 <pre>
 126 ../../../boost/concept_check.hpp:209: no match for
 127 `boost::detail::error_property_not_found &amp; ==
 128  boost::detail::error_property_not_found &amp;'
 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  -->