提高认识图形顶点创作行为 [英] boost graph understanding vertex creation behaviour

问题描述

我想使用的add_edge功能时找出顶点创作的行为。下面是一个例子：

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 << " ";
}

返回：

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

为什么要创建这些顶点？该图总共有1,2,3,4和6个顶点，5不是7.看来，函数创建从0到顶点的最高值顶点。

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.

我真不知道什么怎么回事，所以任何帮助是极大的AP preciated。

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

非常感谢你在前进。

推荐答案

对于每个顶点邻接表店相邻节点：

An adjacency list stores adjacent node for every vertex:

根据文档：

VertexList时为用于重新present图的顶点列表容器中的选择器。结果，
  默认值：血管内皮细胞

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

这意味着，在索引载体与顶点ID。你不能有一个包含索引1的向量，但没有指标0。因此，你得到所有的中间指标免费。

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

当然，你可以调整这一点：例如使用一个列出为顶点列表：看到它的 直播在Coliru

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)) << " ";
    }
}

打印

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

这篇关于提高认识图形顶点创作行为的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！