我正在尝试从专有图形库迁移到开源图形库。
编辑：由于似乎很少有人知道 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但是，如果这可行，那么类似的逻辑也可以使用and应用于边缘edge_name_t。
包起来。我需要一段工作代码来展示如何：
- 添加顶点（带有属性）
- 添加弧（带属性）
- 删除顶点
- 移除弧线
具备这些重要条件：
- 能够按 id（int 或 string）索引顶点，以便轻松检索它们并访问它们的属性
- 如果顶点被移除，ids 不能改变
- 索引和属性的添加不应使“查找连接的组件”和“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();
这可能看起来像很多问题，但实际上只是启动和运行这个库所需的基础。少一点，对我需要做的事情完全没用。
请点击所有要点。
将此视为教程，我希望给予赏金也能帮助其他人。