如何在Boost Graph Library中通过add_vertex()设置自定义vertex_descriptor

背景与问题重现 #

我正在学习Boost Graph Library（BGL），编写代码从文本文件读取数据构建图。文本文件格式为：首行是节点数，第二行是边数，后续每行描述顶点连接关系及边权重，数据如下：

8
16
4 5 0.35
4 7 0.37
5 7 0.28
0 7 0.16
1 5 0.32
0 4 0.38
2 3 0.17
1 7 0.19
0 2 0.26
1 2 0.36
1 3 0.29
2 7 0.34
6 2 0.40
3 6 0.52
6 0 0.58
6 4 0.93

编写的代码 #

主程序代码

#include <unordered_map>
#include <fstream>
#include <boost/graph/adjacency_list.hpp>
#include <boost/config.hpp>
#include <boost/algorithm/string/split.hpp>

int main() {
  // read in the graph from 'tiny-ewg.txt'
  std::ifstream datafile("tiny-ewg.txt");

  if (!datafile) {
    std::cerr << "tiny-ewg.txt was not found" << std::endl;
    return EXIT_FAILURE;
  };

  typedef boost::adjacency_list
  <boost::vecS,
   boost::vecS, 
   boost::undirectedS,
   boost::property<boost::vertex_index_t, size_t>,
   boost::property<boost::edge_weight_t, double>
  > Graph;

  typedef std::pair<int, int> Edge;

  // read in number of vertices
  std::string line;
  std::getline(datafile, line);
  const int num_vertices = std::stoi(line);

  // read in number of edges
  std::getline(datafile, line);
  const int num_edges = std::stoi(line);

  Graph g(num_vertices);

  // unordered map tiny_ewg_vertex to vertex_descriptor
  typedef boost::graph_traits<Graph>::vertex_descriptor Vertex;
  typedef std::unordered_map<int, Vertex> VertexMap;
  VertexMap vertex_map;

  // property map for the edge weight
  boost::property_map<Graph, boost::edge_weight_t>::type weight_map = 
  boost::get(boost::edge_weight, g);

  for (std::string line; std::getline(datafile, line);) {
    std::cout << line << std::endl;
    typedef std::vector<std::string> Tokens;
    Tokens tokens;
    boost::split(tokens, line, boost::is_any_of(" "));
  
    auto tok_it = tokens.begin();
    bool inserted;
    Vertex u, v;
    VertexMap::iterator pos;
    boost::tie(pos, inserted) = vertex_map.insert(std::make_pair(stoi(*tok_it), Vertex()));
    if (inserted) {
      u = boost::add_vertex(g);
      pos->second = u;
    } else {
      u = pos->second;
    }

    tok_it++;
 
    boost::tie(pos, inserted) = vertex_map.insert(std::make_pair(stoi(*tok_it), Vertex()));
    if (inserted) {
      v = boost::add_vertex(g);
      pos->second = v;
    } else {
      v = pos->second;
    }

    // add edge between u and v
    boost::graph_traits<Graph>::edge_descriptor e;
    boost::tie(e, inserted) = boost::add_edge(u, v, g);

    // add the weight to the edge using a weight property map
    if (inserted) {
      tok_it++;
      weight_map[e] = stod(*tok_it);
    }
  }
}

打印边的函数

template<typename Graph, typename WeightMap>
void printEdges(const Graph& g, WeightMap w) {
  typename typedef boost::graph_traits<Graph>::edge_iterator EdgeIterator;
  EdgeIterator it, end;
  for (boost::tie(it, end) = boost::edges(g); it != end; ++it) {
    std::cout << boost::source(*it, g) << "  " << " --( " << w[*it] << " )--> " << "  " << 
    boost::target(*it, g) << std::endl; 
  }
}

运行结果 #

运行后输出的边不符合预期，例如期望输出4 --(0.35)--> 5，实际得到：

8   --( 0.35 )-->   9
8   --( 0.37 )-->   10
9   --( 0.28 )-->   10
11   --( 0.16 )-->   10
12   --( 0.32 )-->   9
11   --( 0.38 )-->   8
13   --( 0.17 )-->   14
12   --( 0.19 )-->   10
11   --( 0.26 )-->   13
12   --( 0.36 )-->   13
12   --( 0.29 )-->   14
13   --( 0.34 )-->   10
15   --( 0.4 )-->   13
14   --( 0.52 )-->   15
15   --( 0.58 )-->   11
15   --( 0.93 )-->   8

打印vertex_map的结果：

4 : 8
5 : 9
7 : 10
0 : 11
1 : 12
2 : 13
3 : 14
6 : 15

可以看到map的键正确，但boost::add_vertex(g)返回的vertex_descriptor与预期索引不符，现提出以下技术问题：

• 是否可以设置自定义vertex_descriptor？若可以，如何操作？
• BGL的vertex_descriptor生成规则是什么？例如为何代码中第一个新增的vertex_descriptor是8而非0？
• 应该直接使用vertex_descriptor，还是使用vertex_index更合适？

内容的提问来源于stack exchange，提问作者Blargian