BOOST :: ADGACENCY_LIST＆lt;＆gt;＆gt;和boost ::列表

Question

列表选择STD :: LIST

在示例我正在尝试适应。

在示例中，我看不到边缘和顶点类型的传递以提高:: adjacency_list＆lt;＆gt;。 毫不奇怪，使用开头对构造图形在边缘容器中构建图并不对我进行编译。

如何告诉图表库有关使用的边缘和顶点的类型？

Answer 1

我使用普通 std::size_t 作为顶点和 std::pair创建了该图的副本对于边缘。

我不清楚为什么我必须这样做，因为图形库是一个模板库。

Answer 2

问。在示例中我没有看到边和顶点类型被传递给 boost::adjacency_list<> 的任何地方。

您可以使用模板参数选择图形的所有属性。

前两个选择如何存储边和顶点。对于邻接列表，邻接列表是给定的，但您可以选择边容器选择器（它存储每个源顶点的邻接（出边））和实际的顶点容器选择器（其中存储顶点本身）。

其他模板参数包括顶点/边和图属性。因此，当容器选择器选择如何存储图形实体时，属性描述应该存储什么。

如何存储所有内容最终都是实现细节。

问并且毫不奇怪，使用开始-结束对将图形构建到边缘容器中不会对我进行编译。

我们对此无话可说，因为我们不知道“边缘容器”是什么意思。您是否已经拥有其他格式的图表？

构建图表不需要构造函数参数。例如：

#include <boost/graph/adjacency_list.hpp>
using G = boost::adjacency_list<>;

int main() {
    G g(10);
}

是创建具有 10 个未连接顶点的图的最简单的程序。也可以打印它： Live

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/graph_utility.hpp>
using G = boost::adjacency_list<>;

int main() {
    G g(10);
    print_graph(g);
}

输出显示 10 个没有邻接的顶点：

0 --> 
1 --> 
2 --> 
3 --> 
4 --> 
5 --> 
6 --> 
7 --> 
8 --> 
9 --> 

如何告诉图形库想要使用的边和顶点的类型？

让我从“使用”开始，然后稍微修改类型：

相反，您可以在构造后添加边/顶点： 实时

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

using G = boost::adjacency_list<>;
using V = G::vertex_descriptor;
using E = G::edge_descriptor;

int main() {
    G g;

    V v1 = add_vertex(g);
    V v2 = add_vertex(g);
    E e1 = add_edge(v1, v2, g).first;
    // or:
    auto [ed, inserted] = add_edge(v1, v2, g);

    std::cout << "Second insertion happened: " << std::boolalpha << inserted << "\n";

    print_graph(g);
}

输出：

Second insertion happened: true
0 --> 1 1 
1 --> 

现在，让我们立即展示setS作为边缘存储的效果：

using G = boost::adjacency_list<boost::setS>;

输出变成 - 因为 setS 不允许重复的出边：

Second insertion happened: false
0 --> 1 
1 --> 

现在，让我们还尝试不同的顶点容器选择器？

using G = boost::adjacency_list<boost::setS, boost::listS>;

呃，现在打印图表时遇到问题，因为，正如您可能已经在 链接文档：

如果图的 VertexList 是 vecS，则图具有通过 vertex_index_t 属性的属性映射访问的内置顶点索引。索引落在 [0, num_vertices(g)) 范围内并且是连续的。当移除顶点时，索引会被调整，以便它们保留这些属性。使用这些索引访问外部属性存储时必须小心。顶点索引的属性映射是可读属性映射的模型。

如果使用listS，则不存在隐式顶点索引。当然，我们可以添加一个索引，但让我们向顶点添加一个名称属性。

有很多方法可以添加属性，但让我向您展示更通用/友好的版本：捆绑属性：

struct VertexProps {
    std::string name;
};

using G = boost::adjacency_list<boost::setS, boost::listS, boost::undirectedS, VertexProps>;

现在，我们需要做的就是告诉 print_graph 使用 name 属性从束而不是顶点索引（自 listS 起不可用于打印）：

print_graph(g, get(&VertexProps::name, g));

当然，当您实际给出顶点名称时，它会变得更好：

V v1 = add_vertex(VertexProps{"v1"}, g);
V v2 = add_vertex(VertexProps{"v2"}, g);

但是当然，名称可以更改：

g[v2].name += "(changed)";

请参阅全部一起：实时

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

struct VertexProps {
    std::string name;
};

using G = boost::adjacency_list<boost::setS, boost::listS, boost::undirectedS, VertexProps>;
using V = G::vertex_descriptor;
using E = G::edge_descriptor;

int main() {
    G g;

    V v1 = add_vertex(VertexProps{"v1"}, g);
    V v2 = add_vertex(VertexProps{"v2"}, g);
    E e1 = add_edge(v1, v2, g).first;
    // or:
    auto [ed, inserted] = add_edge(v1, v2, g);

    g[v2].name += "(changed)";
    std::cout << "Second insertion happened: " << std::boolalpha << inserted << "\n";

    print_graph(g, get(&VertexProps::name, g));
}

打印

Second insertion happened: false
v1 <--> v2(changed) 
v2(changed) <--> v1 

---

1 您可能不需要复制任何东西，只需调整/使用现有图表即可）