Как читать графы раскраски вершин DIMACS на С++?

Я пытаюсь воспроизвести эксперименты, проведенные в эта статья, измеряющая производительность алгоритма на тестовых графиках DIMACS Vertex-Coloring, которые можно найти здесь.

Графики представлены в стандартном формате DIMACS, и я хотел бы проанализировать их в формате библиотеки C++ Boost Graph Library, чтобы я мог запустить на них свой алгоритм.

Я пытался анализировать их, используя существующие функции Boost DIMACS, но документация по ним довольно скудна, поэтому я не совсем понимаю, как именно использовать эти функции. Когда я печатаю график в Graphviz, результат не соответствует файлу DIMACS.

Мне любопытно:

  1. Что я делаю неправильно, используя функции парсинга Boost? (см. пример ниже)

  2. Есть ли лучшая или альтернативная библиотека C++ для простого разбора стандартного графического формата DIMACS?

Вот моя попытка разбора и печати графиков:

#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);

}

c++ boost graph graph-coloring boost-graph
person jmite    schedule 23.05.2015    source источник

Ответы (1)


arrow_upward
6
arrow_downward

Хе-хе. Это будет третья ошибка, о которой нужно сообщить сегодня.

Код синтаксического анализа dimacs кажется мне действительно злым. Интерфейс очень неудобный, а реализация... Ну, как вы поняли, очень неправильная:

В read_edge_line есть этот цикл:

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 // ...

Конечно, запись через указатель c_str() char const* с самого начала является неопределенным поведением (приведение (char*) buf.c_str() просто не рекомендуется, даже несмотря на то, что большинство реализаций библиотек будут делать здесь ожидаемые вещи).

Однако *tmp = '\0'; в строке 156 сбрасывает номер целевой вершины. atoi автоматически завершается сбоем, и в to есть неопределенные данные.

Ручной парсер

Вместо этого бардака я бы очень рекомендовал написать парсинг самостоятельно. Это может быть очень просто:

Прямой эфир на 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:

Жить на 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;
}

Выход

Обе версии приводят к этому графику:

введите здесь описание изображения

person sehe    schedule 25.05.2015
comment
Я обновил простой синтаксический анализатор. В нем были ошибки. Вот почему я предпочитаю подход генератора парсеров. - person sehe; 26.05.2015
comment
Спасибо! Я писал синтаксические анализаторы раньше, но никогда не писал на C++, и я не очень хорошо разбирался в деталях формата DIMACS. Я попробую эти прямо сейчас. Большое спасибо! - person jmite; 26.05.2015
comment
Я использовал этот mat.gsia.cmu.edu/COLOR/general/ccformat.ps описание в качестве ссылки - person sehe; 26.05.2015