mirror of
https://github.com/boostorg/graph.git
synced 2026-01-21 17:02:23 +00:00
120 lines
4.5 KiB
HTML
120 lines
4.5 KiB
HTML
<HTML>
|
|
<!--
|
|
-- Copyright (c) Jeremy Siek, Lie-Quan Lee, and Andrew Lumsdaine 2000
|
|
--
|
|
-- Permission to use, copy, modify, distribute and sell this software
|
|
-- and its documentation for any purpose is hereby granted without fee,
|
|
-- provided that the above copyright notice appears in all copies and
|
|
-- that both that copyright notice and this permission notice appear
|
|
-- in supporting documentation. We make no
|
|
-- representations about the suitability of this software for any
|
|
-- purpose. It is provided "as is" without express or implied warranty.
|
|
-->
|
|
<Head>
|
|
<Title>Boost Graph Library: FAQ</Title>
|
|
<BODY BGCOLOR="#ffffff" LINK="#0000ee" TEXT="#000000" VLINK="#551a8b"
|
|
ALINK="#ff0000">
|
|
<IMG SRC="../../../c++boost.gif"
|
|
ALT="C++ Boost" width="277" height="86">
|
|
|
|
<BR Clear>
|
|
|
|
<h1>Frequently Asked Questions</h1>
|
|
|
|
|
|
<ol>
|
|
|
|
<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 member
|
|
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(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>
|