(C++) boost::adjacency_list tutorial #1

Goal of this tutorial:

Create a boost::adjacency_list
Add edges and vertices
Display the boost::adjacency_list on screen

In the code below the default directed graph is used. After creating some vertices, each vertex is connected to all subsequent vertices. Then all these (out-edge) connections are shown on screen.

include <iostream>

include <cassert>

include <boost/graph/adjacency_list.hpp>


int main()
{
  //Create a graph
  boost::adjacency_list<> myGraph; //With some compilers you can leave out the <>
  //See if it is indeed empty
  assert(boost::num_vertices(myGraph)==0);
  assert(boost::num_edges(myGraph)==0);
  //Add vertices and edges
  {
    //Create some vertices
    const int nVertices = 10;
    for(int i = 0; i!=nVertices; ++i)
    {
      boost::add_vertex(myGraph);
    }
    //Connect each vertex to all next vertices
    for(int i = 0; i!=nVertices; ++i) //'-1' as the last vertex has no out-edge
    {
      for(int j=i+1; j!=nVertices; ++j)
      {
        boost::add_edge(i,j,myGraph);
      }
    }
    assert(boost::num_vertices(myGraph)==nVertices);
    assert(boost::num_edges(myGraph) == ((nVertices * (nVertices-1))) / 2 );
  }
  //Display the structure on screen
  {
define I_LOVE_USING_CONST

    //Some handy typedefs
    typedef boost::graph_traits < boost::adjacency_list <> >::vertex_iterator VertexIterator;
    typedef boost::graph_traits < boost::adjacency_list <> >::adjacency_iterator AdjacencyIterator;
    typedef boost::property_map < boost::adjacency_list <>, boost::vertex_index_t >::type IndexMap;
      
    //Get a property map. This property we need is the boost::vertex_index
    const IndexMap myIndexMap = boost::get(boost::vertex_index, myGraph);
ifdef I_LOVE_USING_CONST    

      //Set an active vertex iterator at the first vertex
      VertexIterator vertexIterator = boost::vertices(myGraph).first;
      //Set a const vertex iterator beyond the last vertex
      const VertexIterator vertexIteratorEnd = boost::vertices(myGraph).second;
else 

      //Set an active vertex iterator at the first vertex
      //and set another vertex iterator beyond the last vertex
      VertexIterator vertexIterator, vertexIteratorEnd;
      boost::tie(vertexIterator, vertexIteratorEnd) = boost::vertices(myGraph); 
endif


    for ( ; vertexIterator != vertexIteratorEnd; ++vertexIterator) 
    {
      //Show the focal vertex's index
      std::cout << "The vertex at index " << boost::get(myIndexMap, *vertexIterator);
      
      //Get the adjacent vertices
ifdef I_LOVE_USING_CONST

        //Set the active iterator to the first adjecent vertex
        AdjacencyIterator adjacencyIterator 
          = boost::adjacent_vertices(*vertexIterator, myGraph).first;
        //Set a const iterator to beyond the last adjecent vertex
        const AdjacencyIterator adjacencyIteratorEnd 
          = boost::adjacent_vertices(*vertexIterator, myGraph).second;
else

        //Set the active iterator to the first adjecent vertex
        //and set another iterator to beyond the last adjecent vertex
        AdjacencyIterator adjacencyIterator, adjacencyIteratorEnd;
        boost::tie(adjacencyIterator, adjacencyIteratorEnd) 
          = boost::adjacent_vertices(*vertexIterator, myGraph);
endif


      //Work through the range of the AdjecentIterators
      if (adjacencyIterator == adjacencyIteratorEnd)
      { //There is no range, in other words: the vertex has no out-edge
        std::cout << " is not connected." << std::endl;
      }
      else
      { //There is a range, in other words: the vertex has at least one out-edge
        std::cout << " is connected to ";
        //Loop through all vertices the focal vertex is connected to
        for (  ; adjacencyIterator != adjacencyIteratorEnd; ++adjacencyIterator) 
        {
          //Display the index of the vertex the focal vertex is connected to
          std::cout << boost::get(myIndexMap, *adjacencyIterator) << " ";
        }
        std::cout << std::endl;
      }
    } //Next vertex..
  //Done displaying the structure on screen
  } 
}

A #define was put in, to show the constness of the ?iterators. It also avoids using boost::tie, which might look difficult for programmers not used to this function.

boost::adjacency_list tutorials

Code links

last edited (March 7, 2007) by bilderbikkel, Number of views: 2278, Current Rev: 12 (Diff)

[Edit this page] [Page history] [What links here] [Discuss this topic] [Printer Friendly]