Using adjacency_list

1. Choosing the Edgelist and VertexList
2. Directed and Undirected Adjacency Lists
3. Internal Properties
4. Customizing the Adjacency List Storage

Choosing the Edgelist and VertexList

This section focuses on how to decide which version of the adjacency_list class to use in different situations. The adjacency_list is like a swiss-army knife in that it can be configured in many ways. The parameters that we will focus on in this section are OutEdgeList and VertexList, which control the underlying data structures that will be used to represent the graph. The choice of OutEdgeList and VertexList affects the time complexity of many of the graph operations and the space complexity of the graph object.

BGL uses containers from the STL such as std::vector, std::list, and std::set to represent the set of vertices and the adjacency structure (out-edges and in-edges) of the graph. There are several selector types that are used to specify the choice of container for OutEdgeList and VertexList.

• vecS selects std::vector.
• listS selects std::list.
• slistS selects std::slist.
• setS selects std::set.
• multisetS selects std::multiset.
• hash_setS selects boost::unordered_set.

Choosing the VertexList type

The VertexList parameter determines what kind of container will be used to represent the vertex set, or two-dimensional structure of the graph. The container must model Sequence or RandomAccessContainer. In general, listS is a good choice if you need to add and remove vertices quickly. The price for this is extra space overhead compared to choosing vecS.

Space Complexity

The std::list has a higher per-vertex space overhead than the std::vector, storing three extra pointers per vertex.

Time Complexity

The choice of VertexList affects the time complexity of the following operations.

• add_vertex()
  

  This operation is amortized constant time for both vecS and listS (implemented with push_back()). However, when the VertexList type is vecS the time for this operation is occasionally large because the vector will be reallocated and the whole graph copied.

• remove_vertex()
  

  This operation is constant time for listS and O(V + E) for vecS. The large time complexity for vecS is because the vertex descriptors (which in this case are indices that correspond to the vertices' place in the vertex list) must be adjusted in the out-edges for the whole graph.

• vertex()
  

  This operation is constant time for vecS and for listS.

Choosing the OutEdgeList type

The OutEdgeList parameter determines what kind of container will be used to store the out-edges (and possibly in-edges) for each vertex in the graph. The containers used for edge lists must either satisfy the requirements for Sequence or for AssociativeContainer.

One of the first things to consider when choosing the OutEdgeList is whether you want adjacency_list to enforce the absence of parallel edges in the graph (that is, enforce that the graph not become a multi-graph). If you want this enforced then use the setS or hash_setS selectors. If you want to represent a multi-graph, or know that you will not be inserting parallel edges into the graph, then choose one of the Sequence types: vecS, listS, or slistS. You will also want to take into account the differences in time and space complexity for the various graph operations. Below we use V for the total number of vertices in the graph and E for the total number of edges. Operations not discussed here are constant time.

Space Complexity

The selection of the OutEdgeList affects the amount of space overhead per edge in the graph object. In the order of least space to most space, the selectors are vecS, slistS, listS, and setS.

Time Complexity

In the following description of the time complexity for various operations, we use E/V inside of the ``big-O'' notation to express the length of an out-edge list. Strictly speaking this is not accurate because E/V merely gives the average number of edges per vertex in a random graph. The worst-case number of out-edges for a vertex is V (unless it is a multi-graph). For sparse graphs E/V is typically much smaller than V and can be considered a constant.

• add_edge()
  

  When the OutEdgeList is a UniqueAssociativeContainer like std::set the absence of parallel edges is enforced when an edge is added. The extra lookup involved has time complexity O(log(E/V)). The OutEdgeList types that model Sequence do not perform this check and therefore add_edge() is amortized constant time. This means that it if you don't care whether the graph has parallel edges, or know that the input to the graph does not contain them, then it is better to use the sequence-based OutEdgeList. The add_edge() for the sequence-based OutEdgeList is implemented with push_front() or push_back(). However, for std::list and std::slist this operation will typically be faster than with std::vector which occasionally reallocates and copies all elements.

• remove_edge()
  

  For sequence-based OutEdgeList types this operation is implemented with std::remove_if() which means the average time is E/V. For set-based OutEdgeList types this is implemented with the erase() member function, which has average time log(E/V).

• edge()
  

  The time complexity for this operation is O(E/V) when the OutEdgeList type is a Sequence and it is O(log(E/V)) when the OutEdgeList type is an AssociativeContainer.

• clear_vertex()
  

  For directed graphs with sequence-based OutEdgeList types the time complexity is O(V + E), while for associative container based OutEdgeList types the operation is faster, with time complexity O(V log(E/V)). For undirected graphs this operation is O(E²/V²) or O(E/V log(E/V)).

• remove_vertex()
  

  The time complexity for this operation is O(V + E) regardless of the OutEdgeList type.

• out_edge_iterator::operator++()
  

  This operation is constant time for all the OneD types. However, there is a significant constant factor time difference between the various types, which is important since this operation is the work-horse of most graph algorithms. The speed of this operation in order of fastest to slowest is vecS, slistS, listS, setS, hash_setS.

• in_edge_iterator::operator++()
  

  This operation is constant time and exhibits a similar speed ordering as the out_edge_iterator with respect to the OutEdgeList selection.

• vertex_iterator::operator++()
  

  This operation is constant time and fast (same speed as incrementing a pointer). The selection of OneD does not affect the speed of this operation.

• edge_iterator::operator++()
  

  This operation is constant time and exhibits a similar speed ordering as the out_edge_iterator with respect to the OutEdgeList selection. Traversing through the whole edge set is O(V + E).

• adjacency_iterator::operator++()
  

  This operation is constant time and exhibits a similar speed ordering as the out_edge_iterator with respect to the OutEdgeList selection.

Directed and Undirected Adjacency Lists

The adjacency_list class can be used to represent both directed and undirected graphs, depending on the argument passed to the Directed template parameter. Selecting directedS or bidirectionalS choose a directed graph, whereas undirectedS selects the representation for an undirected graph. See Section Undirected Graphs for a description of the difference between directed and undirected graphs in BGL. The bidirectionalS selector specifies that the graph will provide the in_edges() function as well as the out_edges() function. This imposes twice as much space overhead per edge, which is why in_edges() is optional.

Internal Properties

Properties can be attached to the vertices or edges of an adjacency_list graph via the property interface. The template parameters VertexProperty and EdgeProperty of the adjacency_list class are meant to be filled by these interior properties.

NOTE: The Boost Graph Library supports two interchangeable methods for specifying interior properties: bundled properties and property lists. The former is easier to use and requires less effort, whereas the latter is compatible with older, broken compilers and is backward-compatible with Boost versions prior to 1.32.0. If you absolutely require these compatibility features, read on to learn about property lists. Otherwise, we strongly suggest that you read about the bundled properties mechanism.

One may specify internal properties via property lists, which are build from instances of the property class declared as follows.

template <class PropertyTag, class T, class NextProperty = no_property>
struct property;

The PropertyTag template parameter is a tag class that simply identifies or gives a unique name to the property. There are several predefined tags, and it is easy to add more.

  struct vertex_index_t { };
  struct vertex_index1_t { };
  struct vertex_index2_t { };
  struct edge_index_t { };
  struct graph_name_t { };
  struct vertex_name_t { };
  struct edge_name_t { };
  struct edge_weight_t { };
  struct edge_weight2_t { };
  struct edge_capacity_t { };
  struct edge_residual_capacity_t { };
  struct edge_reverse_t { };
  struct vertex_distance_t { };
  struct vertex_root_t { };
  struct vertex_all_t { };
  struct edge_all_t { };
  struct graph_all_t { };
  struct vertex_color_t { };
  struct vertex_rank_t { };
  struct vertex_predecessor_t { };
  struct vertex_isomorphism_t { };
  struct vertex_invariant_t { };
  struct vertex_invariant1_t { };
  struct vertex_invariant2_t { };
  struct vertex_degree_t { };
  struct vertex_out_degree_t { };
  struct vertex_in_degree_t { };
  struct vertex_discover_time_t { };
  struct vertex_finish_time_t { };

The T template parameter of property specifies the type of the property values. The type T must be Default Constructible, Assignable, and Copy Constructible. Like the containers of the C++ Standard Library, the property objects of type T are held by-value inside of the graph.

The NextProperty parameter allows property types to be nested, so that an arbitrary number of properties can be attached to the same graph.

The following code shows how a vertex and edge property type can be assembled and used to create a graph type. We have attached a distance property with values of type float and a name property with values of type std::string to the vertices of the graph. We have attached a weight property with values of type float to the edges of the graph.

  typedef property<vertex_distance_t, float,
            property<vertex_name_t, std::string> > VertexProperty;
  typedef property<edge_weight_t, float> EdgeProperty;

  typedef adjacency_list<mapS, vecS, undirectedS,
                         VertexProperty, EdgeProperty> Graph;

  Graph g(num_vertices); // construct a graph object

The property values are then read from and written to using property maps. See Section Interior Properties for a description of how to obtain property maps from a graph, and read Section Property Maps for how to use property maps.

Custom Edge Properties

Creating your own property types and properties is easy; just define a tag class for your new property. The property tag class will need to define num with a unique integer ID, and kind which should be either edge_property_tag, vertex_property_tag, or graph_property_tag.

struct flow_t {
  typedef edge_property_tag kind;
};

struct capacity_t {
  typedef edge_property_tag kind;
};

You can also use enum's instead of struct's to create tag types. Create an enum type for each property inside the boost namespace. The first part of the name of the enum type must be edge, vertex, or graph followed by an underscore, the new property name, and a _t at the end. Inside the enum, define a value with the same name minus the _t. Then invoke the BOOST_INSTALL_PROPERTY macro.

namespace boost {
  enum edge_flow_t { edge_flow };
  enum edge_capacity_t { edge_capacity };

  BOOST_INSTALL_PROPERTY(edge, flow);
  BOOST_INSTALL_PROPERTY(edge, capacity);
}

Now you can use your new property tag in the definition of properties just as you would one of the builtin tags.

  typedef property<capacity_t, int> Cap;
  typedef property<flow_t, int, Cap> EdgeProperty;
  typedef adjacency_list<vecS, vecS, no_property, EdgeProperty> Graph;

Just as before, the property maps for these properties can be obtained from the graph via the get(Property, g) function.

  property_map<Graph, capacity_t>::type capacity
    = get(capacity_t(), G);
  property_map<Graph, flow_t>::type flow
    = get(flow_t(), G);

The file edge_property.cpp shows the complete source code for this example.

Custom Vertex Properties

Creating your own properties to attach to vertices is just as easy as for edges. Here we want to attach people's first names to the vertices in the graph.

  struct first_name_t {
    typedef vertex_property_tag kind;
  };

Now we can use the new tag in the property class and use that in the assembly of a graph type. The following code shows creating the graph type, and then creating the graph object. We fill in the edges and also assign names to the vertices. The edges will represent ``who owes who''.

  typedef property<first_name_t, std::string> FirstNameProperty;
  typedef adjacency_list<vecS, vecS, directedS,
                         FirstNameProperty> MyGraphType;

  typedef pair<int,int> Pair;
  Pair edge_array[11] = { Pair(0,1), Pair(0,2), Pair(0,3),
                          Pair(0,4), Pair(2,0), Pair(3,0),
                          Pair(2,4), Pair(3,1), Pair(3,4),
                          Pair(4,0), Pair(4,1) };

  MyGraphType G(5);
  for (int i = 0; i < 11; ++i)
    add_edge(edge_array[i].first, edge_array[i].second, G);

  property_map<MyGraphType, first_name_t>::type
    name = get(first_name_t(), G);

  boost::put(name, 0, "Jeremy");
  boost::put(name, 1, "Rich");
  boost::put(name, 2, "Andrew");
  boost::put(name, 3, "Jeff");
  name[4] = "Kinis"; // you can use operator[] too

  who_owes_who(edges(G).first, edges(G).second, G);

The who_owes_who() function written for this example was implemented in a generic style. The input is templated so we do not know the actual graph type. To find out the type of the property map for our first-name property, we need to use the property_map traits class. The const_type is used since the graph parameter is const. Once we have the property map type, we can deduce the value type of the property using the property_traits class. In this example, we know that the property's value type will be std::string, but written in this generic fashion the who_owes_who() function could work with other property value types.

  template <class EdgeIter, class Graph>
  void who_owes_who(EdgeIter first, EdgeIter last, const Graph& G)
  {
    // Access the propety acessor type for this graph
    typedef typename property_map<Graph,
      first_name_t>::const_type NameMap;
    NameMap name = get(first_name, G);

    typedef typename boost::property_traits<NameMap>
      ::value_type NameType;

    NameType src_name, targ_name;

    while (first != last) {
      src_name = boost::get(name, source(*first, G));
      targ_name = boost::get(name, target(*first, G));
      cout << src_name << " owes "
           << targ_name << " some money" << endl;
      ++first;
    }

Jeremy owes Rich some money
Jeremy owes Andrew some money
Jeremy owes Jeff some money
Jeremy owes Kinis some money
Andrew owes Jeremy some money
Andrew owes Kinis some money
Jeff owes Jeremy some money
Jeff owes Rich some money
Jeff owes Kinis some money
Kinis owes Jeremy some money
Kinis owes Rich some money

Customizing the Adjacency List Storage

The adjacency_list is constructed out of two kinds of containers. One type of container to hold all the vertices in the graph, and another type of container for the out-edge list (and potentially in-edge list) for each vertex. BGL provides selector classes that allow the user to choose between several of the containers from the STL. It is also possible to use your own container types. When customizing the VertexList you need to define a container generator as described below. When customizing the OutEdgeList you will need to define a container generator and the parallel edge traits. The file container_gen.cpp has an example of how to use a custom storage type.

Container Generator

The adjacency_list class uses a traits class called container_gen to map the OutEdgeList and VertexList selectors to the actual container types used for the graph storage. The default version of the traits class is listed below, along with an example of how the class is specialized for the listS selector.

namespace boost {
  template <class Selector, class ValueType>
  struct container_gen { };

  template <class ValueType>
  struct container_gen<listS, ValueType> {
    typedef std::list<ValueType> type;
  };
}

To use some other container of your choice, define a selector class and then specialize the container_gen for your selector.

  struct custom_containerS { }; // your selector

  namespace boost {
    // the specialization for your selector
    template <class ValueType>
    struct container_gen<custom_containerS, ValueType> {
      typedef custom_container<ValueType> type;
    };
  }

There may also be situations when you want to use a container that has more template parameters than just ValueType. For instance, you may want to supply the allocator type. One way to do this is to hard-code in the extra parameters within the specialization of container_gen. However, if you want more flexibility then you can add a template parameter to the selector class. In the code below we show how to create a selector that lets you specify the allocator to be used with the std::list.

  template <class Allocator>
  struct list_with_allocatorS { };

  namespace boost {
    template <class Alloc, class ValueType>
    struct container_gen<list_with_allocatorS<Alloc>, ValueType>
    {
      typedef typename Alloc::template rebind<ValueType>::other Allocator;
      typedef std::list<ValueType, Allocator> type;
    };
  }

  // now you can define a graph using std::list
  //   and a specific allocator
  typedef adjacency_list< list_with_allocatorS< std::allocator<int> >, vecS, directedS> MyGraph;

Push and Erase for the Custom Container

You must also tell the adjacency_list how elements can be efficiently added and removed from the custom container. This is accomplished by overloading the push() and erase() functions for the custom container type. The push() function should return an iterator pointing to the newly inserted element and a bool flag saying whether the edge was inserted.

  template <class T>
  std::pair<typename custom_container<T>::iterator, bool>
  push(custom_container<T>& c, const T& v)
  {
    // this implementation may need to change for your container
    c.push_back(v);
    return std::make_pair(boost::prior(c.end()), true);
  }

  template <class T>
  void erase(custom_container<T>& c, const T& x)
  {
    // this implementation may need to change for your container
    c.erase(std::remove(c.begin(), c.end(), x), c.end());
  }

There are default push() and erase() functions implemented for the STL container types.

Parallel Edge Traits

When customizing the OutEdgeList, you must also specialize the parallel_edge_traits class to specify whether the container type allows parallel edges (and is a Sequence) or if the container does not allow parallel edges (and is an AssociativeContainer).

  template <>
  struct parallel_edge_traits<custom_containerS> {
    typedef allow_parallel_edge_tag type;
  };