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

Question

Я пытаюсь перейти с проприетарной библиотеки графов на Open Source.

РЕДАКТИРОВАТЬ: так как очень немногие люди, кажется, знают, как на самом деле работает 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 это лучший вариант для моего случая. Ваш вклад приветствуется в этом отношении.

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

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

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

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

Главный вопрос Можно ли создать 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), чтобы их было легко найти и получить доступ к их свойствам
• Идентификаторы не должны меняться, если вершина удалена
• добавление индексов и свойств не должно усложнять выполнение таких алгоритмов, как "поиск подключенных компонентов" и "поиск Дейкстры".

Я был бы счастлив, если бы я мог достичь чего-то вроде

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 быть целочисленным типом (он станет непрозрачным).

В обмен на стабильность итератора вам необходимо предоставить карты вершинных индексов для определенных алгоритмов.