我正在尝试从专有图形库迁移到开源的。
编辑:因为很少有人似乎知道Boost Graph的实际工作原理,所以如果您可以使用LEMON Graph Library提供解决方案,那也很好。
目前,我的顶点类型为Graph_Vertex*
,并且可以具有关联的void*
指针来存储相关信息。对于Graph_Edge*
类型的边缘,使用类似的逻辑。我使用void*
指针存储自己的结构Node_State
,就像这样
struct Node_State {
std::string name;
int id;
// other stuff
};
从我对BGL的了解到现在,我可以使用
adjacency_list
结构和bundled properties指向我的Node_State
来创建图形。然后,我将使用整数顶点索引,而不是使用顶点指针。我一直在看tutorial和一些questions here,这似乎是可能的。我在想类似的东西
typedef adjacency_list < listS, vecS, bidirectionalS, Node_State> gr;
我会不时移除顶点上的所有边缘。不太频繁,我也可以删除节点。这就是为什么我会选择
listS, vecS
的原因。我想轻松地为无向边创建此结构的第二个版本。我不确定
bidirectionalS
是否适合我的情况。在这方面,您的意见表示赞赏。不过还有另一个问题。现在,我可以使用外部映射来通过其名称或使用唯一的整数 id 查找每个顶点。
std::map<int, Graph_Vertex*> nodes_by_id;
std::map<std::string, Graph_Vertex*> nodes_by_name();
如果删除顶点,则只需要删除 map 中的相应条目即可,并且一切正常。
据我了解,使用BGL并不是那么容易实现,因为删除顶点会触发ID较高的所有顶点的重编号,并且还可能导致内部结构的重新分配。因此,再见ID和再见指针。
主要问题。是否有可能创建一个
map<name, node>
或map<index, node>
,使其能够以最小的调整(例如,仅删除无效密钥)在节点删除中生存下来?如果不是,将节点映射到某个唯一标识符的最佳方法是什么?一个选项可以使用internal properties。教程example在这里。
struct vertex_index_t { };
struct edge_index_t { };
struct vertex_name_t { };
struct edge_name_t { };
并保留一些外部结构
std::map<vertex_index_t, Graph_Vertex*> nodes_by_id;
std::map<vertex_name_t, Graph_Vertex*> nodes_by_name;
std::map<edge_index_t, Graph_Edge*> edges_by_id;
std::map<edge_name_t, Graph_Edge*> edges_by_name;
这将与我现在所拥有的更加相似,并且对当前代码的更改更少。
我还不太了解顶点移除如何影响
vertex_index_t
,以及如何分配vertex_name_t
。但是,如果可行,可以使用edge_index_t
和edge_name_t
将类似的逻辑应用于边缘。包起来。我需要一段代码来说明如何:
具有以下重要条件:
如果我能做到这样,我会很高兴
Vertex* vertex0 = Graph.get_vertex_by_name("v0");
Vertex_Data* v0_data = vertex0.get_data();
Edge* edge4 = Graph.get_edge_by_id(4);
Edge_Data* e4_data = edge4.get_data();
这似乎是很多问题,但实际上只是我启动和运行该库所需的基础。什么都做不到,对于我需要做的事情完全没有用。
请击中所有要点。
将此视为教程,我希望给予赏金也会对其他人有所帮助。
最佳答案
实际上,我认为您将使用顶点描述符。对于vecS容器选择,这是必不可少的,是
严格来说,并非总是如此。对于vecS
来说,是,但对于例如listS
(列表具有稳定的迭代器)。
总而言之,我建议将
listS
视为容器选择,并删除vertex_descriptor
是整数类型(它将变得不透明)的假设。作为迭代器稳定性的返回,您将需要为某些算法提供顶点索引映射。