BGL: Как эффективно хранить edge_descriptors и vertex_descriptors? - PullRequest
Новая
       22

BGL: Как эффективно хранить edge_descriptors и vertex_descriptors?

2 голосов
/ 25 ноября 2010

Итак, после того, как моя проблема круговой зависимости с BGL была решена, я натолкнулся на другое препятствие.

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

class Node {
    int x, int y // position
};
class Edge {
    float length;
};

boost::adjacency_list<boost::listS, boost::listS, boost::directedS, Node, Edge>

Проблема возникает, когда я хочу сохранить ярлыки для определенных узлов и ребер где-нибудь еще в моем коде (например, для улицы с несколькими полосами движения). Мой первый подход состоял в том, чтобы сохранить edge_descriptors и vertex_descriptors там, где они мне нужны. Но мне интересно, насколько большими (в байтах) будут такие дескрипторы. Может быть, есть лучшее решение, например, хранить только часть информации, чтобы получить те же результаты.

Кто-нибудь знает объем памяти, который используется для вектора этого типа: 

std::vector<edge_descriptor> ?

Я уже думал о том, чтобы просто хранить указатели на edge_descriptors, но я не знаю, как и как это будет работать.

/////////////////////////////////////////////// ////////////////////////////////////////////////// ////////////////////////////////////////////////// //////////////////

РЕДАКТИРОВАТЬ: Теперь, когда мой первый вопрос был дан исчерпывающий ответ, мне все еще интересно одно. Я хочу построить какой-то интерфейс для моего графового класса. Этот интерфейс должен отделять детали класса графа от других классов, которые не должны знать детали графа. Таким образом, другие классы должны предпочтительно распознавать узлы и ребра как числа. Итак, я пришел с двумя идеями:

  1. Я использую hash_map std::tr1::unordered_map<int, edge_descriptor>, чтобы иметь возможность переводить числа в дескрипторы, которые снова используются в качестве индексов для моего граф-объекта. Это может быть одним шагом к большому - возможно, вычисление значений хеша займет слишком много времени если есть достаточно узлов и ребер для расчета. Вот почему у меня появилась вторая идея.
  2. Сам граф должен внутренне преобразовать эти числа в ребра и узлы. Я знаю, что внутренние свойства вместе с картами свойств могут быть использованы для реализации моей идеи. Затем вы можете получить доступ к узлу, просто набрав что-то вроде:
    boost::property_map<My_Graph, my_prop>::type index = get(my_prop(), G);

Но есть ли способ объединить такие карты свойств с моими связанными свойствами?

Или у вас есть другая идея, которую я еще не реализовал?

1 Ответ

1 голос
/ 25 ноября 2010

Дескрипторы вершин и ребер имеют очень маленький размер.

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

Поэтому ответ на ваш вопрос заключается в том, что вы можете использовать их в векторах. Это не вызовет проблемы с памятью.

...