Planet
navi homePPSaboutscreenshotsdownloaddevelopmentforum

source: downloads/boost_1_33_1/libs/graph/doc/faq.html @ 14

Last change on this file since 14 was 12, checked in by landauf, 18 years ago

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