具有可移动节点、可访问属性和可靠 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 创建一个图表结构与bundled properties指向我的Node_State .然后，我不使用顶点指针，而是使用整数顶点索引。

我一直在查看 tutorial还有一些questions here ，这似乎是可能的。我在想类似的事情

typedef adjacency_list < listS, vecS, bidirectionalS, Node_State> gr;

我会时不时地移除顶点的所有边。很少见，我也可能会删除一个节点。这就是为什么我会选择 listS, vecS .

我想让为无向边创建此结构的第二个版本变得容易。我不确定 bidirectionalS是我的情况的最佳选择。在这方面感谢您的意见。

还有一个问题。现在，我可以使用外部 ma​​p 通过其 name 或使用唯一整数 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也是。

总结一下。我需要一段工作代码来展示如何:

• 添加顶点(具有属性)
• 添加弧线(具有属性)
• 删除顶点
• 删除圆弧

有了这些重要的先决条件:

• 能够通过 id(整数或字符串)索引顶点，以便轻松检索它们并访问它们的属性
• 如果删除顶点，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

Then, instead of using vertex pointers, I would use integer vertex indices.

事实上，我认为您会使用顶点描述符。在 vecS 容器选择的情况下，哪个是不可或缺的，是的

From what I understand, this is not so easy to achieve with BGL, because deleting a vertex triggers the renumbering of all the vertices with a higher ID, and might also cause a reallocation of the internal structures.

严格来说，情况并非总是如此。 是 vecS 的情况，但不是例如listS(列表具有稳定的迭代器)。

• Iterator invalidation rules

总而言之，我建议将 listS 视为容器选择，并放弃 vertex_descriptor 是整数类型(它将变得不透明)的假设。

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