153 lines
5.8 KiB
HTML
153 lines
5.8 KiB
HTML
<HTML>
|
|
<!--
|
|
Copyright (c) Jeremy Siek, Lie-Quan Lee, and Andrew Lumsdaine 2000
|
|
|
|
Distributed under the Boost Software License, Version 1.0.
|
|
(See accompanying file LICENSE_1_0.txt or copy at
|
|
http://www.boost.org/LICENSE_1_0.txt)
|
|
-->
|
|
<Head>
|
|
<Title>Boost Graph Library: FAQ</Title>
|
|
<BODY BGCOLOR="#ffffff" LINK="#0000ee" TEXT="#000000" VLINK="#551a8b"
|
|
ALINK="#ff0000">
|
|
<IMG SRC="../../../boost.png"
|
|
ALT="C++ Boost" width="277" height="86">
|
|
|
|
<BR Clear>
|
|
|
|
<h1>Frequently Asked Questions</h1>
|
|
|
|
<ol>
|
|
|
|
<li>
|
|
How do I perform an early exit from an algorithm such as BFS?<br>
|
|
|
|
<p>
|
|
Create a visitor that throws an exception when you want to cut off the
|
|
search, then put your call to <tt>breadth_first_search</tt> 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.
|
|
</p>
|
|
|
|
<li>
|
|
Why is the visitor parameter passed by value rather than reference
|
|
in the various BGL algorithms?<br>
|
|
|
|
<p>
|
|
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 your 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 you may want the
|
|
visitor to hold this state by pointer or reference.
|
|
</p>
|
|
|
|
<li>Why does the BGL interface use friend functions (or free functions)
|
|
instead of member functions?<br>
|
|
<p>
|
|
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 <tt>stanford_graph.hpp</tt>
|
|
and <tt>leda_graph.hpp</tt>. One can even use
|
|
<tt>std::vector<std::list></tt> as a graph due to the overloads
|
|
in <tt>vector_as_graph.hpp</tt>.
|
|
</p>
|
|
<p>
|
|
Of course, there is a way to adapt 3rd party classes into an interface
|
|
with member functions. You 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.
|
|
</p>
|
|
|
|
<p>
|
|
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!
|
|
</p>
|
|
</li>
|
|
|
|
|
|
|
|
|
|
<li>How do I create a graph where the edges are sorted/ordered? <br>
|
|
<p>The example <a href="../example/ordered_out_edges.cpp">
|
|
<tt>ordered_out_edges.cpp</tt></a> shows how to do this.</p>
|
|
</li>
|
|
|
|
<li>Why does the algorithm X work with <tt>adjacency_list</tt> where
|
|
<tt>VertexList=vecS</tt> but not when <tt>VertexList=listS</tt>? <br><br>
|
|
Often the reason is that the algorithm expects to find the
|
|
<tt>vertex_index</tt> property stored in the graph. When
|
|
<tt>VertexList=vecS</tt>, the <tt>adjacency_list</tt> automatically
|
|
has a <tt>vertex_index</tt> property. However, when <tt>VertexList=listS</tt>
|
|
this is not the case, and the <tt>vertex_index</tt> property must be
|
|
explicitly added, and initialized. For example,
|
|
<pre>
|
|
// 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(boost::tie(vi,vend) = vertices(G); vi != vend; ++vi)
|
|
put(index, *vi, cnt++);
|
|
</pre>
|
|
</li>
|
|
|
|
<li>When using algorithm X, why do I get an error about a property
|
|
not being found, such as:
|
|
<pre>
|
|
../../../boost/concept_check.hpp:209: no match for
|
|
`boost::detail::error_property_not_found & ==
|
|
boost::detail::error_property_not_found &'
|
|
</pre>
|
|
or a message such as:
|
|
<pre>
|
|
../../..\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'
|
|
</pre>
|
|
|
|
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. You need to 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.</li>
|
|
|
|
|
|
|
|
</ol>
|
|
<!-- LocalWords: gif ALT BGL std const STL GraphBase LEDA BFS stanford hpp OO
|
|
-->
|
|
<!-- LocalWords: leda cpp VertexList vecS listS undirectedS num cnt struct
|
|
-->
|
|
<!-- LocalWords: enum
|
|
-->
|