提升图列表或 vec
Boost graph list or vec
我已经花了好几天时间使用 boost 图形库。据我了解，在考虑 VertexList 和 EdgeList 存储时：
vecS :
- 拥有一个索引，所以可以用它访问
- 删除顶点时，迭代器失效
名单：
- 无索引
- 不会使迭代器失效
它有点短，但这是我的问题的关键。我需要那些索引号，我希望以后能够轻松删除顶点。
我有一个具有这种图形结构的工作算法：
typedef boost::adjacency_list<
boost::vecS, boost::vecS, boost::undirectedS,
topologicalmap::Intersection_Graph ,
boost::edge_weight_t,
boost::no_property > Graph_boost;
我有一个自定义结构 Intersection_Graph 用于我需要使用的顶点。这里我使用vecS。
我想改用 listS 来移除顶点。同样，我希望以后能够将它与 Dijkstra 算法一起使用。
我有点明白我需要在我的列表中包含 boost::vertex_index_t 但我真的很困惑如何做到这一点并同时保留我的自定义结构。
我尝试了一些类似的方法：
typedef boost::adjacency_list<
boost::listS, boost::listS, boost::undirectedS,
boost::property<boost::vertex_index_t, topologicalmap::Intersection_Graph>,
boost::edge_weight_t,
boost::no_property > Graph_boost;
但我什至无法再访问我的自定义结构。另外，索引访问不起作用。
我真的需要索引访问功能，因为我的图的算法将取决于 return 父节点的索引。我觉得我可以使用 Vertex 而不是索引，但这意味着要对代码进行重大重写，我想知道我是否可以避免它。
所以我的问题是：有没有办法让 listS 以类似 vecS 的方式运行，同时保持 listS 的优势？
如果这听起来很愚蠢，请多多包涵。我现在很困惑，所以我可能会说一些愚蠢的话。如果您需要更多信息，请询问。
内部属性公式为：
property<tag, type, next_property>
当然，除非你让 Intersection_Graph 表现得像一个整数类型，否则你不能直接将它用作 type vertex_index 属性。它也可能不是您想要的。
这看起来更近了：
boost::property<boost::vertex_index_t, int, topologicalmap::Intersection_Graph>
它会声明两个属性：
- 内部 属性 标记为
vertex_index_t（类型 int）
- 捆绑 属性（键入
Intersection_Graph）。请注意，捆绑属性可通过 vertex_bundle_t 标记隐式访问。
现在考虑到这一点，一切都应该一帆风顺：
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/random.hpp>
#include <boost/graph/graph_utility.hpp>
#include <boost/graph/iteration_macros.hpp>
#include <random>
#include <iostream>
using namespace boost;
namespace topologicalmap {
struct Intersection_Graph {
std::string bundled;
};
}
typedef boost::adjacency_list<
boost::listS, boost::listS, boost::undirectedS,
boost::property<boost::vertex_index_t, int, topologicalmap::Intersection_Graph>,
boost::edge_weight_t,
boost::no_property > Graph_boost;
int main() {
std::mt19937 prng { std::random_device {} () };
Graph_boost g;
generate_random_graph(g, 10, 20, prng);
// assign indices
int i = 0;
BGL_FORALL_VERTICES(v, g, Graph_boost) {
get(vertex_index, g)[v] = i;
g[v].bundled = "id:" + std::to_string(i);
i++;
}
// print the graph using the `bundled` property as a label:
print_graph(g, get(&topologicalmap::Intersection_Graph::bundled, g));
// do some index accesses:
for (int i : {1,7})
std::cout << "\nVertex at index #" << i << " has a bundled property of '" << g[vertex(i,g)].bundled << "'";
}
打印例如（每个随机生成运行）
id:0 <--> id:8 id:8 id:7 id:6 id:1
id:1 <--> id:3 id:4 id:4 id:3 id:0 id:2
id:2 <--> id:7 id:1
id:3 <--> id:1 id:7 id:1 id:9 id:4
id:4 <--> id:1 id:1 id:5 id:6 id:3
id:5 <--> id:4 id:9
id:6 <--> id:0 id:9 id:4 id:8
id:7 <--> id:3 id:0 id:2 id:9
id:8 <--> id:0 id:0 id:6
id:9 <--> id:7 id:6 id:3 id:5
Vertex at index #1 has a bundled property of 'id:1'
Vertex at index #7 has a bundled property of 'id:7'
备注：
图表 "knows" vertex_index 现在并不意味着它得到维护；你必须自己填写：
int i = 0;
BGL_FORALL_VERTICES(v, g, Graph_boost) get(vertex_index, g)[v] = i++;
您实际上不需要 vertex_index 与您的图形类型相关联，因为您可以将其作为命名参数传递给所有相关算法 AFAIK。这包括构建依赖于 vertex_index（例如 make_iterator_property_map）
- 我相信也可以使用图形特征关联顶点索引（但我过去没有这样做过）。如果你，这似乎是一个不错的方法。想将索引存储在
Intersection_Graph 结构的成员中。
- 就像我在 my comment 中所说的，如果您存储
vertex_descriptor 而不是整数索引，您可能不需要任何这些。
我已经花了好几天时间使用 boost 图形库。据我了解，在考虑 VertexList 和 EdgeList 存储时：
vecS :
- 拥有一个索引，所以可以用它访问
- 删除顶点时，迭代器失效
名单：
- 无索引
- 不会使迭代器失效
它有点短，但这是我的问题的关键。我需要那些索引号，我希望以后能够轻松删除顶点。
我有一个具有这种图形结构的工作算法：
typedef boost::adjacency_list<
boost::vecS, boost::vecS, boost::undirectedS,
topologicalmap::Intersection_Graph ,
boost::edge_weight_t,
boost::no_property > Graph_boost;
我有一个自定义结构 Intersection_Graph 用于我需要使用的顶点。这里我使用vecS。
我想改用 listS 来移除顶点。同样，我希望以后能够将它与 Dijkstra 算法一起使用。
我有点明白我需要在我的列表中包含 boost::vertex_index_t 但我真的很困惑如何做到这一点并同时保留我的自定义结构。
我尝试了一些类似的方法：
typedef boost::adjacency_list<
boost::listS, boost::listS, boost::undirectedS,
boost::property<boost::vertex_index_t, topologicalmap::Intersection_Graph>,
boost::edge_weight_t,
boost::no_property > Graph_boost;
但我什至无法再访问我的自定义结构。另外，索引访问不起作用。
我真的需要索引访问功能，因为我的图的算法将取决于 return 父节点的索引。我觉得我可以使用 Vertex 而不是索引，但这意味着要对代码进行重大重写，我想知道我是否可以避免它。
所以我的问题是：有没有办法让 listS 以类似 vecS 的方式运行，同时保持 listS 的优势？
如果这听起来很愚蠢，请多多包涵。我现在很困惑，所以我可能会说一些愚蠢的话。如果您需要更多信息，请询问。
内部属性公式为：
property<tag, type, next_property>
当然，除非你让 Intersection_Graph 表现得像一个整数类型，否则你不能直接将它用作 type vertex_index 属性。它也可能不是您想要的。
这看起来更近了：
boost::property<boost::vertex_index_t, int, topologicalmap::Intersection_Graph>
它会声明两个属性：
- 内部 属性 标记为
vertex_index_t（类型int） - 捆绑 属性（键入
Intersection_Graph）。请注意，捆绑属性可通过vertex_bundle_t标记隐式访问。
现在考虑到这一点，一切都应该一帆风顺：
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/random.hpp>
#include <boost/graph/graph_utility.hpp>
#include <boost/graph/iteration_macros.hpp>
#include <random>
#include <iostream>
using namespace boost;
namespace topologicalmap {
struct Intersection_Graph {
std::string bundled;
};
}
typedef boost::adjacency_list<
boost::listS, boost::listS, boost::undirectedS,
boost::property<boost::vertex_index_t, int, topologicalmap::Intersection_Graph>,
boost::edge_weight_t,
boost::no_property > Graph_boost;
int main() {
std::mt19937 prng { std::random_device {} () };
Graph_boost g;
generate_random_graph(g, 10, 20, prng);
// assign indices
int i = 0;
BGL_FORALL_VERTICES(v, g, Graph_boost) {
get(vertex_index, g)[v] = i;
g[v].bundled = "id:" + std::to_string(i);
i++;
}
// print the graph using the `bundled` property as a label:
print_graph(g, get(&topologicalmap::Intersection_Graph::bundled, g));
// do some index accesses:
for (int i : {1,7})
std::cout << "\nVertex at index #" << i << " has a bundled property of '" << g[vertex(i,g)].bundled << "'";
}
打印例如（每个随机生成运行）
id:0 <--> id:8 id:8 id:7 id:6 id:1
id:1 <--> id:3 id:4 id:4 id:3 id:0 id:2
id:2 <--> id:7 id:1
id:3 <--> id:1 id:7 id:1 id:9 id:4
id:4 <--> id:1 id:1 id:5 id:6 id:3
id:5 <--> id:4 id:9
id:6 <--> id:0 id:9 id:4 id:8
id:7 <--> id:3 id:0 id:2 id:9
id:8 <--> id:0 id:0 id:6
id:9 <--> id:7 id:6 id:3 id:5
Vertex at index #1 has a bundled property of 'id:1'
Vertex at index #7 has a bundled property of 'id:7'
备注：
图表 "knows"
vertex_index现在并不意味着它得到维护；你必须自己填写：int i = 0; BGL_FORALL_VERTICES(v, g, Graph_boost) get(vertex_index, g)[v] = i++;您实际上不需要
vertex_index与您的图形类型相关联，因为您可以将其作为命名参数传递给所有相关算法 AFAIK。这包括构建依赖于 vertex_index（例如make_iterator_property_map） 的派生 属性 地图
- 我相信也可以使用图形特征关联顶点索引（但我过去没有这样做过）。如果你，这似乎是一个不错的方法。想将索引存储在
Intersection_Graph结构的成员中。 - 就像我在 my comment 中所说的，如果您存储
vertex_descriptor而不是整数索引，您可能不需要任何这些。