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

Question

When reading a graph with read_graphviz() of the boost graph Library, the internal index used to store the nodes changes compared with the one used to display the same graph. This is problematic when dealing with big graphs as it becomes difficult to compare them as text files.

I wrote a small example (see below the source code), where I start reading a small graph with

INPUT

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

But then, when printing it with write_graphviz() the output ordering changes:

OUTPUT

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

Although I understand why the node index 10 is reaffected to a smaller value such as all indexes follow each others in ascending order, I don't get why it gets affected index 2 and not 3 as it comes after the index 2 (in input).

I guess that it is because the order used must be somehow a lexicographic order on the index property interpreted as a string, but is this really the case ? In my own program, nodes indexes go above 150 and I get the following reordering:

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

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

Here is the code of this simple example:

#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 ?

You have to make it print as the node_id as well as the index attribute. I'd suggest using dynamic properties once again:

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

Now it prints: Live On Coliru

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

Notes:

• for technical reasons, dynamic_properties does not accept read-only property maps by default. You can work around this so you can define operator<< to take DAG const&, see boost::dynamic_properties and immutable graph object

• You can also READ with node_id but there are some caveats. Your current graph model has a vertex container selector (vecS) that has an implicit vertex_index that matches the vector index. Reading the node_id from the index attribute would lead to a "sparse" graph (vertices 3..9 would also exist without any edges and no meaningful index property).

  You can change the selector to something else, but then you require a vertex_index property map. The only elegant way to supply it implicitly to relevant algorithms would be

  • using internal properties (instead of the property bundle that you're currently using, which can be cumbersome)
  • using traits specializing the propert-map selector

  Showing how to do that, just for completeness: Live On Coliru

  Note that this no longer specifically reads the index attribute, because the node_id already populates Node::index directly.

Full Listing

Of the first solution above:

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