Don - 4 years ago 88

C++ Question

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

Recommended for you: Get network issues from **WhatsUp Gold**. **Not end users.**

Answer Source

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.

Recommended from our users: **Dynamic Network Monitoring from WhatsUp Gold from IPSwitch**. ** Free Download**