We have a graph of relational tables, with the foreign keys being the edges of the graph. We're using boost::topological_sort() to sort the graph, and have struggled in the past with Boost.Graph. Recently we had cycles appearing in our graph, so I'm revisiting this code, and I think I must be missing something fundamental about Boost.Graph, because I get what I consider incoherent results. Here are the relevant code snippets. typedef std::pair<std::size_t, std::size_t> IndexPair; std::vector<IndexPair> edges; // fill edges with pairs of integers, in range [0, 111] (at the moment) using namespace boost; typedef property<vertex_color_t, default_color_type> GraphProperty; typedef adjacency_list<vecS, vecS, directedS, GraphProperty> Graph; typedef boost::graph_traits<Graph>::vertex_descriptor Vertex; Graph G(edges.begin(), edges.end(), edges.size()); size_t max_vrtx_index = 0; for (const auto& e : boost::make_iterator_range(boost::edges(G))) { size_t s = boost::source(e, G); size_t t = boost::target(e, G); max_vrtx_index = std::max(max_vrtx_index, s); max_vrtx_index = std::max(max_vrtx_index, t); } const auto G_vrtx_count = num_vertices(G); const auto G_edge_count = num_edges(G); if (G_vrtx_count != (max_vrtx_index + 1)) { std::cout << "Graph has " << G_vrtx_count << " vertices " "and " << G_edge_count << " edges, yet in reality " "our edges refer to at most " << max_vrtx_index << " vertices!" << std::endl; } This outputs: Graph has 1137 vertices and 1137 edges, yet in reality our edges refer to at most 111 vertices! How can num_vertices() and num_edges() return the same number? Why isn't num_vertices() returning 112 as I'd expect? I'm using 1.58. Thanks, --DD