Odd Error Importing DOT files

Question

For my C++ program, I need to read in a DOT file using Boost Graph, and later output another DOT file. However, I am encountering a weird error in the read-in stage which is really screwing up my program.

My read-in code (Graph type is a typedef of a bidirectional Boost graph)

void readGraph(Graph& graph, string filename) {

    boost::dynamic_properties dp(boost::ignore_other_properties);

    ifstream fin(filename.c_str());
    boost::read_graphviz(fin, graph, dp);

}

Ok, so the problem is that the nodes in the .DOT file are read in in the wrong order! I tried it with a simple example .DOT file:

digraph G {
0; 1; 2; 3; 4; 5; 6; 7; 8; 9; 10;
0->1; 1->0;
1->2; 2->1;
2->3; 3->2;
3->4; 4->3;
4->5; 5->4;
5->6; 6->5;
6->7; 7->6;
7->8; 8->7;
8->9; 9->8;
9->10; 10->9;
}

This is a bi-directional chain from node 0 to node 10. However if I read this file using Boost Graph and output it immediately without changes, it becomes:

digraph G {
0;
1;
2;
3;
4;
5;
6;
7;
8;
9;
10;
0->1 ;
1->3 ;
3->4 ;
4->5 ;
5->6 ;
6->7 ;
7->8 ;
8->9 ;
9->10 ;
10->2 ;
1->0 ;
3->1 ;
4->3 ;
5->4 ;
6->5 ;
7->6 ;
8->7 ;
9->8 ;
10->9 ;
2->10 ;
}

Notice, node 2 is now inexplicably connected to node 10, and is at the end of the chain. I have done nothing in between reading and outputting the graph.

Notes:

When I try this with more complicated .DOT files, the topology of the graph remains the same, it's just that the nodes have been permuted for some odd reason.
I know it is a read, not write error, because when I output the vertices and edges during the program, they are already screwed up.

Can anyone help me understand and fix this? Thanks.

score 2 · Accepted Answer · answered Sep 27 '15 at 20:08

If you read the graph and print the resulting again (in graphviz format), you'll find that the graphs are equivalent (or isomorphic):

Live On Coliru

#include <boost/graph/graphviz.hpp>
#include "/Archive2/45/a4410ef1bd3024/main.cpp" // alias <libs/graph/src/read_graphviz_new.

using Graph = boost::adjacency_list<boost::vecS, boost::vecS, boost::directedS>;

void readGraph(Graph &graph, std::string filename) {
    boost::dynamic_properties dp(boost::ignore_other_properties);

    std::ifstream fin(filename.c_str());
    boost::read_graphviz(fin, graph, dp);
}

int main() {
    Graph g;
    readGraph(g, "input.dot");

    boost::write_graphviz(std::cout, g);
}

With your input:

The output is clearly iso-morphic:

NOTE The output shown in your own question is simply that too!

What you actually want is for the vertex ID's to be retained.

In order to do that, you'll have to store the vertex ID (as read from the dot file) into a property explicitly. Here is an example:

Live On Coliru

#include <boost/graph/graphviz.hpp>
#include "/Archive2/45/a4410ef1bd3024/main.cpp" // alias <libs/graph/src/read_graphviz_new.

using namespace boost;

struct MyVertex {
    int id;
};

using Graph = adjacency_list<
    vecS, vecS, directedS, 
    MyVertex
>;

void readGraph(Graph &graph, std::string filename) {
    boost::dynamic_properties dp(boost::ignore_other_properties);
    dp.property("node_id", boost::get(&MyVertex::id, graph));

    std::ifstream fin(filename.c_str());
    boost::read_graphviz(fin, graph, dp);
}

int main() {
    Graph g;
    readGraph(g, "input.dot");

    boost::dynamic_properties dp(boost::ignore_other_properties);
    dp.property("node_id", boost::get(&MyVertex::id, g));
    boost::write_graphviz_dp(std::cout, g, dp);
}

Generates:

score 1 · Answer 2 · answered Sep 27 '15 at 09:30

Ok, so I did more investigating. I modified my read-in function to be:

void readGraph(Graph& graph, string filename) {

    boost::dynamic_properties dp(boost::ignore_other_properties);

    ifstream fin(filename.c_str());

    dp.property("node_id", boost::get(&vert::id, graph));
    boost::read_graphviz(fin, graph, dp, "node_id");

}

Where I have created the struct

vert {
    int id;
}

as the bundled property for my vertices in my Graph:

typedef boost::adjacency_list<boost::listS, boost::vecS, boost::bidirectionalS, vert, edge> Graph;

If I now print out all the vertices and edges of the read-in graph using the .id bundle:

Graph h;
readGraph(h, "InputGraph.dot");
for(pair<vertexIt, vertexIt> it = boost::vertices(h); it.first != it.second; ++it.first) {
    cout << h[*it.first].id << endl;
}
for(pair<edgeIt, edgeIt> it = boost::edges(h); it.first != it.second; ++it.first) {
    cout << h[source(*it.first,h)].id << " -> " << h[target(*it.first,h)].id << endl;
}

I get:

0
1
10
2
3
4
5
6
7
8
9
0 -> 1
1 -> 0
1 -> 2
2 -> 1
2 -> 3
3 -> 2
3 -> 4
4 -> 3
4 -> 5
5 -> 4
5 -> 6
6 -> 5
6 -> 7
7 -> 6
7 -> 8
8 -> 7
8 -> 9
9 -> 8
9 -> 10
10 -> 9

So we see a potential problem - the nodes have been read in alphabetically. I don't know how this explains the weird 2->10 connection I saw before. Thankfully, the .id bundle stores the true information of the nodes, so we just use that to access the graph. I still think it's really silly and un-intuitive how read_graphviz parses the dot file though.

please wait with self-accepting here. I'll find the time later to read the question fully. I might find the underlying problem. Meanwhile, you can [search my existing answers](http://stackoverflow.com/search?tab=relevance&q=user%3a85371%20read_graphviz) in case you catch something you're doing differently — sehe, Sep 27 '15 at 11:00
There wasn't anything spooky going on after all (the "spurious" connection (_node 2 is now inexplicably connected to node 10_) is explained in my answer. — sehe, Sep 27 '15 at 20:12
+1-ed because I see you nearly had all the ingredients here. I would just disagree "it's really silly and unintuitive" - at the time of reading there's no way the parser knows the type of the node id. By the way, if you can afford to change the formatting of the node ids (to e.g. `02` and `03`) then there's another option: https://vimeo.com/channels/761265 — sehe, Oct 03 '15 at 14:10

Odd Error Importing DOT files

2 Answers2

Linked