График C++ со съемными узлами, доступными свойствами и надежными идентификаторами

Я пытаюсь мигрировать с проприетарной графической библиотеки на библиотеку с открытым исходным кодом.

РЕДАКТИРОВАТЬ: поскольку так мало людей, похоже, знают, как на самом деле работает Boost Graph, если вы можете предоставить решение с использованием библиотеки LEMON Graph, это тоже хорошо.

В настоящее время мои вершины имеют тип 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 лучший вариант для моего случая. Ваш вклад приветствуется в этом отношении.

Хотя есть еще одна проблема. Прямо сейчас я могу использовать внешнюю карту для поиска каждой вершины по ее имени или уникальному целочисленному идентификатору.

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

Если я удаляю вершину, мне просто нужно удалить соответствующую запись(и) на карте(ах), и все будет продолжать работать.

Насколько я понимаю, этого не так просто добиться с помощью BGL, потому что удаление вершины вызывает перенумерацию всех вершин с более высоким идентификатором, а также может привести к перераспределению внутренних структур. Итак, прощайте идентификаторы и прощайте указатели.

Основной вопрос. Можно ли создать 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* 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();