为什么boost图库的read_graphviz()函数会改变节点的索引

Question

当使用 boost 图形库的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 !      */
}

虽然我明白为什么节点 index 10 会重新影响到一个较小的值，例如所有索引都按升序排列，但我不明白为什么它会受到影响 index 2 而不是 3 因为它位于索引 2 之后（在输入中）。

我猜这是因为使用的顺序一定是索引属性上解释为字符串的某种词典顺序，但真的是这样吗？在我自己的程序中，节点索引超过 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 以及索引属性。我建议再次使用动态属性：

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)，它有一个与向量索引匹配的隐式 vertex_index。从 index 属性读取 node_id 将导致一个 "sparse" 图（顶点 3..9 也将存在，没有任何边并且没有有意义的索引属性）。

您可以将选择器更改为其他内容，但随后您需要一个vertex_index属性映射.将其隐式提供给相关算法的唯一优雅方式是
- 使用内部属性（而不是您当前使用的属性包，后者可能很麻烦）
- 使用特化属性映射选择器的特征
展示如何做到这一点，只是为了完整性：Live On Coliru

请注意，这不再专门读取索引属性，因为 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;
    }
}

为什么boost图库的read_graphviz()函数会改变节点的索引

Why does the read_graphviz() function of the boost graph library changes the index of the nodes

c++

boost

boost-graph

完整列表