c++ - 为什么Boost图形库的read_graphviz()函数会更改节点的索引

Question

读取带有升压图形库的read_graphviz()的图形时，用于存储节点的内部索引与用于显示同一图形的索引相比会发生变化。在处理大图时，这很成问题，因为很难将它们作为文本文件进行比较。

我写了一个小例子(见下面的源代码)，在这里我开始阅读一个小图

输入

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会被较小的值所影响，例如所有索引都以升序相互跟随，但是我不明白为什么它会影响索引2，而不是索引2之后的3(在输入中) 。

我猜这是因为所使用的顺序必须是索引属性解释为字符串的字典顺序，但这是真的吗？在我自己的程序中，节点索引超过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

My Question: how can I avoid this behavior such that internal node index always match my own index ?

您必须使其打印为node_id以及index属性。我建议再次使用动态属性:

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 and immutable graph object

您也可以使用node_id进行读取，但有一些警告。您当前的图形模型具有一个顶点容器选择器(vecS)，该选择器具有一个与 vector 索引匹配的隐式vertex_index。从node_id属性读取index将导致“稀疏”图形(也将存在顶点3..9，没有任何边且没有有意义的索引属性)。

您可以将选择器更改为其他选择器，但随后需要vertex_index属性映射。隐式提供给相关算法的唯一优雅方法是

使用内部属性(而不是您当前正在使用的属性束，这可能很麻烦)

使用专门用于propert-map选择器的特征

展示如何做到这一点，仅出于完整性考虑: Live On Coliru

请注意，这不再专门读取index属性，因为node_id已经直接填充 Node::index。
完整 list

在上述第一个解决方案中:

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;
    }
}