Boost is a huge collection of libraries. Some of those libraries are small and meant for everyday use and others require a separate article to describe all of their features. This article is devoted to some of those big libraries and to give you some basics to start with. The first two recipes will explain the usage of Boost.Graph. It is a big library with an insane number of algorithms. We’ll see some basics and probably the most important part of it visualization of graphs.
We’ll also see a very useful recipe for generating true random numbers. This is a very important requirement for writing secure cryptography systems.
Some C++ standard libraries lack math functions. We’ll see how that can be fixed using Boost. But the format of this article leaves no space to describe all of the functions.
Writing test cases is described in the Writing test cases and Combining multiple test cases in one test module recipes. This is important for any production-quality system.
The last recipe is about a library that helped me in many courses during my university days. Images can be created and modified using it. I personally used it to visualize different algorithms, hide data in images, sign images, and generate textures.
Unfortunately, even this article cannot tell you about all of the Boost libraries. Maybe someday I’ll write another book… and then a few more.
Working with graphs
Some tasks require a graphical representation of data. Boost.Graph is a library that was designed to provide a flexible way of constructing and representing graphs in memory. It also contains a lot of algorithms to work with graphs, such as topological sort, breadth first search, depth first search, and Dijkstra shortest paths.
Well, let’s perform some basic tasks with Boost.Graph!
Getting ready
Only basic knowledge of C++ and templates is required for this recipe.
How to do it…
In this recipe, we’ll describe a graph type, create a graph of that type, add some vertexes and edges to the graph, and search for a specific vertex. That should be enough to start using Boost.Graph.
- We start with describing the graph type:
#include <boost/graph/adjacency_list.hpp> #include <string> typedef std::string vertex_t; typedef boost::adjacency_list< boost::vecS , boost::vecS , boost::bidirectionalS , vertex_t > graph_type;
- Now we construct it:
graph_type graph;
- Let’s use a non portable trick that speeds up graph construction:
static const std::size_t vertex_count = 5; graph.m_vertices.reserve(vertex_count);
- Now we are ready to add vertexes to the graph:
typedef boost::graph_traits<graph_type> ::vertex_descriptor descriptor_t; descriptor_t cpp = boost::add_vertex(vertex_t("C++"), graph); descriptor_t stl = boost::add_vertex(vertex_t("STL"), graph); descriptor_t boost = boost::add_vertex(vertex_t("Boost"), graph); descriptor_t guru = boost::add_vertex(vertex_t("C++ guru"), graph); descriptor_t ansic = boost::add_vertex(vertex_t("C"), graph);
- It is time to connect vertexes with edges:
boost::add_edge(cpp, stl, graph); boost::add_edge(stl, boost, graph); boost::add_edge(boost, guru, graph); boost::add_edge(ansic, guru, graph);
- We make a function that searches for a vertex:
template <class GraphT> void find_and_print(const GraphT& g, boost::string_ref name) {
- Now we will write code that gets iterators to all vertexes:
typedef typename boost::graph_traits<graph_type> ::vertex_iterator vert_it_t; vert_it_t it, end; boost::tie(it, end) = boost::vertices(g);
- It’s time to run a search for the required vertex:
typedef boost::graph_traits<graph_type>::vertex_descriptor desc_t; for (; it != end; ++ it) { desc_t desc = *it; if (boost::get(boost::vertex_bundle, g)[desc] == name.data()) { break; } } assert(it != end); std::cout << name << 'n'; } /* find_and_print */
How it works…
In step 1, we are describing what our graph must look like and upon what types it must be based. boost::adjacency_list is a class that represents graphs as a two-dimensional structure, where the first dimension contains vertexes and the second dimension contains edges for that vertex. boost::adjacency_list must be the default choice for representing a graph; it suits most cases.
The first template parameter, boost::adjacency_list, describes the structure used to represent the edge list for each of the vertexes; the second one describes a structure to store vertexes. We can choose different STL containers for those structures using specific selectors, as listed in the following table:
|
Selector |
STL container |
|
boost::vecS |
std::vector |
|
boost::listS |
std::list |
|
boost::slistS |
std::slist |
|
boost::setS |
std::set |
|
boost::multisetS |
std::multiset |
|
boost::hash_setS |
std::hash_set |
The third template parameter is used to make an undirected, directed, or bidirectional graph. Use the boost::undirectedS, boost::directedS, and boost::bidirectionalS selectors respectively.
The fifth template parameter describes the datatype that will be used as the vertex. In our example, we chose std::string. We can also support a datatype for edges and provide it as a template parameter.
Steps 2 and 3 are trivial, but at step 4 you will see a non portable way to speed up graph construction. In our example, we use std::vector as a container for storing vertexes, so we can force it to reserve memory for the required amount of vertexes. This leads to less memory allocations/deallocations and copy operations during insertion of vertexes into the graph. This step is non-portable because it is highly dependent on the current implementation of boost::adjacency_list and on the chosen container type for storing vertexes.
At step 4, we see how vertexes can be added to the graph. Note how boost::graph_traits<graph_type> has been used. The boost::graph_traits class is used to get types that are specific for a graph type. We’ll see its usage and the description of some graph-specific types later in this article. Step 5 shows what we need do to connect vertexes with edges.
If we had provided a datatype for the edges, adding an edge would look as follows:
boost::add_edge(ansic, guru, edge_t(initialization_parameters), graph)
Note that at step 6 the graph type is a template parameter. This is recommended to achieve better code reusability and make this function work with other graph types.
At step 7, we see how to iterate over all of the vertexes of the graph. The type of vertex iterator is received from boost::graph_traits. The function boost::tie is a part of Boost.Tuple and is used for getting values from tuples to the variables. So calling boost::tie(it, end) = boost::vertices(g) will put the begin iterator into the it variable and the end iterator into the end variable.
It may come as a surprise to you, but dereferencing a vertex iterator does not return vertex data. Instead, it returns the vertex descriptor desc, which can be used in boost::get(boost::vertex_bundle, g)[desc] to get vertex data, just as we have done in step 8. The vertex descriptor type is used in many of the Boost.Graph functions; we saw its use in the edge construction function in step 5.
As already mentioned, the Boost.Graph library contains the implementation of many algorithms. You will find many search policies implemented, but we won’t discuss them in this article. We will limit this recipe to only the basics of the graph library.
There’s more…
The Boost.Graph library is not a part of C++11 and it won’t be a part of C++1y. The current implementation does not support C++11 features. If we are using vertexes that are heavy to copy, we may gain speed using the following trick:
vertex_descriptor desc = boost::add_vertex(graph); boost::get(boost::vertex_bundle, g_)[desc] = std::move(vertex_data);
It avoids copy constructions of boost::add_vertex(vertex_data, graph) and uses the default construction with move assignment instead.
The efficiency of Boost.Graph depends on multiple factors, such as the underlying containers types, graph representation, edge, and vertex datatypes.
Visualizing graphs
Making programs that manipulate graphs was never easy because of issues with visualization. When we work with STL containers such as std::map and std::vector, we can always print the container’s contents and see what is going on inside. But when we work with complex graphs, it is hard to visualize the content in a clear way: too many vertexes and too many edges.
In this recipe, we’ll take a look at the visualization of Boost.Graph using the Graphviz tool.
Getting ready
To visualize graphs, you will need a Graphviz visualization tool. Knowledge of the preceding recipe is also required.
How to do it…
Visualization is done in two phases. In the first phase, we make our program output the graph’s description in a text format; in the second phase, we import the output from the first step to some visualization tool. The numbered steps in this recipe are all about the first phase.
- Let’s write the std::ostream operator for graph_type as done in the preceding recipe:
#include <boost/graph/graphviz.hpp> std::ostream& operator<<(std::ostream& out, const graph_type& g) { detail::vertex_writer<graph_type> vw(g); boost::write_graphviz(out, g, vw); return out; }
- The detail::vertex_writer structure, used in the preceding step, must be defined as follows:
namespace detail { template <class GraphT> class vertex_writer { const GraphT& g_; public: explicit vertex_writer(const GraphT& g) : g_(g) {} template <class VertexDescriptorT> void operator()(std::ostream& out, const VertexDescriptorT& d) const { out << " [label="" << boost::get(boost::vertex_bundle, g_)[d] << ""]"; } }; // vertex_writer } // namespace detail
That’s all. Now, if we visualize the graph from the previous recipe using the std::cout << graph; command, the output can be used to create graphical pictures using the dot command-line utility:
$ dot -Tpng -o dot.png digraph G { 0 [label="C++"]; 1 [label="STL"]; 2 [label="Boost"]; 3 [label="C++ guru"]; 4 [label="C"]; 0->1 ; 1->2 ; 2->3 ; 4->3 ; }
The output of the preceding command is depicted in the following figure:
We can also use the Gvedit or XDot programs for visualization if the command line frightens you.
How it works…
The Boost.Graph library contains function to output graphs in Graphviz (DOT) format. If we write boost::write_graphviz(out, g) with two parameters in step 1, the function will output a graph picture with vertexes numbered from 0. That’s not very useful, so we provide an instance of the vertex_writer class that outputs vertex names.
As we can see in step 2, the format of output must be DOT, which is understood by the Graphviz tool. You may need to read the Graphviz documentation for more info about the DOT format.
If you wish to add some data to the edges during visualization, we need to provide an instance of the edge visualizer as a fourth parameter to boost::write_graphviz.
There’s more…
C++11 does not contain Boost.Graph or the tools for graph visualization. But you do not need to worry—there are a lot of other graph formats and visualization tools and Boost.
Graph can work with plenty of them.
Using a true random number generator
I know of many examples of commercial products that use incorrect methods for getting random numbers. It’s a shame that some companies still use rand() in cryptography and banking software.
Let’s see how to get a fully random uniform distribution using Boost.Random that is suitable for banking software.
Getting ready
Basic knowledge of C++ is required for this recipe. Knowledge of different types of distributions will also be helpful. The code in this recipe requires linking against the boost_random library.
How to do it…
To create a true random number, we need some help from the operating system or processor. This is how it can be done using Boost:
- We’ll need to include the following headers:
#include <boost/config.hpp> #include <boost/random/random_device.hpp> #include <boost/random/uniform_int_distribution.hpp>
- Advanced random number providers have different names under different platforms:
static const std::string provider = #ifdef BOOST_WINDOWS "Microsoft Strong Cryptographic Provider" #else "/dev/urandom" #endif ;
- Now we are ready to initialize the generator with Boost.Random:
boost::random_device device(provider);
- Let’s get a uniform distribution that returns a value between 1000 and 65535:
boost::random::uniform_int_distribution<unsigned short> random(1000);
That’s it. Now we can get true random numbers using the random(device) call.
How it works…
Why does the rand() function not suit banking? Because it generates pseudo-random numbers, which means that the hacker could predict the next generated number. This is an issue with all pseudo-random number algorithms. Some algorithms are easier to predict and some harder, but it’s still possible.
That’s why we are using boost::random_device in this example (see step 3). That device gathers information about random events from all around the operating system to construct an unpredictable hardware-generated number. The examples of such events are delays between pressed keys, delays between some of the hardware interruptions, and the internal CPU random number generator.
Operating systems may have more than one such type of random number generators. In our example for POSIX systems, we used /dev/urandom instead of the more secure /dev/random because the latter remains in a blocked state until enough random events have been captured by the OS. Waiting for entropy could take seconds, which is usually unsuitable for applications. Use /dev/random to create long-lifetime GPG/SSL/SSH keys.
Now that we are done with generators, it’s time to move to step 4 and talk about distribution classes. If the generator just generates numbers (usually uniformly distributed), the distribution class maps one distribution to another. In step 4, we made a uniform distribution that returns a random number of unsigned short type. The parameter 1000 means that distribution must return numbers greater or equal to 1000. We can also provide the maximum number as a second parameter, which is by default equal to the maximum value storable in the return type.
There’s more…
Boost.Random has a huge number of true/pseudo random generators and distributions for different needs. Avoid copying distributions and generators; this could turn out to be an expensive operation.
C++11 has support for different distribution classes and generators. You will find all of the classes from this example in the <random> header in the std:: namespace. The Boost.Random libraries do not use C++11 features, and they are not really required for that library either. Should you use Boost implementation or STL? Boost provides better portability across systems; however, some STL implementations may have assembly-optimized implementations and might provide some useful extensions.
Using portable math functions
Some projects require specific trigonometric functions, a library for numerically solving ordinary differential equations, and working with distributions and constants. All of those parts of Boost.Math would be hard to fit into even a separate book. A single recipe definitely won’t be enough. So let’s focus on very basic everyday-use functions to work with float types.
We’ll write a portable function that checks an input value for infinity and not-a-number (NaN) values and changes the sign if the value is negative.
Getting ready
Basic knowledge of C++ is required for this recipe. Those who know C99 standard will find a lot in common in this recipe.
How to do it…
Perform the following steps to check the input value for infinity and NaN values and change the sign if the value is negative:
- We’ll need the following headers:
#include <boost/math/special_functions.hpp> #include <cassert>
- Asserting for infinity and NaN can be done like this:
template <class T> void check_float_inputs(T value) { assert(!boost::math::isinf(value)); assert(!boost::math::isnan(value));
- Use the following code to change the sign:
if (boost::math::signbit(value)) { value = boost::math::changesign(value); } // ... } // check_float_inputs
That’s it! Now we can check that check_float_inputs(std::sqrt(-1.0)) and check_float_inputs(std::numeric_limits<double>::max() * 2.0) will cause asserts.
How it works…
Real types have specific values that cannot be checked using equality operators. For example, if the variable v contains NaN, assert(v!=v) may or may not pass depending on the compiler.
For such cases, Boost.Math provides functions that can reliably check for infinity and NaN values.
Step 3 contains the boost::math::signbit function, which requires clarification. This function returns a signed bit, which is 1 when the number is negative and 0 when the number is positive. In other words, it returns true if the value is negative.
Looking at step 3 some readers might ask, “Why can’t we just multiply by -1 instead of calling boost::math::changesign?”. We can. But multiplication may work slower than boost::math::changesign and won’t work for special values. For example, if your code can work with nan, the code in step 3 will be able to change the sign of -nan and write nan to the variable.
The Boost.Math library maintainers recommend wrapping math functions from this example in round parenthesis to avoid collisions with C macros. It is better to write (boost::math::isinf)(value) instead of boost::math::isinf(value).
There’s more…
C99 contains all of the functions described in this recipe. Why do we need them in Boost? Well, some compiler vendors think that programmers do not need them, so you won’t find them in one very popular compiler. Another reason is that the Boost.Math functions can be used for classes that behave like numbers.
Boost.Math is a very fast, portable, reliable library.
