带有可移动节点,可访问属性和可靠ID的C++图

Question

我正在尝试从专有图库迁移到开源图库.

编辑:因为很少有人知道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结构和捆绑属性创建一个图表指向我的Node_State.然后,我将使用整数顶点索引,而不是使用顶点指针.

我一直在寻找的教程和一些问题 在这里,这似乎是可能的.我在想类似的东西

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();

如果我删除一个顶点,我只需要删除地图中相应的条目,并且事情继续有效.

根据我的理解,使用BGL实现这一点并不容易,因为删除顶点会触发使用更高ID 重新编号所有顶点,并且还可能导致内部结构的重新分配.再见ids和再见指针.

主要问题.是否有可能通过最少的调整创建一个map<name, node>或者map<index, node>能够在节点删除后继续存在(例如只删除无效密钥)？如果没有,那么将节点映射到某些唯一标识符的最佳方法是什么？

一个选项可能是使用内部属性.这里的教程示例.

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太.

包起来.我需要一段代码来展示如何:

• 添加顶点(带属性)
• 添加弧(带属性)
• 删除顶点
• 删除弧

有了这些重要的要求:

• 能够通过id(int或string)索引顶点,以便检索它们并访问它们的属性
• 如果删除顶点,则不得更改ID
• 索引和属性的添加不应该使"查找连接组件"和"Dijkstra搜索"等运行算法更加困难

如果能达到类似的目标,我会很高兴的

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();

这可能看起来像很多问题,但实际上只是我需要这个库启动和运行的基础.什么都没有,对我需要做的事情完全没用.

请点击所有要点.

把它想象成一个教程,我希望给予赏金也能帮助其他人.

Answer 1

然后,我将使用整数顶点索引,而不是使用顶点指针.

实际上,我认为你会使用顶点描述符.在vecS容器选择的情况下,哪个是不可或缺的,是的

根据我的理解,使用BGL实现这一点并不容易,因为删除顶点会触发使用更高ID重新编号所有顶点,并且还可能导致内部结构的重新分配.

严格来说,情况并非总是如此.它是与本案vecS有关,而与如listS(名单有稳定的迭代器).

• 迭代器失效规则

总而言之,我建议listS将容器选择看作vertex_descriptor是一个整体类型的假设(它会变得不透明).

作为迭代器稳定性的回报,您需要为某些算法提供顶点索引映射.