升压图形列表或VEC [英] Boost graph list or vec
问题描述
我已经花与升压图图书馆工作好几天。据我了解,在考虑VertexList时,与EdgeList都存储:
I've been spending quite a few days working with the boost graph library. As far as I understand, when considering VertexList and EdgeList storage :
vecS的:
- 在具备索引,它因此可以访问
- 删除顶点时,迭代器失效
清单:
- 在没有指数
- 在不坏迭代器
这是一个有点短,但是这给了点我的问题。我需要这些索引号,我希望能够在以后轻松删除顶点。
It's a bit short but that's to the point for my problem. I need those index number and I want to be able to easily remove vertices later on.
我有一个工作的算法与此图结构:
I have a working algorithm with this graph structure :
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的。
I have a custom structure Intersection_Graph
for my vertices that I need to use. Here I use vecS.
我要使用列表,而不是要能够删除顶点。同时,我希望以后能够使用它Dijkstra算法。
I want to use listS instead to be able to remove vertices. As well, I want to be able to use it later with Dijkstra algorithm.
我有点明白,我需要有的boost :: vertex_index_t
在我的名单,但我真的很困惑,如何做到这一点,让我的自定义结构的同时。
I kind of understand that I need to have boost::vertex_index_t
in my list but I am really confused as to how to do it and keep my custom struct at the same time.
我想类似的规定:
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;
不过,我甚至不能访问我的自定义结构了。此外,索引访问不工作。
But I can't even access my custom struct anymore. Plus, index access don't work.
我真正需要的是,由于算法的索引访问能力我图将取决于返回父节点的索引。我觉得我可以逃脱使用,而不是索引的顶点,但是这将意味着一个重大重写的code,我想知道如果我能避免它。
I really need that index access capability since the algorithm my graph will depend on return the index of the parent node. I feel like I could get away with using a Vertex instead of indexes but it would imply a major re-writing of the code and I want to know if I can avoid it.
所以我的问题是:有没有什么办法让listS的行为在vecS的类似的方式,同时保持列出的优点
So my question is : is there any way to have listS behaving in a vecS like manner while keeping the advantages of listS ?
请,忍耐一下,如果它听起来很愚蠢。我很迷惑的时刻,所以我可能说一些愚蠢的。如果您需要了解更多信息,只问。
Please, bear with me if it sounds stupid. I'm quite confuse at the moment, so I might have say something stupid. If you need more information, just ask.
推荐答案
在内部性能的提法是:
property<tag, type, next_property>
当然,除非你让 Intersection_Graph
的的行为的像一个整体的类型,你不能直接使用它作为的键入的的的vertex_index
属性。这也很可能不是你想要的。
Of course, unless you make Intersection_Graph
behave like an integral type you cannot use it directly as the type of the vertex_index
property. It's also likely not what you wanted.
这看起来更接近:
boost::property<boost::vertex_index_t, int, topologicalmap::Intersection_Graph>
和这将宣布的两个的属性:
- 在内部属性标记
vertex_index_t
(键入INT
) - 捆绑性(类型
Intersection_Graph
)。需要注意的是捆绑的属性通过vertex_bundle_t
标记含蓄地访问。
- an interior property tagged
vertex_index_t
(typeint
) - a bundled property (typed
Intersection_Graph
). Note that bundled properties are implicitly accessible through thevertex_bundle_t
tag.
现在考虑到这一点,一切都应该是一帆风顺:
Now with this in mind, everything should be plain sailing:
<大骨节病> 住在Coliru
#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 << "'";
}
它打印如(随机生成每个运行)
Which prints e.g. (random generated each run)
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'
注:
-
这图知道的事实
的vertex_index
现在并不意味着它得到维持;你必须自己填吧:
the fact that the graph "knows"
vertex_index
now doesn't mean it gets maintained; you have to fill it yourself:
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
)
you don't actually need to have vertex_index
associated with your graph type, because you can pass it in as a named parameter to all relevant algorithms AFAIK. This includes constructing derived property maps that rely on a vertex_index (e.g. make_iterator_property_map
)
这篇关于升压图形列表或VEC的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!