Making axiomatic statements about computing is usually a matter of hot debate. However, graph theory being one of the most important theoretical pillars of modern computing is not one of those statements. Myriad fields of engineering—from designing routers and networks to designing the chips that form the core of your mobile—are but applications of graph theory.

As C++ application-software developers, we often have a direct need to transform a practical engineering problem into an equivalent graph-theory problem. Having a robust C++-based generic-graph library that helps us do just that would obviously be welcome: The Boost Graph Library (BGL) fills in that precise void.

Generic Programming and the Boost Graph Library Jeremy Siek Department of Electrical, Computer, and Energy Engineering University of Colorado at Boulder BoostCon 2010 Jeremy Siek Generic Programming and the Boost Graph Library.

In this article, you create an undirected, and then a directed graph followed by the usual traversal routines. Then, you apply some classical algorithms—all without adding a lot of code. That is the magic of BGL.

Download and installation

Boost is a set of libraries for the C programming language that provide support for tasks and structures such as linear algebra, pseudorandom number generation, multithreading, image processing, regular expressions, and unit testing.It contains over eighty individual libraries. Most of the Boost libraries are licensed under the Boost Software License, designed to allow Boost to be used with. Part of the Boost Graph Library is a generic interface that allows access to a graph's structure, but hides the details of the implementation. This is an “open” interface in the sense that any graph library that implements this interface will be interoperable with the BGL generic algorithms and with other algorithms that also use this. Using the Boost Graph Library. These code samples listed on here appear reasonably up to date and appear to compile and work fine. I am finding that some of the online documentation concerning the use of the Boost Graph Library seems to be out of date or produces compilation errors.

BGL is available as a free download from the Boost site (see Related topics for a link). BGL is a header-only library, therefore, subsequent use of this library in application code requires including the relevant headers in your source code. However, BGL does need the serialization library to link. Here is a typical command line:

For the purposes of this article, you need the Boost 1.44 release.

Adjacency lists

At the heart of any graph implementation lies an adjacency list or matrix. Listing 1 shows how the adjacency list is declared in the Boost header adjacency_list.hpp.

Listing 1. Declaring an adjacency list in Boost

To keep matters simple, let us concentrate on the first three template parameters.

The OutEdgeList template parameter decides what kind of container will be used to store the edge-list information. Recall from your graph-theory basics that, for a directed graph, all vertices that have only incoming edges have an empty corresponding adjacency list. The default value is set to vecS, which corresponds to std::vector. The VertexList template parameter decides what kind of container is used to represent the vertex list of the graph, again the default being std::vector. The DirectedS template parameter decides whether this is a directed or undirected graph based on whether the value provided is directedS or undirectedS.

Creating a graph in BGL

With that declaration of the adjacency list in tow, the code in Listing 2 creates a simple undirected graph in BGL. The edge information will be stored in std::list and the vertices in std::vector.

Listing 2. Creating an undirected graph

In Listing 2, the graph g is created without providing any vertex or edge details in the constructor. Edges and vertices would be created at run time using helper functions like add_edge and add_vertex. The add_edge function does what its name implies: It adds an edge between two vertices of the graph. At the end of execution in Listing 2, g should have four vertices labeled 0, 1, 2, and 3, with 1 connected to 0 and 2, and so on.

Traversing the graph

Traversing the graph involves using the vertex_iterator and the adjacency_iterator classes. The former iterates over all the vertices of the graph; the latter iterates over the corresponding adjacent vertices. Listing 3 shows the code.

Listing 3. Traversing the graph using BGL

Creating a directed graph

To create a directed graph, simply modify the graph type in Listing 3 to directedS:

#include <boost/graph/adjacency_list.hpp> using namespace boost; typedef boost::adjacency_list<listS, vecS, directedS> mygraph; int main() { mygraph g; add_edge (0, 1, g); add_edge (0, 3, g); add_edge (1, 2, g); add_edge (2, 3, g); // Same as Listing 3 }

The helper function vertices returns a std::pair<vertex_iterator and vertex_iterator>, with the former pointing to the first vertex in the graph. The result is captured in the tuple tie (vertexIt, vertexEnd), and vertexIt is subsequently used to traverse the graph. Likewise, the helper function adjacent_vertices returns std::pair<adjacency_iterator, adjacency_iterator>, with the first adjacency_iterator pointing to the first element in the adjacency list.

Configuring an adjacency list

One of the cool things about BGL is that it is highly configurable. BGL lets you configure the set of vertices and the collection of edges using any of the following selector types (these are all defined in the header; all you need to do is use them while declaring the graph):

• vecS selects std::vector
• lists for std::list
• slistS selects std::slist
• setS selects std::set
• multiSetS selects std::multiset
• hash_setS selects std::hash_set

If your code would have many vertex insertions but not much deletion, then the VertexList could be vecS or listS. push_back is usually constant time except for when a vector needs reallocation. If you will have many insertions and deletions, then a listS is a better choice than vecS, because deleting an element from a vector is usually more expensive, time wise.

Another way to create an undirected graph

Instead of using the adjacency list-based version to create an undirected graph, you can use the BGL-provided undirected_graph class (defined in undirected_graph.hpp). However, this class internally uses an adjacency list, and using graphs based on adjacency lists always provides for greater flexibility. Listing 4 shows the code.

Listing 4. Creating an undirected graph using undirected_graph.hpp

In Listing 4, I added individual vertices to a graph using add_vertex and edges using add_edge. Finally, the degree of an individual vertex is displayed using the degree method call. Listing 5 provides the declaration and definition of undirected_graph (from Boost sources).

The Boost Graph Library User Guide And Reference Manual Pdf Online

Listing 5. Deciphering a BGL undirected_graph

Tracking the in-edges and out-edges of a vertex

You access the outgoing edges of a vertex using the out_edges helper function; to access the incoming edges, use in_edges. A great thing about BGL is that you can directly output an edge using cout, and it shows the connecting vertices. Listing 6 shows the code.

Listing 6. Iterating over the edges of a directed graph

If you compiled the code in Listing 6, you would get errors. To fix the errors, just replace directedS with bidirectionalS in the declaration of mygraph. When using the directedS tag in BGL, you are allowed to use only the out_edges helper function and associated iterators. Using in_edges requires changing the graph type to bidirectionalS, although this is still more or less a directed graph.

Note: Using in_edges comes with an additional space cost (twice the per-edge cost if you compare it with directedS), so be sure it is something you can live with.

Some useful BGL functions

Now, let us take stock of some of the more important utility functions that BGL provides and that have not been discussed, yet.

You can use the following functions for graph access:

• std::pair<edge_iterator, edge_iterator> edges(const adjacency_list& g). Returns an iterator pair corresponding to the edges in graph g
• vertices_size_type num_vertices(const adjacency_list& g). Returns the number of vertices in g
• edges_size_type num_edges(const adjacency_list& g). Returns the number of edges in g
• vertex_descriptor source(edge_descriptor e, const adjacency_list& g). Returns the source vertex of an edge
• vertex_descriptor target(edge_descriptor e, const adjacency_list& g). Returns the target vertex of an edge
• degree_size_type in_degree(vertex_descriptor u, const adjacency_list& g). Returns the in-degree of a vertex
• degree_size_type out_degree(vertex_descriptor u, const adjacency_list& g). Returns the out-degree of a vertex

Listing 7 shows the code performing a fair number of graph accesses.

Listing 7. Graph accesses using BGL

You can use the following functions for graph modification:

• void remove_edge(vertex_descriptor u, vertex_descriptor v, adjacency_list& g). Removes an edge from g
• void remove_edge(edge_descriptor e, adjacency_list& g). Removes an edge from g
• void clear_vertex(vertex_descriptor u, adjacency_list& g). Removes all edges to and from u
• void clear_out_edges(vertex_descriptor u, adjacency_list& g). Removes all outgoing edges from vertex u in the directed graph g (not applicable for undirected graphs)
• void clear_in_edges(vertex_descriptor u, adjacency_list& g). Removes all incoming edges from vertex u in the directed graph g (not applicable for undirected graphs)
• void remove_vertex(vertex_descriptor u, adjacency_list& g). Removes a vertex from graph g (It is expected that all edges associated with this vertex have already been removed using clear_vertex or another appropriate function.)

Creating a directed weighted graph using BGL

Now that you are comfortable with directed graphs, the next logical task is to create a weighted directed graph with BGL. If you look back to the declaration of the adjacency list in Listing 1, you see that one of the template parameters is called EdgeProperty. It is this template parameter that you use to construct the graph.

A property is a parameter that can be assigned to both vertices and edges. You define a property using a tag name and a type corresponding to the property. BGL has several available tag names, including edge_weight_t and vertex_name_t. For example, to store names in graph vertices, you can define a property as typedef property<vertex_name_t, std::string> VertexNameProperty, and then pass this property to the VertexProperty parameter in the template declaration for the graph.

Here is the declaration for a property for edge weights:

Now that you have created EdgeWeightProperty, tweak your definition of mygraph:

Finally, when you add the edges in the graph, use the overloaded version of add_edge, which accepts a weight as the third argument. Listing 8 provides the complete code.

The Boost Graph Library User Guide And Reference Manual Pdf Free

Listing 8. Creating a weighted directed graph

A minimum spanning tree in BGL

One of the best things about BGL is that it comes with a whole host of predefined algorithms that work on graphs. Kruskal, Prim, Dijkstra—you name it and BGL has it. To see what I mean, modify the code in Listing 8 to have an undirected graph with weighted edges, and then use Kruskal's algorithm on it to get the minimum spanning tree. BGL provides individual algorithms in separate headers, so to use Kruskal, you must include boost/graph/kruskal_min_spanning_tree.hpp. Listing 9 shows the code.

Listing 9. Minimum spanning tree using Kruskal's algorithm

The function kruskal_minimum_spanning_tree does the magic behind the scenes. It takes in the graph and an iterator to a container where the edges are stored. Note the declaration of spanning_tree: I used a list here, but it can be anything—for example, a vector. All BGL cares for is that the second argument must be the Standard Template Library (STL) output-iterator type.

Depth-first search using BGL

Breadth-first search and depth-first search (DFS) form the crux of graph traversals, and BGL comes with a lot of support for these operations. The relevant header file to be included is boost/graph/depth_first_search.hpp; the corresponding routine is depth_first_search. BGL provides for multiple interfaces to depth_first_search; all of them need what is known as a visitor object to be passed to the method.

A visitor in BGL plays the role of a functor in STL except that it does a lot more. A visitor does not have a single method like operator ( ) but instead has the flexibility to define several methods, such as initialize_index, start_index, discover_index, and examine_edge. It is safe to say that BGL lets you customize the DFS by providing these hooks. Let us first look into a sample code using DFS (Listing 10).

Listing 10. DFS using BGL

Listing 10 declares a class called custom_dfs_visitor that defines two hooks: discover_vertex and examine_edges. The former is invoked when a vertex is encountered for the first time; the latter is invoked on every outgoing edge from the vertex after the vertex is discovered.

So, what would have happened if in the visitor (vis) you had vis be of type boost_default_visitor? Yes, you guessed it: nothing on the display. Table 1 provides a quick summary of some of the hooks BGL provides.

Table 1. BGL hooks for traversing using DFS

Note that BGL supports other visitors, like dijkstra_visitor, bellman_visitor, and astar_visitor.

Conclusion

That is it for this article. You have learned how to create undirected, directed, and weighted graphs in BGL; played with the accessors and modifier functions; and tried your hand at implementing some classical graph algorithms on the graphs you created. BGL offers a lot more, and this article has just skimmed the surface. Be sure to look into the BGL documentation for details.

Downloadable resources

Related topics

• Check out the BGL documentation.
• The Boost Graph Library: User Guide and Reference Manual by Jeremy G. Siek, Lie-Quan Lee, and Andrew Lumsdaine is a fantastic resource for the BGL.
• Download the BGL.

Comments

Sign in or register to add and subscribe to comments.

Boost is a set of libraries for the C++ programming language that provide support for tasks and structures such as linear algebra, pseudorandom number generation, multithreading, image processing, regular expressions, and unit testing. It contains over eighty individual libraries.

Most of the Boost libraries are licensed under the Boost Software License, designed to allow Boost to be used with both free and proprietary software projects. Many of Boost's founders are on the C++ standards committee, and several Boost libraries have been accepted for incorporation into both the C++ Technical Report 1 and the C++11 standard.^[4]

Design[edit]

The libraries are aimed at a wide range of C++ users and application domains. They range from general-purpose libraries like the smart pointer library, to operating system abstractions like Boost FileSystem, to libraries primarily aimed at other library developers and advanced C++ users, like the template metaprogramming (MPL) and domain-specific language (DSL) creation (Proto).

In order to ensure efficiency and flexibility, Boost makes extensive use of templates. Boost has been a source of extensive work and research into generic programming and metaprogramming in C++.^{[citation needed]}

Most Boost libraries are header based, consisting of inline functions and templates, and as such do not need to be built in advance of their use. Some Boost libraries coexist as independent libraries.^[5][6]

The Boost Graph Library User Guide And Reference Manual

Associated people[edit]

The original founders of Boost that are still active in the community include Beman Dawes and David Abrahams. Author of several books on C++, Nicolai Josuttis contributed to the Boost array library in 2001. There are mailing lists devoted to Boost library use and library development, active as of 2019.^[7]

License[edit]

Boost is licensed under its own free, open-source license, known as the Boost Software License.^[8] It is a permissive license in the style of the BSD license and the MIT license, but without requiring attribution for redistribution in binary form.^[9] The license has been OSI-approved since February 2008^[10][11] and is considered a free software license, compatible with the GNU General Public License, by the Free Software Foundation.^[12]

See also[edit]

• Apache Portable Runtime – used by the Apache HTTP Server
• GLib – the equivalent upon which GNOME is built
• KDE Frameworks – the equivalent upon which KDE Software Compilation is built

References[edit]

1. ^'Old Versions'. Retrieved 11 April 2017.
2. ^'Boost Releases on GitHub'. Retrieved 19 August 2019.
3. ^'Boost Version History'. Retrieved 19 August 2019.
4. ^'Library Technical Report'. JTC1/SC22/WG21 - The C++ Standards Committee. 2 July 2003. Retrieved 1 February 2012.
5. ^'Asio web site'.
6. ^'Spirit web-site'.
7. ^'Boost Mailing Lists (A.K.A. Discussion Groups)'. Retrieved 7 Apr 2019.
8. ^http://www.boost.org/LICENSE_1_0.txt
9. ^Dawes, Beman. 'Boost Software License'. Retrieved 2016-08-01.
10. ^'Boost mailing list archive'.
11. ^'Boost Software License 1.0 (BSL-1.0) | Open Source Initiative'.
12. ^'Various Licenses and Comments about Them - GNU Project - Free Software Foundation (FSF)'.

Further reading[edit]

• Demming, Robert & Duffy, Daniel J. (2010). Introduction to the Boost C++ Libraries. Volume 1 - Foundations. Datasim. ISBN978-94-91028-01-4.
• Demming, Robert & Duffy, Daniel J. (2012). Introduction to the Boost C++ Libraries. Volume 2 - Advanced Libraries. Datasim. ISBN978-94-91028-02-1.
• Mukherjee, Arindam (2015). Learning Boost C++ Libraries. Packt. ISBN978-1-78355-121-7.
• Polukhin, Antony (2013). Boost C++ Application Development Cookbook. Packt. ISBN978-1-84951-488-0.
• Polukhin, Antony (2017). Boost C++ Application Development Cookbook (2 ed.). Packt. ISBN978-1-78728-224-7.
• Schäling, Boris (2011). The Boost C++ Libraries. XML Press. ISBN978-0-9822191-9-5.
• Schäling, Boris (2014). The Boost C++ Libraries (2 ed.). XML Press. p. 570. ISBN978-1-937434-36-6.
• Siek, Jeremy G.; Lee, Lie-Quan & Lumsdaine, Andrew (2001). The Boost Graph Library: User Guide and Reference Manual. Addison-Wesley. ISBN978-0-201-72914-6.

User Guide Ipad

External links[edit]

• Official website