Odd Error Importing DOT files

问题:

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.

回答1:

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:

回答2:

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.