0

我正在尝试在 C++ 中构建一个图形实例解析器，它将图形节点作为输入并将它们插入到由 LEMON 库定义的 SmartGraph 类中。

该库不允许我插入具有特定 ID 的节点（据我在文档中所见），因此我创建了一个并行结构来存储输入文件的节点 ID 和节点 ID 之间的关系我的代码中的实际图表（可能有一个聪明的方法来解决这个问题，但我没有考虑太多，这对我来说听起来不错，只要实例不是那么大以至于我用完内存，这几乎是不可能的）。为此，我使用了一个 std::map ，它将输入文件 ID 作为键，将图形节点 ID 作为值。

如果我只是执行程序，这个 std::map 在从输入文件中读取行的循环的第 239 次迭代中崩溃，如果我用 Valgrind 检查它，它会达到 2252，这让我觉得我必须做一个真正的大的疏忽和某处的内存泄漏，但我无法弄清楚。代码如下

#include <lemon/smart_graph.h>
#include <lemon/concepts/graph.h>
#include <iostream>
#include <fstream>
#include <map>
#include <string>

using std::cout;
using std::cin;
using std::getline;
using std::vector;
using std::string;
using std::stringstream;
using std::exception;
using std::ifstream;
using std::ios;
using std::map;

using lemon::SmartGraph;

map<int, int> instance_graph_ids;
map<int, int>::iterator it;
SmartGraph graph;
ifstream input_instance("instance.txt", ios::in);
string current_line;
while (getline (input_instance, current_line))
    {
        stringstream stream(current_line);
        string buffer;
        vector <int> separated_nodes;
        while(getline(stream, buffer, '\t')){
            separated_nodes.push_back(stoi(buffer));
        };
        for (int node : separated_nodes){
            it = instance_graph_ids.find(node);
            if (it == instance_graph_ids.end())
                {
                    int new_node_id;
                    SmartGraph::Node new_node = graph.addNode();
                    new_node_id = graph.id(new_node);
                    instance_graph_ids.insert({ node, new_node_id });
                };
        };
        auto first_node_iterator = instance_graph_ids.find(separated_nodes[0]);
        auto second_node_iterator = instance_graph_ids.find(separated_nodes[1]);
        graph.addEdge( graph.nodeFromId(first_node_iterator -> first),graph.nodeFromId(second_node_iterator -> second));
    }

我知道这很丑陋，但我正试图在我开始精巧之前让它发挥作用，所以请耐心等待。node 是输入文件中节点的 ID，以整数表示。它在尝试 .insert() instance_graph_ids 中的值时崩溃，这是我之前写过的地图结构。我已经用 gdb 进行了检查，node 和 new_node_id 都是普通整数，instance_graph_ids 上的现有值对我来说也不错。尝试在 gdb 中的 instance_graph_ids 中调用 find() 或 insert() 会返回“尝试获取不在内存中的值的地址”错误。我在这里想念什么？

编辑了一个完整的例子。示例实例可从https://snap.stanford.edu/data/oregon1_010331.txt.gz下载

4

1 回答 1

0

你应该first_node_iterator->first改为first_node_iterator->second

graph.addEdge(graph.nodeFromId(first_node_iterator->second),
              graph.nodeFromId(second_node_iterator->second));

例如，在处理“10000 4725”的第一行时，
使用std::vector存储节点，SmartGraph当
std::vector只有两个元素时graph.addEdge，
使用first_node_iterator->first(value is 10000)作为下标，超出范围。

修改后的代码：

#include <lemon/smart_graph.h>
#include <lemon/concepts/graph.h>
#include <iostream>
#include <fstream>
#include <map>
#include <string>
#include <assert.h>

using std::cout;
using std::cin;
using std::getline;
using std::vector;
using std::string;
using std::stringstream;
using std::exception;
using std::ifstream;
using std::ios;
using std::map;

using lemon::SmartGraph;

int main()
{
    map<int, int> instance_graph_ids;
    map<int, int>::iterator it;
    SmartGraph graph;
    ifstream input_instance("instance.txt", ios::in);
    string current_line;

    while (getline (input_instance, current_line)) {
        stringstream stream(current_line);
        string buffer;
        vector <int> separated_nodes;

        while (getline(stream, buffer, '\t')) {
            separated_nodes.push_back(stoi(buffer));
        };

        for (int node : separated_nodes) {
            it = instance_graph_ids.find(node);

            if (it == instance_graph_ids.end()) {
                int new_node_id;
                SmartGraph::Node new_node = graph.addNode();
                new_node_id = graph.id(new_node);
                instance_graph_ids.insert({ node, new_node_id });
            };
        };

        auto first_node_iterator = instance_graph_ids.find(separated_nodes[0]);
        auto second_node_iterator = instance_graph_ids.find(separated_nodes[1]);

        assert(first_node_iterator->second < graph.nodeNum());
        graph.addEdge(graph.nodeFromId(first_node_iterator->second),
                      graph.nodeFromId(second_node_iterator->second));
    }

    return 0;
}
于 2019-03-15T10:02:52.443 回答