Boost Graph Library не может хранить ссылки на другие вершины? - PullRequest
Новая
       32

Boost Graph Library не может хранить ссылки на другие вершины?

1 голос
/ 02 мая 2019

Я использую BGL для построения графа, содержащего связанные вершины, где один тип вершины хранит ссылку на другой тип вершины.Оба типа обрабатываются с использованием std :: variable: 

struct simple_node_t {
    size_t enabled;
};

struct complex_node_t {
    bool foo1;
    size_t foo2;
    simple_node_t& control;
};

using vertex_t = std::variant<simple_node_t, complex_node_t>;

using netListGraph_t = boost::adjacency_list<
    boost::vecS,
    boost::vecS,
    boost::undirectedS,
    vertex_t>;

Вершины типа complex_node_t создаются и хранятся следующим образом: 

// Create node
complex_node_t cpx = {
    true,
    0xDEADBEEF,
    std::get<simple_node_t>(mGraph[desc_to_simple_vertex])
};

// Add complex_node_t to graph
vertex_t vtx(cpx);
auto vertex = boost::add_vertex(vtx, mGraph);

Теперь проблема: 

auto pVal = std::get_if<complex_node_t>(&mGraph[vertex]);

assert(pVal->foo1 == true); //OK
assert(pVal->foo2 == 0xDEADBEEF); //OK

Но получить доступ к ссылке не удается (недопустимый объект)! 

**pVal->control.enabled -> GARBAGE**

Хранение данных по значению работает - но сохранение по ссылке - нет.

Что я делаю не так?

PS: Мой пример, конечно, очень сокращен ... это означает, что вершины, которые я хочу сохранить по ссылке, намного больше.

РЕДАКТИРОВАТЬ

Я сейчасизменил мой код: 

struct complex_node_t {
    bool foo1;
    size_t foo2;
    std::reference_wrapper<simple_node_t> control;
};

и попробуйте получить доступ к элементам: 

if (pVal->control.get().enabled) -> **STILL GARBAGE**

1 Ответ

1 голос
/ 03 мая 2019

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

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

Остерегайтесь правил аннулирования, хотя: в зависимости от графовой модели [1]. См

PS. если вы знаете, что у вашего графа есть стабильность ссылок для вершин, вы можете сделать то, что вы хотите, заменив ссылку необработанными указателями или std::reference_Wrapper<>

[1] в случае adjacency_list<> зависит от аргументов шаблона селектора контейнера вершин / ребер

Демо-код

Этот код демонстрирует

  • механика определения графа (с само-ссылочными типами дескрипторов)
  • как НЕ заполнять (см. // BUG)
  • как безопасно заполнять / использовать атрибуты.

Live On Coliru 

#include <boost/graph/adjacency_list.hpp>
#include <variant>

using base_traits = boost::graph_traits<boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS> >;

struct simple_node_t {
    size_t enabled = 0;
};

struct complex_node_t {
    bool foo1 = false;
    size_t foo2 = 0;
    base_traits::vertex_descriptor control {};
};

using vertex_t = std::variant<simple_node_t, complex_node_t>;

using netListGraph_t = boost::adjacency_list<
    boost::vecS,
    boost::vecS,
    boost::undirectedS,
    vertex_t>;

int main() {
    {
        netListGraph_t g;
        auto control = add_vertex(simple_node_t{12}, g);
        // BUG HERE:
        add_vertex(complex_node_t{ true, 42, control }, g); // whoops, might invalidate `control`
    }

    {
        netListGraph_t g(10);
        auto control = vertex(6, g);
        g[control] = simple_node_t{12};

        auto other   = vertex(4, g);
        g[other] = complex_node_t{ true, 42, control }; // fine

        // also fine:
        std::get<complex_node_t>(g[other]).control = control;
    }
}
...