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

Question

Я пытаюсь создать древовидный график с использованием 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 для их хранения, я не уверен, могу ли это сделать.

Answer 1

Теоретически, вы могли бы иметь что-то вроде этого:

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, и она будет поддерживать незавершенные типы. Тем не менее, он до сих пор добр на стадии бета (следуйте here или here), а последние версии Boost.Container, похоже, сломали что-то, что мне еще нужно выяснить. Кстати, у меня также есть несколько структур данных дерева BGL, а также новые концепции и черты BGL для деревьев (поскольку вы, похоже, внедряете своеобразное дерево).

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

Наконец, чтобы решить эту ситуацию, вы должны использовать технику стирания. Простым вне-полки способ сделать это состоит в использовании 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), но это детали реализации, на которые вы не должны и не можете положиться.