2

I'm trying to reproduce the experiments carried out in this paper, measuring the performance of an algorithm on the DIMACS Vertex-Coloring benchmark graphs, which can be found here.

The graphs are in the DIMACS Standard format, and I'd like to parse them into the C++ Boost Graph Library format, so I can run my algorithm on them.

I've tried parsing them using the existing Boost DIMACS functions, but the documentation on them is fairly sparse, so I'm unclear on how exactly to use the functions. When I print the graph to Graphviz, the result doesn't seem to match the DIMACS file.

I'm wondering:

  1. What am I doing wrong using the Boost parsing functions? (See example below)

  2. Is there a better or alternative C++ library for easily parsing the DIMACS standard graph format?

Here's my attempt at parsing and printing the graphs:

#include <cstdlib>
#include <iostream>

#include <boost/property_map/property_map.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/graphviz.hpp>
#include <boost/graph/dimacs.hpp>

#include <fstream>

using namespace boost::graph;

typedef boost::adjacency_list < boost::vecS, boost::vecS, boost::undirectedS > Graph;
typedef typename boost::graph_traits<Graph>::edge_descriptor Edge;
typedef typename boost::graph_traits<Graph>::vertex_descriptor Vertex; 


int main()
{
std::ifstream inGraphFile;
inGraphFile.open("myciel4.col");


dimacs_basic_reader reader(inGraphFile, false);
dimacs_basic_reader end;
dimacs_edge_iterator<dimacs_basic_reader> dimacsStart(reader);
dimacs_edge_iterator<dimacs_basic_reader> endIter(end);


Graph g2(dimacsStart, endIter, reader.n_vertices());
boost::write_graphviz(std::cout, g2);

}

1 Answer 1

7

Hehe. This is gonna be the third boost bug to report today.

The dimacs parsing code looks truly evil to me. The interface is very inconvenient and the implementation... Well, as you found it's very wrong:

In read_edge_line there is this loop:

if ('e' == linebuf[0]) {
    while (*tmp != '\n' && *tmp != '\0') {
        if (*tmp == ' ') { 
            *tmp = '\0';
            ts = ++tmp;
            break;
        }
        tmp++;
    }
    *tmp = '\0';                                    /* LINE 156 */
    if (NULL == fs || NULL == ts) return false;
    from = atoi(fs); to = atoi(ts); weight = 0;

} else // ...

Of course, writing through the c_str() char const* pointer is undefined behaviour to begin with (the cast (char*) buf.c_str() is simply not advisable, even though most library implementations will do the expected thing here).

However, the *tmp = '\0'; in line 156 trashes the target vertex number. atoi fails silently and there's indeterminate data in to.

Manual Parser

Instead of this mess, I'd really recommend writing the parsing yourself. It can be very simple:

Live On Coliru

#include <string>
#include <istream>
#include <sstream>

template <typename Graph>
bool read_coloring_problem(std::istream& dimacs, Graph& g) {
    size_t vertices = 0, edges = 0;

    std::string line;
    while (getline(dimacs, line))
    {
        std::istringstream iss(line);
        char ch;
        if (iss >> ch)
        {
            size_t from, to;
            std::string format;

            switch(ch) {
                case 'c': break;
                case 'p': 
                    if (vertices||edges) return false;
                    if (iss >> format >> vertices >> edges) {
                        if ("edge" != format) return false;
                    }
                    break;
                case 'e': 
                    if (edges-- && (iss >> from >> to) && (add_edge(from-1, to-1, g).second))
                        break;
                default: 
                    return false;
            }
        }
    }

    return !(edges || !dimacs.eof());
}

Boost Spirit Parser

But my preference would be to use a parse generator like Boost Spirit:

Live On Coliru

#include <boost/spirit/include/qi.hpp>
#include <boost/spirit/include/phoenix.hpp>
#include <boost/spirit/include/qi_match.hpp>

template <typename Graph>
bool read_coloring_problem(std::istream& dimacs, Graph& g) {
    auto add_edge_ = [&g](size_t from, size_t to) { add_edge(from, to, g); };
    size_t vertices = 0, edges = 0;

    using namespace boost::spirit::qi;
    namespace px = boost::phoenix;
    uint_parser<size_t> num_;

    auto eoil      = eol | eoi;
    auto comment   = boost::proto::deep_copy(lexeme["c " >> *(char_ - eol) >> eoil] | eol);
    auto vertices_ = px::ref(vertices);
    auto edges_    = px::ref(edges);

    dimacs >> std::noskipws >> phrase_match(
            *comment >>
            ("p" >> lit("edge") >> num_ [vertices_ = _1] >> num_ [edges_ = _1] >> eoil) >>
            repeat(edges_) [ 
                *comment >> ("e" >> num_ >> num_ >> eoil) [ px::bind(add_edge_, _1-1, _2-1) ]
            ] 
            >> *comment >> eoi
            , blank);

    return dimacs;
}

Output

Both version result in this graph:

enter image description here

4
  • 1
    I've updated the "simple" parser. It had bugs. This is why I prefer the parser generator approach.
    – sehe
    May 25, 2015 at 22:37
  • Thanks! I've written parsers before, but never in C++, and I wasn't terribly familiar with the details of the DIMACS format. I'll try these out right away. Thanks so much!
    – jmite
    May 26, 2015 at 1:05
  • 1
    I used this mat.gsia.cmu.edu/COLOR/general/ccformat.ps description as a reference
    – sehe
    May 26, 2015 at 8:23
  • 1
    Thanks, @sehe, this just came in useful to me! May 5 at 5:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.