Производительность vertex_descriptor библиотеки Boost Graph

У меня есть сомнения относительно дескриптора vertex_descriptor, используемого для доступа к вершине графа. В своей предыдущей реализации я использовал указатели на вершины как способ прямого доступа к вершине. Я мог бы реализовать карту, если бы я хотел получить доступ к IDVertex целым числом или чем-то еще.

Но в BGL я не понимаю, почему vertex_descriptor является целым числом? Я знаю, что это имеет смысл с вектором. Но если я хочу использовать широкий набор вершин, например 10^6, и иметь возможность удалить любую вершину набора, я использую карту. Кроме того, в моей игре я хочу иметь возможность ссылаться на каждый узел с помощью целого числа указателей, что более логично?

Как работает BGL, чтобы связать целое число с вершиной в контейнере no_random_access_container, таком как std::set ? Метод доступа всегда log(n) no ? Можете ли вы объяснить мне, есть ли механизм, чтобы держать дескриптор непосредственно на вершине, не сохраняя vertex_descirptor ?

Извините за мой плохой английский ;)


c++ vertex boost-graph
person Community    schedule 30.01.2014    source источник

Ответы (1)


arrow_upward
2
arrow_downward

Когда политика контейнера вершин определена как vecS, setS или listS, дескриптор вершины становится итератором ["value_type", на который указывает] в соответствующем контейнере. Тип vertex_iterator обычно является типом итератора в этом контейнере.

Это означает, что доступ к вершине всегда равен O(1). Добавление и удаление новой вершины будет стоить O(logN) в случае setS и O(1) в случае listS или vecS. Удаление вершины сделает недействительными некоторые другие вершины в случае vecS, но не listS или setS. Подробнее см. в разделе Стабильность и недействительность итераторов и дескрипторов на странице страница графика смежности.

По другому вашему вопросу. Если вы хотите сохранить (указатель) на данные непосредственно в вершине, вы добавляете его как свойство вершины.

Довольно часто вам нужно какое-то однозначное сопоставление между вашими данными и вершинами графа. Может быть удобно сохранить прямую карту как, скажем, boost::unordered_set и обратную карту как свойство для каждой вершины.

person Michael Simbirsky    schedule 04.02.2014
comment
Итак, насколько я понял, vertex_descirptor — это size_t, когда vecS, или итератор в VertexListS, когда listS или setS. Вот почему мы можем получить доступ непосредственно к нему. Но у меня есть вопрос, vertex_descriptor и vertex_iterator одинаковы, поэтому, когда мы добавляем или удаляем вершину в listS или setS, они не становятся недействительными. Я прав ? Конечно, если это не тот, который мы удаляем - person ; 05.02.2014
comment
Отредактировал ответ, чтобы ответить на ваш вопрос. - person Michael Simbirsky; 05.02.2014
comment
Спасибо большое! Что касается ребер, когда граф направлен, они сохраняются в списках внешних ребер, а когда граф двунаправленный или ненаправленный, они сохраняются в EdgeList, а элементы списков внешних ребер повторяются на нем? - person ; 06.02.2014
comment
Это немного сложнее, так как adjacency_list<...> хранит как входящие, так и исходящие ребра для каждой вершины, по крайней мере, для ориентированного графа. Какие контейнеры использовать, определяется соответствующим параметром шаблона и может быть vecS, listS или setS с определенными компромиссами. - person Michael Simbirsky; 06.02.2014