Почему функция read_graphviz () библиотеки графов наддува изменяет индекс узлов

Question

При чтении графика с помощью read_graphviz() библиотеки графов буста внутренний индекс, используемый для хранения изменений узлов, сравнивается с индексом, используемым для отображения того же графика. Это проблематично c при работе с большими графиками, так как становится трудно сравнивать их как текстовые файлы.

Я написал небольшой пример (см. Ниже исходного кода), где я начал читать небольшой график с

INPUT

digraph G {
0[index=0];
1[index=1];
2[index=2];
10[index=10];
}

Но затем при печати с помощью write_graphviz () порядок вывода изменяется:

ВЫХОД

digraph G {
0[index=0];
1[index=1];
2[index=10]; /* <= mismatch here ! */
3[index=2];  /* <= and here !      */
}

Хотя я понимаю, почему узел индекс 10 это влияет на меньшее значение, такое как все индексы следуют друг за другом в порядке возрастания, я не понимаю, почему это влияет index 2 , а не 3 , как это происходит после индекса 2 (на входе).

Я полагаю, это потому, что используемый порядок должен быть как-то лексикографическим c порядком для свойства index, интерпретируемого как строка, но так ли это на самом деле? В моей собственной программе индексы узлов go выше 150, и я получаю следующее переупорядочение:

0[index=0000];
1[index=0001];
2[index=0010];
3[index=0100];
4[index=0101];
5[index=0102];
6[index=0103];
7[index=0104];
8[index=0105];
9[index=0106];
10[index=0107];
11[index=0108];
12[index=0109];
13[index=0011];
14[index=0110];
15[index=0111];

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

Вот код этого простого примера:

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

using namespace std;

struct Node { std::size_t index; };


/*! \brief DAG: Directed Acyclic Graph */
typedef boost::adjacency_list<boost::listS, boost::vecS, boost::directedS, Node> DAG;

template<class IndexMap> class node_writer {
public:
    node_writer(IndexMap n) : inm(n) {}
    template<class Vertex>  void operator()(std::ostream & out, const Vertex & v) {
        out << "[index=" << inm[v] << "]";
    }

private:
    IndexMap inm;
};

template<class IndexMap>
inline node_writer<IndexMap> make_node_writer(IndexMap inm) {
    return node_writer<IndexMap>(inm);
}

std::ostream & operator<<(std::ostream & o, const DAG & g) {
    boost::write_graphviz(o, g, make_node_writer(boost::get(&Node::index, g)));
    return o;
}

std::istream & operator>>(std::istream & i, DAG & g)
{
    boost::dynamic_properties dp(boost::ignore_other_properties);
    dp.property("index", get(&Node::index, g));
    read_graphviz(i, g, dp);
    return i;
}

int main(int argc, char * argv[])
{
    DAG * pTree = new DAG(0);
    std::stringstream  dag_file;
    dag_file << "digraph G {\n";
    dag_file << "0[index=0];\n";
    dag_file << "1[index=1];\n";
    dag_file << "2[index=2];\n"; 
    dag_file << "10[index=10];\n";
        dag_file << "}";
    std::cout << dag_file.str() << "\n";
    dag_file >> *pTree;
    std::cout <<  *pTree;
    return 0;
}

Answer 1

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

Вы должны сделать так, чтобы он печатался как идентификатор_узла, а также атрибут индекса , Я бы предложил еще раз использовать свойства Dynami c:

std::ostream & operator<<(std::ostream & o, DAG& g) {
    boost::dynamic_properties dp(boost::ignore_other_properties);
    dp.property("node_id", get(&Node::index, g));
    dp.property("index", get(&Node::index, g));
    boost::write_graphviz_dp(o, g, dp);
    return o;
}

Теперь он печатает: Live On Coliru

digraph G {
0 [index=0];
1 [index=1];
10 [index=10];
2 [index=2];
}

Примечания:

• по техническим причинам dynamic_properties по умолчанию не принимает карты свойств, доступные только для чтения. Вы можете обойти это, так что вы можете определить operator<< для получения DAG const&, см. boost :: dynamic_properties и неизменяемый графический объект

• Вы также можете прочитать с помощью node_id но есть некоторые предостережения. Ваша текущая модель графа имеет селектор вершинного контейнера (vecS), который имеет неявный vertex_index, который соответствует векторному индексу. Чтение node_id из атрибута index приведет к «разреженному» графу (вершины 3..9 также будут существовать без каких-либо ребер и без значимого свойства индекса).

  Вы можете измените селектор на что-то другое, но тогда вам потребуется a vertex_index карта свойств. Единственный элегантный способ неявного предоставления его соответствующим алгоритмам - это

  • с использованием внутренних свойств (вместо используемого в настоящее время набора свойств, что может быть громоздким)
  • с использованием черты, специализирующиеся на селекторе карты свойств

  Показано, как это сделать, просто для полноты: Live On Coliru

  Обратите внимание, что здесь больше не читается атрибут index, поскольку node_id уже заполняет Node::index напрямую.

Полный список

Из первого решения выше:

Live On Coliru

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

using namespace std;

struct Node { std::size_t index; };

/*! \brief DAG: Directed Acyclic Graph */
typedef boost::adjacency_list<boost::listS, boost::vecS, boost::directedS, Node> DAG;

std::ostream & operator<<(std::ostream & o, DAG& g) {
    boost::dynamic_properties dp(boost::ignore_other_properties);
    dp.property("node_id", get(&Node::index, g));
    dp.property("index", get(&Node::index, g));
    boost::write_graphviz_dp(o, g, dp);
    return o;
}

std::istream & operator>>(std::istream & i, DAG & g) {
    boost::dynamic_properties dp(boost::ignore_other_properties);
    dp.property("index", get(&Node::index, g));
    read_graphviz(i, g, dp);
    return i;
}

int main() {
    auto const input = R"(digraph G {
    0[index=0];
    1[index=1];
    2[index=2];
    10[index=10];
})";
    std::stringstream dag_file(input);
    std::cout << input << std::endl;

    {
        DAG tree;
        dag_file >> tree;
        std::cout << tree;
    }
}