- Java 双重比较
- java - 比较器与 Apache BeanComparator
- Objective-C 完成 block 导致额外的方法调用?
- database - RESTful URI 是否应该公开数据库主键?
我正在尝试重现在 this paper 中进行的实验,测量算法在 DIMACS 顶点着色基准图上的性能,可以找到 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);
}
最佳答案
呵呵。这将是今天要报告的第三个 boost 错误。
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( )
是不可取的,即使大多数库实现都会在这里做预期的事情。
但是,第 156 行中的 *tmp = '\0';
破坏了目标顶点编号。 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 这样的解析生成器:
#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;
}
两个版本的结果都是这张图:
关于c++ - 如何在 C++ 中读取 DIMACS 顶点着色图?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/30415388/
我遇到以下问题。我想读取一个包含数百万行和数百列的大型 csv。我想向下转换列的数据类型。我的方法是读取 csv,然后使用 pd.to_numeric() 对其进行向下转换。我不知道列数及其类型。在读
目前,我从 SQL server (2008) 数据库获取数据。 cyurrent的方法是使用DataTable,然后将其传递并使用。 if (parameters != null)
我有以下问题。我有一个巨大的 csv 文件,想用多处理加载它。对于一个包含 500000 行和 130 列不同数据类型的示例文件,Pandas 需要 19 秒。我试过 dask 因为我想多处理阅读。但
是否有关于用于序列化各种 MFC 数据结构的二进制格式的明确文档?我已经能够在十六进制编辑器中查看我自己的一些类,并使用 Java 的 ByteBuffer 类读取它们(使用自动字节顺序转换等)。 但
我正在使用 Selenium 进行测试,我们用 HTML 文件编写测试用例,并用它们制作测试套件,我们的要求是编写足够健壮的测试用例,以根据测试环境改变自身。 为此,我不希望在 HTML 脚本本身中包
我需要一个 JavaScript 代码来读取存储为 .txt 文件的字典(或者也可以保存为任何其他类型的文件。它也可以在线获得)并将其内容存储在一个变量中。我不能找到一种让 JavaScript 像
我正在尝试遍历包含 SSH 登录和其他日志的日志文本文件。 程序正在返回 SSH 登录的总数。 我的解决方案确实有效,但似乎有点慢(在 200mo 文件上大约需要 3.5 秒)。我想知道是否有任何方法
我正在将大量数据从一个电子表格复制到工作簿中的其他 160 个电子表格。目前,Excel (2013) 遇到错误,因为它没有足够的资源来完成操作。 我的目标是将工作表 4 中 V13:XI1150 范
我正在尝试读取一个有 1147 行的文本文件。下面的代码仅读取第 1050-1147 行。我的目标是读取整个文件并提取位于不同行的特定值以在脚本中使用。一个示例是包含“BlockList: 2”的行中
我正在为游戏编写解释器。用户将其移动输入解释器,程序执行该移动。 现在我想为每个决定实现一个时间限制。玩家不应该能够思考超过 30 秒来写一个移动并按下回车。 call_with_time_limit
以this file例如,我正在尝试读取 data.frame 中的数据。来自 the doc (pdf 文件,表 1),它遵循一些 fortran 约定。我尝试了以下但收效甚微: dir 0' 将
我正在使用 R 阅读 Outlook 附件。我的引用在这里:Download attachment from an outlook email using R 这是我的电子邮件的截图: 这每天都会发送
我不会从表格中读取行来将主题放在列表中 php脚本 $url_obj='http://'.$host.':8069/xmlrpc/object'; $sock=new xmlrpc_client($u
我有一个这样的 csv 文件: id,name,value 1,peter,5 2,peter\,paul,3 我如何读取此文件并告诉 R "\," 不表示新列,仅表示 ","。 我必须添加该文件
我正在尝试读取 ~/Library/Preferences/com.apple.mail.plist (在 Snow Leopard 上)以获取电子邮件地址和其他信息以进入“关于”对话框。我使用以下代
This question already has answers here: How do I use floating-point division in bash? (19个回答) 5个月前关闭
本练习的目标是读取输入文件并将其存储到表中,然后验证输入中的某些字段并输出任何错误记录。我需要读取并存储每个策略组,以便表中一次仅存储 5 条记录,而不是整个文件。 所以我需要读取一个包含 5 条记录
据我了解,LWT 插入始终以 SERIAL 一致性级别完成。如果为 true,这是否意味着读取作为 LWT 插入的行可以安全地以 ANY 的一致性级别读取? 换句话说,我假设 LWT 插入是完全一致的
我看到很多很多通过java脚本读取cookie的函数,但我只想在变量中使用它一次,我是JS新手。 这是我的代码 var TheNumber = (Math.random() + '') * 10000
我正在使用 asp.net 和 C#。我在服务器上部署了一个应用程序[已发布],现在我想查看该网站的代码,据我所知,我可以阅读程序集来查看代码。 请告诉我如何实现它。 提前致谢。 最佳答案 您可以使用
我是一名优秀的程序员,十分优秀!