如何使用 add_vertex() 将自定义 vertex_descriptor 设置为自己的值 - Boost Graph Library

问题描述 投票：0回答：1

我正在学习 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
而不是 
4 5 0.35
，但是我最终得到以下结果：

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

如果我打印出 unordered_map 

vertex_map
我得到：

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

这样我确认我的 unordered_map 的键已正确添加，但是 

u
返回的 vertex_descriptors 
v
,
boost::add_vertex(g);
与这些索引不同。我知道可以在调用 
add_vertex
时使用额外的命名参数来设置顶点的属性，但我发现 BGL 网站上的相关文档非常差。

  • 是否可以设置自定义 vertex_descriptor 以及如何设置？
  • BGL 是如何想出什么来设置顶点描述符的。例如为什么是 上面代码中第一个元素的vertex_descriptor添加了8而不是0？
  • 是否应该尝试使用 vertex_descriptor，或者使用 顶点索引？
c++ graph boost boost-graph
1个回答
0
投票

主要问题可能是您在将图形预先调整为 

add_vertex
² 后使用了 
num_vertices
。但既然你是来学习 BGL 的，那么让我们更深入地研究一下吧！

简化

让我们简化整个代码：

住在Coliru

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/graph_utility.hpp>
#include <fstream>
#include <iostream>

struct NL_t {
    friend std::istream& operator>>(std::istream& is, NL_t) { return is.ignore(std::numeric_limits<std::streamsize>::max(), '\n'); }
} inline constexpr NL;

using Graph  = boost::adjacency_list<              //
    boost::vecS, boost::vecS, boost::undirectedS, //
    boost::no_property,                           //
    boost::property<boost::edge_weight_t, double>>;
using Vertex = boost::graph_traits<Graph>::vertex_descriptor;

Graph read_ewg(std::string fname) {
    std::ifstream datafile;
    datafile.exceptions(std::ios::failbit);
    datafile.open(fname);

    size_t nv = 0, ne = 0;
    datafile >> nv >> NL >> ne >> NL;

    Graph g(nv);
    Vertex u, v;
    double w;
    while (ne-- && datafile >> u >> v >> w >> NL)
        /*auto [e, inserted] =*/add_edge(u, v, w, g);

    assert(nv == num_vertices(g));
    return g;
}

int main() {
    auto g = read_ewg("tiny-ewg.txt");
    // auto weight_map = get(boost::edge_weight, g);

    print_graph(g);
}

印刷

0 <--> 7 4 2 6 
1 <--> 5 7 2 3 
2 <--> 3 0 1 7 6 
3 <--> 2 1 6 
4 <--> 5 7 0 6 
5 <--> 4 7 1 
6 <--> 2 3 0 4 
7 <--> 4 5 0 1 2

奖金

我们也简化一下

printEdges
（稍微将输出更改为 no 较长意味着有向边）：

template <typename Graph, typename WeightMap> //
void printEdges(Graph const& g, WeightMap w) {
    for (auto e : make_iterator_range(edges(g)))
        std::cout << e << " w:" << w[e] << "\n";
}

打印现场直播 科利鲁

(4,5) w:0.35
(4,7) w:0.37
(5,7) w:0.28
(0,7) w:0.16
(1,5) w:0.32
(0,4) w:0.38
(2,3) w:0.17
(1,7) w:0.19
(0,2) w:0.26
(1,2) w:0.36
(1,3) w:0.29
(2,7) w:0.34
(6,2) w:0.4
(3,6) w:0.52
(6,0) w:0.58
(6,4) w:0.93

请注意，使用 

vecS
顶点容器选择器意味着内置的顶点索引等于顶点描述符。因此：

  1. 我们删除了 
    vertex_index_t
    属性，它只会与内置索引混淆
  2. 由于 
    add_edge
    会自动增长我们根本没有 
    add_vertex
    的顶点“空间”，
  3. 我们只是根据需要添加边缘，并立即设置权重属性

现在的结果正是你所期望的。

如果一切都不是一首快乐的歌怎么办？

出现这种情况的唯一原因是顶点已经映射到源中的范围

[0..num_vertices(g))
。如果您将 
4
重命名为 
14
，第一个边缘读取 
14 15 0.35
，您会看到 ¹:

0 <--> 7 14 2 6
1 <--> 5 7 2 3
2 <--> 3 0 1 7 6
3 <--> 2 1 6
4 <-->
5 <--> 14 7 1
6 <--> 2 3 0 14
7 <--> 14 5 0 1 2
8 <-->
9 <-->
10 <-->
11 <-->
12 <-->
13 <-->
14 <--> 5 7 0 6

如果您只关注边缘，那么这并不是什么问题，例如

printEdges
：

(14,5) w:0.35
(14,7) w:0.37
(5,7) w:0.28
(0,7) w:0.16
(1,5) w:0.32
(0,14) w:0.38
(2,3) w:0.17
(1,7) w:0.19
(0,2) w:0.26
(1,2) w:0.36
(1,3) w:0.29
(2,7) w:0.34
(6,2) w:0.4
(3,6) w:0.52
(6,0) w:0.58
(6,14) w:0.93

但是，当源图看起来像这样时，您可能会发现问题

2
1
1236748 845723489 5.05

顶点容器的（重新）分配导致我的机器上出现 OOM。那是在 CPU 运行 30 秒之后。 （所以，在你的机器上尝试之前要小心！）

更一般地说，如果输入是

8
16
Barcelona Athens 0.35
Amsterdam Barcelona 0.37
London Barcelona 0.28
Paris Barcelona 0.16
Berlin London 0.32
Paris Amsterdam 0.38
Rome Madrid 0.17
Berlin Barcelona 0.19
Paris Rome 0.26
Berlin Rome 0.36
Berlin Madrid 0.29
Rome Barcelona 0.34
Athens Rome 0.40
Madrid Athens 0.52
Athens Paris 0.58
Athens Amsterdam 0.93

名字

嗯，很高兴你问。我会使用捆绑属性来表达逻辑 id（它永远不会成为顶点描述符，更不用说 BGL 的顶点索引了）：

struct VertexProps {
    std::string id;
};

struct EdgeProps {
    double weight;
};

using Graph  = boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS, VertexProps, EdgeProps>;
using Vertex = boost::graph_traits<Graph>::vertex_descriptor;

现在天真的编辑将几乎做我们需要的事情：

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/graph_utility.hpp>
#include <fstream>
#include <iostream>

template <typename Graph, typename WeightMap> //
void printEdges(Graph const& g, WeightMap w) {
    for (auto e : make_iterator_range(edges(g)))
        std::cout << e << " w:" << w[e] << "\n";
}

struct NL_t {
    friend std::istream& operator>>(std::istream& is, NL_t) { return is.ignore(std::numeric_limits<std::streamsize>::max(), '\n'); }
} inline constexpr NL;

using Id = std::string;
struct VertexProps {
    Id id;
};

struct EdgeProps {
    double weight;
};

using Graph  = boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS, VertexProps, EdgeProps>;
using Vertex = boost::graph_traits<Graph>::vertex_descriptor;

Graph read_ewg(std::string fname) {
    std::ifstream datafile;
    datafile.exceptions(std::ios::failbit);
    datafile.open(fname);

    size_t nv = 0, ne = 0;
    datafile >> nv >> NL >> ne >> NL;

    Graph g;
    Id u, v;
    double w;
    while (ne-- && datafile >> u >> v >> w >> NL)
        add_edge(add_vertex({u}, g), add_vertex({v}, g), {w}, g);

    assert(nv == num_vertices(g));
    return g;
}

int main() {
    auto g = read_ewg("tiny-ewg.txt");
    auto weight_map = get(&EdgeProps::weight, g);
    print_graph(g, get(&VertexProps::id, g));
    printEdges(g, weight_map);
}

印刷

Athens <--> Barcelona 
Barcelona <--> Athens 
Barcelona <--> Amsterdam 
Amsterdam <--> Barcelona 
Barcelona <--> London 
London <--> Barcelona 
Barcelona <--> Paris 
Paris <--> Barcelona 
London <--> Berlin 
Berlin <--> London 
Amsterdam <--> Paris 
Paris <--> Amsterdam 
Madrid <--> Rome 
Rome <--> Madrid 
Barcelona <--> Berlin 
Berlin <--> Barcelona 
Rome <--> Paris 
Paris <--> Rome 
Rome <--> Berlin 
Berlin <--> Rome 
Madrid <--> Berlin 
Berlin <--> Madrid 
Barcelona <--> Rome 
Rome <--> Barcelona 
Rome <--> Athens 
Athens <--> Rome 
Athens <--> Madrid 
Madrid <--> Athens 
Paris <--> Athens 
Athens <--> Paris 
Amsterdam <--> Athens 
Athens <--> Amsterdam

还有

(1,0) w:0.35
(3,2) w:0.37
(5,4) w:0.28
(7,6) w:0.16
(9,8) w:0.32
(11,10) w:0.38
(13,12) w:0.17
(15,14) w:0.19
(17,16) w:0.26
(19,18) w:0.36
(21,20) w:0.29
(23,22) w:0.34
(25,24) w:0.4
(27,26) w:0.52
(29,28) w:0.58
(31,30) w:0.93

重复数据删除

显然问题是具有相同 id 的顶点重复。

您可以像使用地图一样进行操作：

std::map<Id, Vertex> vmap;

auto ensure_vertex = [&](Id const& id) {
    auto it = vmap.find(id);
    if (it == vmap.end())
        it = vmap.emplace(id, add_vertex(VertexProps{id}, g)).first;
    return it->second;
};

while (ne-- && datafile >> u >> v >> w >> NL)
    add_edge(ensure_vertex(u), ensure_vertex(v), {w}, g);

打印 在 Coliru 上直播

Athens <--> Barcelona Rome Madrid Paris Amsterdam 
Barcelona <--> Athens Amsterdam London Paris Berlin Rome 
Amsterdam <--> Barcelona Paris Athens 
London <--> Barcelona Berlin 
Paris <--> Barcelona Amsterdam Rome Athens 
Berlin <--> London Barcelona Rome Madrid 
Madrid <--> Rome Berlin Athens 
Rome <--> Madrid Paris Berlin Barcelona Athens

和原来的 printEdges 一样

(1,0) w:0.35
(2,1) w:0.37
(3,1) w:0.28
...
(7,1) w:0.34
...
(0,2) w:0.93

内部名称属性！

但我开始使用命名顶点作为向顶点添加“名称”的更用户友好的方式：

template <> struct boost::graph::internal_vertex_name<VertexProps> {
    struct type {
        using result_type = Id;
        Id const& operator()(VertexProps const& vp) const { return vp.id; }
    };
};

这告诉 BGL 你的顶点属性包包含一个“名称”以及如何获取它。如果您还告诉 BGL 如何从 Id 构建新包：

template <> struct boost::graph::internal_vertex_constructor<VertexProps> {
    struct type {
        VertexProps operator()(Id id) const { return {std::move(id)}; }
    };
};

现在你可以再次编写原来的“天真的”代码了：

Id u, v;
double w;
while (ne-- && datafile >> u >> v >> w >> NL)
    add_edge(u, v, {w}, g);

实际上，BGL 在内部保留贴图，并执行完全相同的检查来查看顶点是否已存在：

住在Coliru

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/graph_utility.hpp>
#include <fstream>
#include <iostream>

template <typename Graph, typename WeightMap> //
void printEdges(Graph const& g, WeightMap w) {
    for (auto e : make_iterator_range(edges(g)))
        std::cout << e << " w:" << w[e] << "\n";
}

struct NL_t {
    friend std::istream& operator>>(std::istream& is, NL_t) { return is.ignore(std::numeric_limits<std::streamsize>::max(), '\n'); }
} inline constexpr NL;

using Id = std::string;
struct VertexProps {
    Id id;
};

template <> struct boost::graph::internal_vertex_name<VertexProps> {
    struct type {
        using result_type = Id;
        Id const& operator()(VertexProps const& vp) const { return vp.id; }
    };
};

struct EdgeProps {
    double weight;
};

using Graph  = boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS, VertexProps, EdgeProps>;
using Vertex = boost::graph_traits<Graph>::vertex_descriptor;

Graph read_ewg(std::string fname) {
    std::ifstream datafile;
    datafile.exceptions(std::ios::failbit);
    datafile.open(fname);

    size_t nv = 0, ne = 0;
    datafile >> nv >> NL >> ne >> NL;

    Graph g;

    Id u, v;
    double w;

    while (ne-- && datafile >> u >> v >> w >> NL)
        add_edge(u, v, {w}, g);

    assert(nv == num_vertices(g));
    return g;
}

int main() {
    auto g = read_ewg("tiny-ewg.txt");
    auto weight_map = get(&EdgeProps::weight, g);
    print_graph(g, get(&VertexProps::id, g));
    printEdges(g, weight_map);
}

打印预期的内容

Athens <--> Barcelona Rome Madrid Paris Amsterdam 
Barcelona <--> Athens Amsterdam London Paris Berlin Rome 
Amsterdam <--> Barcelona Paris Athens 
London <--> Barcelona Berlin 
Paris <--> Barcelona Amsterdam Rome Athens 
Berlin <--> London Barcelona Rome Madrid 
Madrid <--> Rome Berlin Athens 
Rome <--> Madrid Paris Berlin Barcelona Athens 
(1,0) w:0.35
(2,1) w:0.37
(3,1) w:0.28
(4,1) w:0.16
(5,3) w:0.32
(4,2) w:0.38
(7,6) w:0.17
(5,1) w:0.19
(4,7) w:0.26
(5,7) w:0.36
(5,6) w:0.29
(7,1) w:0.34
(0,7) w:0.4
(6,0) w:0.52
(0,4) w:0.58
(0,2) w:0.93

¹ 当然，假设您删除/静音了调试断言 

assert(nv == num_vertices(g));

² 这立即回答了“为什么第一个元素的vertex_descriptor添加了8而不是0”

最新问题
© www.soinside.com 2019 - 2024. All rights reserved.