Vertices and Edges

Graphs consist of points and lines. To create a graph, you have to define a set of points and any lines between them. Example 31.1 contains a first simple graph consisting of four points and no lines.

#include <boost/graph/adjacency_list.hpp>
#include <iostream>

int main()
{
  boost::adjacency_list<> g;

  boost::adjacency_list<>::vertex_descriptor v1 = boost::add_vertex(g);
  boost::adjacency_list<>::vertex_descriptor v2 = boost::add_vertex(g);
  boost::adjacency_list<>::vertex_descriptor v3 = boost::add_vertex(g);
  boost::adjacency_list<>::vertex_descriptor v4 = boost::add_vertex(g);

  std::cout << v1 << ", " << v2 << ", " << v3 << ", " << v4 << '\n';
}

Boost.Graph provides three containers to define graphs. The most important container is boost::adjacency_list which is used in nearly all of the examples in this chapter. To use this class, include the header file boost/graph/adjacency_list.hpp. If you want to use another container, you must include another header file. There is no master header file to get access to all classes and functions from Boost.Graph.

boost::adjacency_list is a template that is instantiated with default parameters in Example 31.1. Later, you will see what parameters you can pass. This class is defined in boost. All classes and functions from Boost.Graph are defined in this namespace.

To add four points to the graph, the function boost::add_vertex() has to be called four times.

boost::add_vertex() is a free-standing function and not a member function of boost::adjacency_list. You will find there are many free-standing functions in Boost.Graph that could have been implemented as member functions. Boost.Graph is designed to be more of a generic library than an object-oriented library.

boost::add_vertex() adds a point to a graph. In graph theory, a point is called vertex, which explains the function name.

boost::add_vertex() returns an object of type boost::adjacency_list::vertex_descriptor. This object represents a newly added point in the graph. You can write the objects to standard output as shown in Example 31.1. The example displays 0, 1, 2, 3.

Example 31.1 identifies points through positive integers. These numbers are indexes to a vector that is used internally in boost::adjacency_list. It’s no surprise that boost::add_vertex() returns 0, 1, 2, and 3 since every call adds another point to the vector.

std::vector is the container boost::adjacency_list uses by default to store points. In this case, boost::adjacency_list::vertex_descriptor is a type definition for std::size_t. Because other containers can be used to store points, boost::adjacency_list::vertex_descriptor isn’t necessarily always std::size_t.

#include <boost/graph/adjacency_list.hpp>
#include <utility>
#include <algorithm>
#include <iterator>
#include <iostream>

int main()
{
  boost::adjacency_list<> g;

  boost::add_vertex(g);
  boost::add_vertex(g);
  boost::add_vertex(g);
  boost::add_vertex(g);

  std::pair<boost::adjacency_list<>::vertex_iterator,
    boost::adjacency_list<>::vertex_iterator> vs = boost::vertices(g);

  std::copy(vs.first, vs.second,
    std::ostream_iterator<boost::adjacency_list<>::vertex_descriptor>{
      std::cout, "\n"});
}

To get all points from a graph, call boost::vertices(). This function returns two iterators of type boost::adjacency_list::vertex_iterator, which refer to the beginning and ending points. The iterators are returned in a std::pair. Example 31.2 uses the iterators to write all points to standard output. This example displays the number 0, 1, 2, and 3, just like the previous example.

Example 31.3 explains how points are connected with lines.

#include <boost/graph/adjacency_list.hpp>
#include <utility>
#include <algorithm>
#include <iterator>
#include <iostream>

int main()
{
  boost::adjacency_list<> g;

  boost::adjacency_list<>::vertex_descriptor v1 = boost::add_vertex(g);
  boost::adjacency_list<>::vertex_descriptor v2 = boost::add_vertex(g);
  boost::add_vertex(g);
  boost::add_vertex(g);

  std::pair<boost::adjacency_list<>::edge_descriptor, bool> p =
    boost::add_edge(v1, v2, g);
  std::cout.setf(std::ios::boolalpha);
  std::cout << p.second << '\n';

  p = boost::add_edge(v1, v2, g);
  std::cout << p.second << '\n';

  p = boost::add_edge(v2, v1, g);
  std::cout << p.second << '\n';

  std::pair<boost::adjacency_list<>::edge_iterator,
    boost::adjacency_list<>::edge_iterator> es = boost::edges(g);

  std::copy(es.first, es.second,
    std::ostream_iterator<boost::adjacency_list<>::edge_descriptor>{
      std::cout, "\n"});
}

You call boost::add_edge() to connect two points in a graph. You have to pass the points and the graph as parameters. In graph theory, lines between points are called edges – that’s why the function is called boost::add_edge().

boost::add_edge() returns a std::pair. first provides access to the line. second is a bool variable that indicates whether the line was successfully added. If you run Example 31.3, you’ll see that p.second is set to true for each call to boost::add_edge(), and a new line is added to the graph with each call.

boost::edges() provides access to all lines in a graph. Like boost::vertices(), boost::edges() returns two iterators that refer to the beginning and ending lines. Example 31.3 writes all lines to standard output. The example displays (0,1), (0,1) and (1,0).

The output shows that the graph has three lines. All three connect the first two points – those with the indexes 0 and 1. The output also shows where the lines start and end. Two lines start at the first point, one at the second. The direction of the lines depends on the order of the parameters passed to boost::add_edge().

As you see, you can have multiple lines between the same two points. However, this feature can be deactivated.

#include <boost/graph/adjacency_list.hpp>
#include <utility>
#include <algorithm>
#include <iterator>
#include <iostream>

int main()
{
  typedef boost::adjacency_list<boost::setS, boost::vecS,
    boost::undirectedS> graph;
  graph g;

  boost::adjacency_list<>::vertex_descriptor v1 = boost::add_vertex(g);
  boost::adjacency_list<>::vertex_descriptor v2 = boost::add_vertex(g);
  boost::add_vertex(g);
  boost::add_vertex(g);

  std::pair<graph::edge_descriptor, bool> p =
    boost::add_edge(v1, v2, g);
  std::cout.setf(std::ios::boolalpha);
  std::cout << p.second << '\n';

  p = boost::add_edge(v1, v2, g);
  std::cout << p.second << '\n';

  p = boost::add_edge(v2, v1, g);
  std::cout << p.second << '\n';

  std::pair<graph::edge_iterator,
    graph::edge_iterator> es = boost::edges(g);

  std::copy(es.first, es.second,
    std::ostream_iterator<graph::edge_descriptor>{std::cout, "\n"});
}

Example 31.4 doesn’t instantiate boost::adjacency_list with default template parameters. Three parameters, called selectors, are passed in. By convention, the names of selectors end in S. These selectors determine what types will be used in boost::adjacency_list to store points and lines.

By default, boost::adjacency_list uses std::vector for points and lines. By passing boost::setS as the first template parameter in Example 31.4, std::set is selected as the container for lines. Because std::set doesn’t support duplicates, it is not possible to add the same line using boost::add_edge() multiple times. Thus, the example only displays (0,1) once.

The second template parameter tells boost::adjacency_list which class should be used for points. In Example 31.4, boost::vecS is passed. This is the default value for the second template parameter. It is only set so that you can pass a third template parameter.

The third template parameter determines whether lines are directed or undirected. The default is boost::directedS, which means all lines are directed and can be drawn as arrows. Lines can only be crossed in one direction.

boost::undirectedS is used in Example 31.4. This selector makes all lines undirected, which means it is possible to cross a line in any direction. It doesn’t matter which point is the start and which is the end. This is another reason why the graph in Example 31.4 contains only one line. The third call to the function boost::add_edge() swaps the start and end points, but because lines in this example are undirected, this line is the same as the previous lines and, therefore, isn’t added.

Boost.Graph offers more selectors, including boost::listS, boost::mapS, and boost::hash_setS. boost::bidirectionalS can be used to make lines bidirectional. This selector is similar to boost::undirectedS, but in this case, start and end points matter. If you use boost::bidirectionalS in Example 31.4, the third call to boost::add_edge() will add a line to the graph.

Example 31.5 shows a simpler method for adding points and lines to a graph.

#include <boost/graph/adjacency_list.hpp>
#include <tuple>
#include <algorithm>
#include <iterator>
#include <iostream>

int main()
{
  typedef boost::adjacency_list<boost::setS, boost::vecS,
    boost::undirectedS> graph;
  graph g;

  enum { topLeft, topRight, bottomRight, bottomLeft };

  boost::add_edge(topLeft, topRight, g);
  boost::add_edge(topRight, bottomRight, g);
  boost::add_edge(bottomRight, bottomLeft, g);
  boost::add_edge(bottomLeft, topLeft, g);

  graph::edge_iterator it, end;
  std::tie(it, end) = boost::edges(g);
  std::copy(it, end,
    std::ostream_iterator<graph::edge_descriptor>{std::cout, "\n"});
}

Example 31.5 defines a graph consisting of four points. You can visualize the graph as a map with four fields, each represented by a point. The points are given the names topLeft, topRight, bottomRight, and bottomLeft. Because the names are assigned in an enumeration, each will have a numeric value that is used as an index.

It is possible to define a graph without calling boost::add_vertex(). Boost.Graph adds missing points to a graph automatically if the points passed to boost::add_edge() don’t exist. The multiple calls to boost::add_edge() in Example 31.5 define not only lines but also add the four points required for the lines to the graph.

Please note how std::tie() is used to store the iterators returned in a std::pair from boost::edges() in it and end. std::tie() has been part of the standard library since C++11.

The graph in Example 31.5 is a map with four fields. To get from the top left to the bottom right, one can either cross the field in the top right or the one in the bottom left. There is no line between opposite fields. Thus it’s not possible to go directly from the top left to the bottom right. All examples in this chapter use this graph.

#include <boost/graph/adjacency_list.hpp>
#include <tuple>
#include <algorithm>
#include <iterator>
#include <iostream>

int main()
{
  typedef boost::adjacency_list<boost::setS, boost::vecS,
    boost::undirectedS> graph;
  graph g;

  enum { topLeft, topRight, bottomRight, bottomLeft };

  boost::add_edge(topLeft, topRight, g);
  boost::add_edge(topRight, bottomRight, g);
  boost::add_edge(bottomRight, bottomLeft, g);
  boost::add_edge(bottomLeft, topLeft, g);

  graph::adjacency_iterator vit, vend;
  std::tie(vit, vend) = boost::adjacent_vertices(topLeft, g);
  std::copy(vit, vend,
    std::ostream_iterator<graph::vertex_descriptor>{std::cout, "\n"});

  graph::out_edge_iterator eit, eend;
  std::tie(eit, eend) = boost::out_edges(topLeft, g);
  std::for_each(eit, eend,
    [&g](graph::edge_descriptor it)
      { std::cout << boost::target(it, g) << '\n'; });
}

Example 31.6 introduces functions to gain additional information on points. boost::adjacent_vertices() returns a pair of iterators that refer to points a point connects to. You call boost::out_edges() if you want to access all outgoing lines from a point. boost::in_edges() accesses all ingoing lines. With undirected lines, it doesn’t matter which of the two functions is called.

boost::target() returns the end point of a line. The start point is returned with boost::source().

Example 31.6 writes 1 and 3, the indexes of the top right and bottom left fields, to standard output twice. boost::adjacent_vertices(), is called with topLeft and returns and displays the indexes of the top right and bottom left fields. topLeft is also passed to boost::out_edges() to retrieve the outgoing lines. Because boost::target() is called on every outgoing line with std::for_each(), the indexes of the top right and bottom left fields are displayed twice.

Example 31.7 illustrates how to define a graph with boost::adjacency_list without having to call boost::add_edge() for every line.

#include <boost/graph/adjacency_list.hpp>
#include <array>
#include <utility>
#include <iostream>

int main()
{
  enum { topLeft, topRight, bottomRight, bottomLeft };

  std::array<std::pair<int, int>, 4> edges{{
    std::make_pair(topLeft, topRight),
    std::make_pair(topRight, bottomRight),
    std::make_pair(bottomRight, bottomLeft),
    std::make_pair(bottomLeft, topLeft)
  }};

  typedef boost::adjacency_list<boost::setS, boost::vecS,
    boost::undirectedS> graph;
  graph g{edges.begin(), edges.end(), 4};

  std::cout << boost::num_vertices(g) << '\n';
  std::cout << boost::num_edges(g) << '\n';

  g.clear();
}

You can pass iterators to the constructor of boost::adjacency_list that refer to objects of type std::pair<int, int>, which define lines. If you pass iterators, you also have to supply a third parameter that determines the total number of points in the graph. The graph will contain at least the points required for the lines. The third parameter let’s you add points to the graph that aren’t connected to other points.

Example 31.7 uses the functions boost::num_vertices() and boost::num_edges(), which return the number of points and lines, respectively. The example displays 4 twice.

Example 31.7 calls boost::adjacency_list::clear(). This member function removes all points and lines. It is a member function of boost::adjacency_list and not a free-standing function.