CODEWITHSUNDEEP
c++boost
Don
Don

Reputation: 77

C++ Boost Graph - Why do I have an additional vertex?

I have a graph whose vertex and edge are of custom type. In my example below, I created the graph with 4 vertices and 4 edges. When I iterate through the vertices to print it however, the system outputs a total of 5 vertices. I am unsure what I did wrong and I hope someone would be able to enlighten me on this.

struct Vertex { int id; double data; };
struct Edge { float distance; };

int main(int, char** argv)
{

typedef boost::adjacency_list<boost::listS, boost::vecS, boost::directedS, Vertex, Edge> Graph;

//instantiate a graph
Graph g;

//add vertices
boost::add_vertex(Vertex{ 1, 1.1 }, g);
boost::add_vertex(Vertex{ 2, 2.2 }, g);
boost::add_vertex(Vertex{ 3, 3.3 }, g);
boost::add_vertex(Vertex{ 4, 4.4 }, g);

boost::add_edge(1, 2, g);
boost::add_edge(1, 4, g);
boost::add_edge(2, 4, g);   
boost::add_edge(1, 3, g);

// Iterate through the vertices and print them out
typedef boost::graph_traits<Graph>::vertex_iterator vertex_iter;
std::pair<vertex_iter, vertex_iter> vp;
for (vp = boost::vertices(g); vp.first != vp.second; vp.first++)
    std::cout << g[*(vp.first)].id << " " << g[*(vp.first)].data << std::endl;

// Iterate through the edges and print them out
auto es = boost::edges(g);
for (auto eit = es.first; eit != es.second; ++eit) {
    std::cout << boost::source(*eit, g) << ' ' << boost::target(*eit, g) << std::endl;
}

the output are as follows

1 1.1
2 2.2
3 3.3
4 4.4
0 0
1 2
1 4
1 3
2 4

Upvotes: 1

Views: 130

Answers (1)

eerorika
eerorika

Reputation: 238351

From the docs:

If the VertexList of the graph is vecS, then the graph has a builtin vertex indices accessed via the property map for the vertex_index_t property. The indices fall in the range [0, num_vertices(g)) and are contiguous.

The description of add_vertex doesn't say it explicitly, but I believe that the above necessitates that adding vertex with descriptor u into a graph must create vertices 0 through u if any of them don't already exist. Fundamentally, it just resizes the vertex vector to the size u + 1, so that u becomes a valid index.

Upvotes: 2

Related Questions