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