[Boost-users] Missing something about Boost.Graph

Subject: [Boost-users] Missing something about Boost.Graph
From: Dominique Devienne (ddevienne_at_[hidden])
Date: 2015-10-28 04:52:33

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