Вложенные графы Boost.Graph и Graphviz

Question

Я ожидал, что код

#include <boost/graph/graphviz.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/subgraph.hpp>
#include <iostream>

using namespace boost;

using attrs_t = std::map<std::string, std::string>;

using graph_t = adjacency_list<
    vecS, vecS, directedS,
    property<vertex_attribute_t, attrs_t>,
    property<edge_index_t, int, property<edge_attribute_t, attrs_t>>,
    property<graph_name_t, std::string,
        property<graph_graph_attribute_t, attrs_t,
            property<graph_vertex_attribute_t, attrs_t,
                property<graph_edge_attribute_t, attrs_t>>>>>;

int main()
{
    char names[] = {"AB"};
    enum {A, B, N};

    subgraph<graph_t> main(N);
    subgraph<graph_t>& sub1 = main.create_subgraph();
    subgraph<graph_t>& sub2 = sub1.create_subgraph();

    add_vertex(A, sub1);
    add_vertex(B, sub2);
    add_edge(A, B, main);

    get_property(main, graph_name) = "G0";
    get_property(sub1, graph_name) = "clusterG1";
    get_property(sub2, graph_name) = "clusterG2";

    write_graphviz(std::cout, main, make_iterator_vertex_map(names));
}

сгенерирует график слева, тогда как у меня есть правильный:

Вывод:

digraph G0 {
subgraph clusterG1 {
subgraph clusterG2 {
//B;
}
//A;
}
A -> B;
}

Комментированные операторы узла - это то место, где теряется информация об иерархии (этих строк у меня нет в моем выводе).Как я могу избежать этого?

---

Если я добавлю обе вершины в один и тот же подграф:

add_vertex(A, sub1);
add_vertex(B, sub1);
add_edge(A, B, main);

соединение A -> B появится в области действия clusterG1 и какЯ понимаю, что именно здесь упомянутые вершины также будут неявно объявлены.

Я использую Boost 1.68.0

Answer 1

Хорошее место.Связанный ответ на самом деле имеет UB, как объясняет ваш собственный ответ.Карта, передаваемая в функцию write_graphviz, на самом деле не должна иметь node_id для вывода graphviz.Вместо этого предполагалось, что эта карта является vertex_index_t картой свойств.

Это было предположение, которое я, вероятно, понял из boost::print_graph (graph_utility.hpp), что делает такой картой свойств.

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

int main() {
    boost::dynamic_properties dp;
    dp.property("node_id", boost::make_transform_value_property_map<std::string>(&name_for_index, boost::identity_property_map{}));
    write_graphviz_dp(std::cout, create_data<subgraph<Graph> >(), dp);
}

Я решил использовать функцию преобразования, чтобы получить имя для любой вершиныдескриптор, не желая больше предполагать количество вершин, я написал более общую функцию для генерации имен типа «A», ..., «Z», «AA», ..., «ZZ» и т. д.:

static std::string name_for_index(intmax_t index) {
    std::string name;

    do {
        name += 'A' + (index%26);
        index /= 26;
    } while (index);

    return name;
}

Live On Coliru

Сохранение информации о подграфе

Указанная перегрузка отсутствуетнет поддержки подграфа.Итак, вместо этого давайте исправим карту vertex_attribute, чтобы иметь ожидаемые метки вершин:

int main() {
    auto g = create_data<subgraph<Graph> >();

    for (auto vd : make_iterator_range(vertices(g))) {
        put(get(vertex_attribute, g), vd, 
                GraphvizAttributes{
                    {"label", name_for_index(vd)}
                });
    }

    write_graphviz(std::cout, g);
}

Теперь она печатает:

Live On Coliru

digraph G0 {
subgraph clusterG1 {
graph [
label=G1];
node [
color=red, shape=Mrecord];
0[label="Vertex A"];
1[label="Vertex B"];
0 -> 1;
}
subgraph clusterG2 {
graph [
fillcolor=lightgray, label=G2, style=filled];
node [
shape=circle];
4[label="Vertex E"];
2[label="Vertex C"];
5[label="Vertex F"];
4 -> 5;
2 -> 5;
}
3[label="Vertex D"];
1 -> 2;
1 -> 3;
4 -> 1;
5 -> 3;
}

Что отображается как

Answer 2

Проблема была вызвана введением make_iterator_vertex_map(names), который возвращает char s из names ('A', 'B').Это несовместимо с ожидаемыми (и по умолчанию) vertex_index свойствами (0, 1).После исправления я получаю:

digraph G0 {
subgraph clusterG1 {
subgraph clusterG2 {
1;
}
0;
}
0 -> 1;
}

vertex_marker, что в моем случае составляет std::vector<bool> из 2 элементов, а не 67 и более, как ожидается, будет проиндексировано индексами вершин.Я испытывал неопределенное поведение,
и if ( vertex_marker[pos] ) никогда не выполнялись.

Ответственная часть boost::detail::write_graphviz_subgraph:

// Print out vertices and edges not in the subgraphs.

typename graph_traits<Graph>::vertex_iterator i, end;
typename graph_traits<Graph>::edge_iterator ei, edge_end;

for(boost::tie(i,end) = vertices(g); i != end; ++i) {
  Vertex v = g.local_to_global(*i);
  int pos = get(vertex_id, v); // 66, 65, should be 1, 0
  if ( vertex_marker[pos] ) {  // out-of-bounds access
    vertex_marker[pos] = false;
    out << escape_dot_string(pos);
    make_vertex_attributes_writer(g.root())(out, v);
    out << ";" << std::endl;
  }
}

A static_assert / SFINAE vertex_id Тип параметра против Graph 'vertex_id типа (который можно сделать сразу в boost::write_graphviz) будет приветствоваться.Кстати, жестко закодированный int pos = ... выглядит не слишком профессионально ...

И если мы хотим сохранить пользовательские имена, мы должны предоставить их с помощью атрибутов label.