boost graph library example does not compile

Question

I need to do a topological sorting on a graph. Boost graph library can do it. However, an exmaple I found on this site does not compile. The error is "no member named "topological_sort" in namespace boost. What is causing this error ?

#include <iostream>
#include <utility>
#include <algorithm>
#include <vector>

#include "boost/graph/graph_traits.hpp"
#include "boost/graph/adjacency_list.hpp"

using namespace boost;

int main(int argc, char *argv[])
{
  typedef adjacency_list<vecS, vecS, undirectedS> UndirectedGraph;

  //Our set of edges, which basically are just converted into ints (0-4)
  enum {A, B, C, D, E, N};
  const char *name = "ABCDE";

  //An edge is just a connection between two vertitices. Our verticies above
  //are an enum, and are just used as integers, so our edges just become
  //a std::pair<int, int>
  typedef std::pair<int, int> Edge;

  //Example uses an array, but we can easily use another container type
  //to hold our edges.
  std::vector<Edge> edgeVec;
  edgeVec.push_back(Edge(A,B));
  edgeVec.push_back(Edge(A,D));
  edgeVec.push_back(Edge(C,A));
  edgeVec.push_back(Edge(D,C));
  edgeVec.push_back(Edge(C,E));
  edgeVec.push_back(Edge(B,D));
  edgeVec.push_back(Edge(D,E));

  //Now we can initialize our graph using iterators from our above vector
  UndirectedGraph g(edgeVec.begin(), edgeVec.end(), N);

  std::cout << num_edges(g) << "\n";

  //Ok, we want to see that all our edges are now contained in the graph
  typedef graph_traits<UndirectedGraph>::edge_iterator edge_iterator;

  //Tried to make this section more clear, instead of using tie, keeping all
  //the original types so it's more clear what is going on
  std::pair<edge_iterator, edge_iterator> ei = edges(g);
  for(edge_iterator edge_iter = ei.first; edge_iter != ei.second; ++edge_iter) {
      std::cout << "(" << source(*edge_iter, g) << ", " << target(*edge_iter, g) << ")\n";
  }

  std::cout << "\n";
  //Want to add another edge between (A,E)?
  add_edge(A, E, g);

  //Print out the edge list again to see that it has been added
  for(edge_iterator edge_iter = ei.first; edge_iter != ei.second; ++edge_iter) {
      std::cout << "(" << source(*edge_iter, g) << ", " << target(*edge_iter, g) << ")\n";
  }

  //Finally lets add a new vertex - remember the verticies are just of type int
  int F = add_vertex(g);
  std::cout << F << "\n";

  //Connect our new vertex with an edge to A...
  add_edge(A, F, g);

  //...and print out our edge set once more to see that it was added
  for(edge_iterator edge_iter = ei.first; edge_iter != ei.second; ++edge_iter) {
      std::cout << "(" << source(*edge_iter, g) << ", " << target(*edge_iter, g) << ")\n";
  }

  std::deque<int> topo_order;
  boost::topological_sort(g, std::front_inserter(topo_order));
  /*
  for(std::deque<int>::const_iterator i = topo_order.begin();
      i != topo_order.end();
      ++i)
  {
      cout << index(*i) << endl;
  }
  */

  for(auto i: topo_order)
  {
      std::cout << i << std::endl;
  }
  return 0;
}

I have copied and pasted the code into a qtcreator empty project file. My config uses c++11.

Answer 1

The reason for the error is that you're missing the include of topological_sort.hpp from the boost library.

#include "boost/graph/topological_sort.hpp"

This minimal example (a stripped down version of the code in your question) compiles successfully:

#include <deque>

#include "boost/graph/graph_traits.hpp"
#include "boost/graph/adjacency_list.hpp"
#include "boost/graph/topological_sort.hpp"

using namespace boost;

int main(int argc, char *argv[])
{
  typedef adjacency_list<vecS, vecS, undirectedS> UndirectedGraph;
  UndirectedGraph g;
  std::deque<int> topo_order;
  boost::topological_sort(g, std::front_inserter(topo_order));
}