BGL: использование связанных свойств для хранения дескриптора вершины другой вершины

Я пытаюсь создать древовидный граф, используя boost::adjacency list и связанные свойства для хранения родителя для каждой вершины, я хочу хранить дескрипторы вершин таким образом, чтобы они не становились недействительными в случае удаления вершины, поэтому я использую boost::listS, код должен выглядеть что-то вроде этого

// custom vertex for tree graphs
struct tree_vertex_info{
    // descriptor of parent vertex
    boost::graph_traits<Tree>::vertex_descriptor parent_in_tree;
};
// the tree graph type
typedef boost::adjacency_list<boost::listS, boost::listS, boost::directedS
        tree_vertex_info, boost::no_property, graph_info> Tree;

Но это не сработает, так как дерево должно быть определено после определения структуры. Есть ли другой способ сделать это со связанными свойствами? Я думал, что могу использовать переменную int вместо типа vertex_descriptor для хранения vertex_descriptors, но, поскольку я использую boost::listS для их хранения, я не уверен, что смогу.


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

Ответы (1)


arrow_upward
2
arrow_downward

Теоретически у вас может быть что-то вроде этого:

struct tree_vertex_info;  // forward-declaration

typedef boost::adjacency_list<
  boost::listS, boost::listS, boost::directedS, 
  tree_vertex_info, boost::no_property, graph_info> Tree;

struct tree_vertex_info {
  boost::graph_traits<Tree>::vertex_descriptor parent_in_tree;
};

Однако для этого потребуется, чтобы шаблон класса boost::adjacency_list поддерживал неполные типы (именно это и есть tree_vertex_info, пока есть только прямое объявление, пока компилятор не достигнет его полного объявления). Насколько я знаю, класс boost::adjacency_list не поддерживает неполные типы (и я знаю эту реализацию совсем немного, и я не думаю, что она будет работать) и, конечно, не гарантируется их поддержка.

На самом деле я работаю над новой версией boost::adjacency_list, которую я называю boost::adjacency_list_BC, потому что она основана на контейнерах Boost.Container и будет поддерживать неполные типы. Тем не менее, он все еще находится на стадии бета-тестирования (следуйте здесь или здесь), а последние версии Boost.Container, похоже, сломал что-то, что мне еще нужно выяснить. Между прочим, у меня также есть ряд структур данных дерева BGL, а также новые концепции и признаки BGL для деревьев (поскольку вы, похоже, реализуете своего рода дерево).

Кроме того, если ваша мотивация для этого действительно то, что у вас есть («родитель-в-дереве»), тогда вы должны использовать boost::bidirectionalS в своем adjacency_list, чтобы иметь возможность перейти от дочерней вершины к ее родителю (это то, что boost::bidirectionalS означает , вы получите двунаправленный график).

Наконец, чтобы решить эту ситуацию, в которой вы оказались, вам придется использовать метод стирания шрифта. Простой готовый способ сделать это — использовать boost::any для стирания типа vertex_descriptor, например:

struct tree_vertex_info{
  // descriptor of parent vertex
  boost::any parent_in_tree;
};

// the tree graph type
typedef boost::adjacency_list<boost::listS, boost::listS, boost::directedS
        tree_vertex_info, boost::no_property, graph_info> Tree;

Просто найдите Boost.Any, чтобы получить инструкции по его использованию. .

Я думал, что могу использовать переменную int вместо типа vertex_descriptor для хранения vertex_descriptors, но, поскольку я использую listS для их хранения, я не уверен, что смогу.

Нет, ты не можешь. Вы не можете зависеть от того, является ли тип vertex_descriptor чем-то конкретным (например, вы не можете предполагать, что это целочисленный тип, не говоря уже о «int»). Я знаю, что vertex_descriptor обычно является либо типом итератора (например, std::list<T>::iterator), либо типом размера (например, std::size_t или std::vector<T>::size_type), но это деталь реализации, на которую вы не должны и не можете полагаться.

person Mikael Persson    schedule 23.09.2014
comment
boost::any похоже решил проблему! Моя первая мысль состояла в том, чтобы использовать двунаправленный граф, но поскольку я пытаюсь реализовать динамический алгоритм для поддержания путей минимальной длины, это не совсем хорошо работает, потому что, когда мне понадобится родитель ребра, мне придется проверить все соседние ребра а затем проверить, какие из них ведут к вершине с наименьшей глубиной, и в этом случае мне пришлось бы хранить глубины. Большое спасибо за помощь! За исключением решения, вы также дали мне подсказку о вещах, в которых я не был уверен! - person LetsPlayYahtzee; 23.09.2014