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 IndexPair;
std::vector<IndexPair> edges;
// fill edges with pairs of integers, in range [0, 111] (at the moment)
using namespace boost;
typedef property GraphProperty;
typedef adjacency_list 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
