boost graph understanding vertex creation behaviour

Question

I am trying to figure out the behaviour of the vertex creation when using the add_edge function. Here is an example:

#include <iostream> 
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/graph_traits.hpp>

using namespace boost;
typedef adjacency_list<> Graph;
typedef graph_traits<Graph>::vertex_iterator v_iter;

Graph g;
add_edge(1,2,g);
add_edge(1,4,g);
add_edge(2,3,g);
add_edge(2,6,g);

    std::cout << "num edges: " << num_edges(g) << "; num vertices: " << num_vertices(g) << std::endl;
for (std::pair<v_iter,v_iter> vp = vertices(g);  vp.first != vp.second; vp.first++) {
    std::cout << *vp.first << " ";
}

returns:

bash-3.2$ ./main
num edges: 4; num vertices: 7
0 1 2 3 4 5 6

Why are these vertices being created? The graph has 1,2,3,4 and 6 as vertices, 5 in total not 7. It seems that the function creates vertices from 0 to the highest value of a vertice.

I really don"t know whats going on here, so any help is greatly appreciated.

Thank you very much in advance.

sehe · Answer 1 · 2014-09-09T08:34:25.593

An adjacency list stores adjacent node for every vertex:

enter image description here

As per the docs:

VertexList The selector for the container used to represent the vertex-list of the graph.
Default: vecS

This means that the index into the vector is the the vertex ID. You cannot have a vector that contains index 1, but no index 0. Therefore, you get all intermediate indices "for free".

Of course, you can tweak this: use e.g. a listS for the vertex list: See it Live On Coliru

#include <iostream> 
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/graph_traits.hpp>
#include <algorithm>

using namespace boost;
typedef adjacency_list<boost::listS> Graph;
typedef graph_traits<Graph>::vertex_iterator v_iter;

int main()
{
    Graph g;

    graph_traits<Graph>::vertex_descriptor v[] = {
        {}, // unused
        add_vertex(g), add_vertex(g), add_vertex(g),
        add_vertex(g), add_vertex(g), add_vertex(g),
    };

    add_edge(v[1], v[2], g);
    add_edge(v[1], v[4], g);
    add_edge(v[2], v[3], g);
    add_edge(v[2], v[6], g);

    std::cout << "num edges: " << num_edges(g) << "; num vertices: " << num_vertices(g) << std::endl;
    for (std::pair<v_iter, v_iter> vp = vertices(g); vp.first != vp.second; ++vp.first) {
        std::cout << std::distance(v, std::find(std::begin(v), std::end(v), *vp.first)) << " ";
    }
}

Prints

num edges: 4; num vertices: 6
1 2 3 4 5 6 Press any key to continue . . .

@VincentGrunert Cheers. And here's a version without the extra array for presentational purposes (so slightly more real life, as you would just print another vertex property instead of the index in real life): http://coliru.stacked-crooked.com/a/df42441985e4f92b — sehe, Sep 09 '14 at 08:26

Vincent · Answer 2 · 2014-09-09T08:20:40.067

0

Just figured it out: the values are treated as indexes. For example:

add_edge(1,200);

assumes that there are actually 200 vertices and connects the second with the 201 vertex. Apparently, all vertices in between are automatically being created.

Bw

edited Sep 09 '14 at 08:20

answered Sep 09 '14 at 08:09

Vincent

1,361
2
20
33

you probably mean add_edge () :) – user1767754 Sep 09 '14 at 08:11
indeed =), just changed it – Vincent Sep 09 '14 at 08:21

score 0 · Answer 3 · answered Sep 09 '14 at 08:10

0

It will create as many Vertices as the highest Number, this means, when you write

add_edge(60)

you will have 61 vertices starting by 0

answered Sep 09 '14 at 08:10

user1767754

23,311
18
141
164

thanks, your absolutly right. Took me a while to figure out the obvious. – Vincent Sep 09 '14 at 08:21

boost graph understanding vertex creation behaviour

3 Answers3

Linked