如何在 C++ 中读取 DIMACS 顶点着色图?
How to read DIMACS Vertex-coloring graphs in C++?
我正在尝试重现 this paper, measuring the performance of an algorithm on the DIMACS Vertex-Coloring benchmark graphs, which can be found here 中进行的实验。
图表采用 DIMACS 标准格式,我想将它们解析为 C++ Boost 图表库格式,这样我就可以 运行 我的算法。
我试过使用现有的 Boost DIMACS 函数解析它们,但是关于它们的文档相当稀少,所以我不清楚如何使用这些函数。当我将图形打印到 Graphviz 时,结果似乎与 DIMACS 文件不匹配。
我在想:
我在使用 Boost 解析函数时做错了什么? (见下面的例子)
是否有更好或替代的 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);
}
呵呵。这将是今天要报告的第三个提升错误。
dimacs 解析代码对我来说真的很邪恶。界面很不方便,实现起来...嗯,你发现很不对:
在read_edge_line
中有这个循环:
if ('e' == linebuf[0]) {
while (*tmp != '\n' && *tmp != '[=10=]') {
if (*tmp == ' ') {
*tmp = '[=10=]';
ts = ++tmp;
break;
}
tmp++;
}
*tmp = '[=10=]'; /* 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()
是不可取的,即使大多数库实现都符合预期事情在这里)。
然而,第 156 行中的 *tmp = '[=17=]';
破坏了目标顶点编号。 atoi
无声地失败并且 to
中有 不确定数据 。
手动解析器
为了避免这种混乱,我真的建议您自己编写解析。它可以很简单:
#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 解析器
但我更喜欢使用像 Boost Spirit 这样的解析生成器:
#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;
}
输出
此图的两个版本结果:
我正在尝试重现 this paper, measuring the performance of an algorithm on the DIMACS Vertex-Coloring benchmark graphs, which can be found here 中进行的实验。
图表采用 DIMACS 标准格式,我想将它们解析为 C++ Boost 图表库格式,这样我就可以 运行 我的算法。
我试过使用现有的 Boost DIMACS 函数解析它们,但是关于它们的文档相当稀少,所以我不清楚如何使用这些函数。当我将图形打印到 Graphviz 时,结果似乎与 DIMACS 文件不匹配。
我在想:
我在使用 Boost 解析函数时做错了什么? (见下面的例子)
是否有更好或替代的 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);
}
呵呵。这将是今天要报告的第三个提升错误。
dimacs 解析代码对我来说真的很邪恶。界面很不方便,实现起来...嗯,你发现很不对:
在read_edge_line
中有这个循环:
if ('e' == linebuf[0]) {
while (*tmp != '\n' && *tmp != '[=10=]') {
if (*tmp == ' ') {
*tmp = '[=10=]';
ts = ++tmp;
break;
}
tmp++;
}
*tmp = '[=10=]'; /* 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()
是不可取的,即使大多数库实现都符合预期事情在这里)。
然而,第 156 行中的 *tmp = '[=17=]';
破坏了目标顶点编号。 atoi
无声地失败并且 to
中有 不确定数据 。
手动解析器
为了避免这种混乱,我真的建议您自己编写解析。它可以很简单:
#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 解析器
但我更喜欢使用像 Boost Spirit 这样的解析生成器:
#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;
}
输出
此图的两个版本结果: