C ++图形与移动节点访问的性能和可靠的ID [英] C++ graph with removable nodes, accessible properties and reliable IDs

问题描述

我想的迁移从专有图形库的到一个开源的。

编辑：既然有那么几个人似乎知道如何提升图形的实际工作，如果你能提供使用柠檬图形库的解决方案，那也没关系。

目前，我的顶点具有类型 Graph_Vertex * ，可以有一个相关的无效* 指针来保存相关信息。类似的逻辑用于相对于边缘，这是类型的 Graph_Edge * 。我用的是无效* 指针来保存我自己的结构 Node_State ，它是这样的。

 结构Node_State {
    性病::字符串名称;
    INT ID;
    // 其他的东西
};
 

这是我所见过的BGL的到现在为止，我可以创建使用的adjacency_list 结构的捆绑性指向我 Node_State 。然后，而不是使用的顶点指针，我会用整数的顶点索引

我一直在看教程和一些问题 这里 ，这似乎可能的。我在考虑类似

 的typedef的adjacency_list＆LT;列表，血管内皮细胞，bidirectionalS，Node_State＆GT;克;
 

我将删除所有边，并从一个顶点不时。非常不经常，我可以删除一个节点了。这就是为什么我会选择列表，血管内皮细胞。

我想可以很容易地创建这种结构的无向边缘的第二个版本。我不知道，如果 bidirectionalS 是我的情况下的最佳选择。您输入AP preciated在这方面。

有另外一个问题，虽然。现在，我可以使用外部的地图由它的名称查找每个顶点或使用一个唯一的整数 ID

 的std ::地图＆LT; INT，Graph_Vertex *＆GT; nodes_by_id;
性病::地图＆LT;的std ::字符串，Graph_Vertex *＆GT; nodes_by_name（）;
 

如果我删除了一个顶点，我只需要删除该地图（S）的相应项（IES），事情继续工作。

据我了解，这并不是那么容易实现与BGL，因为删除一个顶点触发的重编所有具有较高ID顶点，并且还可能导致内部的再分配结构。所以，再见ID和再见指针。

的主要问题的是否有可能创建一个地图＆LT;名称，节点＆GT; 或地图＆LT;指标，节点＆GT ; 可存活节点的清除以最小的调整（如只删除无效键​​）？如果没有，什么是映射到一些独特的标识符生存修改图中的节点的最佳方式？

一个选项可以使用内部属性的。教程<一个href=\"http://www.boost.org/doc/libs/1_57_0/libs/graph/doc/using_adjacency_list.html#sec:custom-vertex-properties\"相对=nofollow> 的例子在这里。

 结构vertex_index_t {};
结构edge_index_t {};结构vertex_name_t {};
结构edge_name_t {};
 

和保持一些外部结构

 的std ::地图＆LT; vertex_index_t，Graph_Vertex *＆GT; nodes_by_id;
性病::地图＆LT; vertex_name_t，Graph_Vertex *＆GT; nodes_by_name;
性病::地图＆LT; edge_index_t，Graph_Edge *＆GT; edges_by_id;
性病::地图＆LT; edge_name_t，Graph_Edge *＆GT; edges_by_name;
 

这会更类似于我现在有，并且需要对当前code较少的变化。

我还没有真正理解如何 vertex_index_t 由顶点消除影响，以及如何 vertex_name_t 可以分配。如果这可以工作，不过，类似的逻辑可应用于使用边缘 edge_index_t 和 edge_name_t 了。

结束语。我需要code呈现出一块工作如何：

• 添加新顶点（带属性）


• 添加弧（带属性）


• 删除顶点


• 删除弧

有了这些重要必要条件：

• 将ID为能够索引顶点（int或字符串），这样很容易对它们进行检索和访问他们的属性


• 如果一个顶点被删除IDS不得更改


• 增加指标和性能的不应该让运行像找到连接组件和算法Dijkstra算法搜索更加困难

我会很高兴，如果我能做到像

 顶点* vertex0 = Graph.get_vertex_by_name（V0）;
Vertex_Data * v0_data = vertex0.get_data（）;边缘* edge4 = Graph.get_edge_by_id（4）;
Edge_Data * e4_data = edge4.get_data（）;
 

这可能看起来是一个很大的问题，但我需要得到这个库的建立和运行其实只是基础。如果不这样做，它是什么，我需要做的完全无用的。

请，打所有的要点。

认为这是一个教程，我的希望是，给予赏金将帮助其他人也是如此。

解决方案

  

然后，而不是使用顶点三分球，我会用整数顶点索引。

事实上，我认为你会使用顶点描述。其中在血管内皮细胞容器的选择的情况下，将是不可或缺的，是的。

  

据我了解，这并不是那么容易实现与BGL，因为删除一个顶点触发所有具有较高ID的顶点重新编号，同时还可能导致内部结构的重新分配。

严格地说这并非总是如此。它的是与血管内皮细胞，而不是与本案例如列出（列表中有稳定的迭代器）。

• 迭代器失效规则

所有的一切，我建议在看列出作为容器的选择和拖放假设 vertex_descriptor的是一个整体式（它会变得不透明）。

在回报稳定的迭代器，你将需要提供顶点索引映射到特定的算法。

I'm trying to migrate from a proprietary graph library to an Open Source one.

EDIT: since so few people seem to know how Boost Graph actually works, if you can provide a solution using the LEMON Graph Library, that's fine too.

Currently, my vertices have type Graph_Vertex* and can have an associated void* pointer to store related information. A similar logic is used with respect to edges, which are of type Graph_Edge*. I use the void* pointer to store my own structure Node_State, which is something like this

struct Node_State {
    std::string name;
    int id;
    // other stuff
};

From what I've seen of the BGL up to now, I could create a graph using an adjacency_list structure and bundled properties to point to my Node_State. Then, instead of using vertex pointers, I would use integer vertex indices.

I've been looking at the tutorial and some questions here, and this seems possible. I'm thinking about something like

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

I'll remove all the edges to and from a vertex from time to time. Very less frequently, I may remove a node too. That's why I would choose listS, vecS.

I would like to make it easy to create a second version of this structure for undirected edges. I am not sure if bidirectionalS is the best option for my case. Your input is appreciated in this regard.

There's another problem though. Right now, I can use an external map to find each vertex by its name or using a unique integer id.

std::map<int, Graph_Vertex*> nodes_by_id;
std::map<std::string, Graph_Vertex*> nodes_by_name();

If I delete a vertex, I just need to remove the corresponding entry(ies) in the map(s), and things keep working.

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. So goodbye ids and goodbye pointers.

Main question. Is it possible to create a map<name, node> or map<index, node> that can survive node removals with minimal adjustments (e.g. just removing the invalid keys)? If not, what's the best way to map nodes to some unique identifier that survives modifications to the graph?

An option could be using the internal properties. Tutorial example here.

struct vertex_index_t { };
struct edge_index_t { };

struct vertex_name_t { };
struct edge_name_t { };

And keeping some external structures

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;

This would be much more similar to what I have now, and require less changes to the current code.

I haven't really understood how vertex_index_t is affected by vertex removal, and how vertex_name_t can be assigned. If this can work, though, a similar logic could be applied to edges using edge_index_t and edge_name_t too.

Wrap up. I need a working piece of code showing how to:

• add vertices (with properties)
• add arcs (with properties)
• remove vertices
• remove arcs

With these important requisites:

• being able to index vertices by id (int or string) so that it's easy to retrieve them and access their properties
• ids must not change if a vertex is removed
• the addition of indices and properties should not make running algorithms like "find connected components" and "Dijkstra search" more difficult

I would be happy if I could achieve something like

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

This may seem like a lot of questions, but really just the basis of what I need to get this library up and running. Anything less and it's completely useless for what I need to do.

Please, hit all the bullet points.

Think of this as a tutorial, my hope is that giving a bounty will help other people as well.

解决方案

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

In fact, I think you would use vertex descriptors. Which in the case of vecS container selections would be integral, yes

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.

Strictly speaking this is not always the case. It is the case with vecS, but not with e.g. listS (lists have stable iterators).

• Iterator invalidation rules

All in all, I suggest looking at listS as the container selection and drop the assumption that vertex_descriptor be an integral type (it will become opaque).

In return for iterator stability, you will need to provide vertex index maps to certain algorithms.

这篇关于C ++图形与移动节点访问的性能和可靠的ID的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！