boost graph understanding vertex creation behaviou

问题:

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.

回答1:

An adjacency list stores adjacent node for every vertex:

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 . . .

回答2:

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

回答3:

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