1475 字
7 分钟
GrapSO复现记录
2025-05-15
编程
论文复现
/
踩坑
/
图计算

GraphSO#

HUST开发的用于核外单机图系统的存储管理系统，通过集成到已有系统，对已有系统图划分的再次划分和存储管理、调度，以提升图系统性能。Github

GridGraph#

THU开发的核外单机图计算系统，GraphSO公布的源码就是集成在其上。

复现中遇到的问题#

在尝试编译运行其系统时，遇到了一些问题。

1. Linux而非Win#

源码基于Linux，Linux和Win存在诸多差异，无法在Win上直接编译，需要修改很多函数和Makefile。

解决方案#

使用Linux系统

2. 顶点编号不可超过顶点总数#

在一些数据集中，顶点编号可能超过顶点总数，这会导致GridGraph出现段错误，所以有必要进行重编号。

解决方案#

顶点重编号
def remap_vertex_ids(input_file, output_file, mapping_file):
    """
    重编号图的顶点，保证编号从0开始且连续。


    参数:
    - input_file: 输入的边数据文件（每行由两个顶点 ID 构成，制表符分隔）。
    - output_file: 输出的重编号后边数据文件。
    - mapping_file: 输出的顶点映射表文件，记录原顶点ID与新ID的对应关系。
    """
    vertex_map = {}
    next_id = 0
    remapped_edges = []


    # 读取输入文件并重编号
    with open(input_file, "r") as f:
        for line in f:
            parts = line.strip().split('\t')
            if len(parts) == 2:
                source = int(parts[0])
                target = int(parts[1])


                # 给 source 分配新的编号
                if source not in vertex_map:
                    vertex_map[source] = next_id
                    next_id += 1
                new_source = vertex_map[source]


                # 给 target 分配新的编号
                if target not in vertex_map:
                    vertex_map[target] = next_id
                    next_id += 1
                new_target = vertex_map[target]


                remapped_edges.append(f"{new_source}\t{new_target}\n")


    # 写入重编号后的边文件
    with open(output_file, "w") as f:
        f.writelines(remapped_edges)


    # 写入映射表
    with open(mapping_file, "w") as f:
        for original, new_id in sorted(vertex_map.items(), key=lambda x: x[1]):
            f.write(f"{original} {new_id}\n")


    print(f"顶点总数：{len(vertex_map)}")
    print(f"已写入重编号边文件：{output_file}")
    print(f"已写入映射文件：{mapping_file}")


# 调用示例
# remap_vertex_ids(wiki_vote, wiki_vote + "_remapped.txt", wiki_vote + "_mapping.txt")

3. 二进制文件而非文本文件#

GridGraph默认使用二进制读取，但是Snap给出的数据集很多是.txt结尾的文本文件，有些还包括了注释，比如LiveJournal1。如果直接读取文本文件，会读取错误数据，可能导致段错误。

解决方案#

  1. 去掉文本文件内的注释行

  2. 使用脚本转换为二进制文件 注意：如果不能保证顶点编号都小于顶点总数，你应该先运行我的顶点重编号脚本。

    文本文件到二进制文件
    import struct
    

    def convert_txt_to_bin(txt_path, bin_path, edge_type=0):
        """
        将文本格式的边列表转换为二进制格式。
        :param txt_path: 输入的文本文件路径
        :param bin_path: 输出的二进制文件路径
        :param edge_type: 边的类型，0表示无权重边，1表示有权重边
        """
    

        with open(txt_path, 'r') as txt_file, open(bin_path, 'wb') as bin_file:
            for line in txt_file:
                parts = line.strip().split()
                if edge_type == 0 and len(parts) != 2:
                    continue  # 跳过不符合格式的行
                if edge_type == 1 and len(parts) != 3:
                    continue
    

                source = int(parts[0])
                target = int(parts[1])
    

                # 写入两个 VertexId（一般是 4 字节 int）
                bin_file.write(struct.pack('ii', source, target))
    

                if edge_type == 1:
                    weight = float(parts[2])
                    # 写入 Weight（float，4 字节）
                    bin_file.write(struct.pack('f', weight))
    

        print(f"转换完成，生成二进制文件：{bin_path}")
    

    # 举例
    # wiki_vote = "./Wiki-Vote.txt"
    # convert_txt_to_bin(wiki_vote, wiki_vote + ".bin")

4. 大小写敏感#

Linux对大小写敏感。所以Github给出的Processing要改为processing。

5. GraphSO的划分目录问题#

GraphSO要在GridGraph的基础上进行二次划分，但是源Repo没有提到目录问题…

运行GraphSO的划分时，要在GridGraph划分的目录下运行，即GraphSO的二次划分得到的结果会生成在你当前bash所在目录，如：

Terminal window
./bin/Preprocessing /data/LiveJournal 20 526.38 8

如果还不明白，我给出一个目录:

# GridGraph的划分结果
block-0-1
...
block-x-y


column
column_offset
row
row_offset
meta


# GraphSO同一路径下生成的二次划分
chunk-table-0
...
chunk-table-n

总而言之，GraphSO的划分结果输出目录下也要有GridGraph原本的划分结果，不然程序无法正常运行。

附录#

C++版本的数据集处理代码#

#include <iostream>
#include <fstream>
#include <unordered_map>
#include <vector>
#include <sstream>
#include <string>
#include <algorithm>


// 转换文本为二进制文件
void convert_txt_to_bin(const std::string& txt_path, const std::string& bin_path, int edge_type = 0) {
    std::ifstream txt_file(txt_path);
    std::ofstream bin_file(bin_path, std::ios::binary);


    if (!txt_file.is_open() || !bin_file.is_open()) {
        std::cerr << "文件无法打开" << std::endl;
        return;
    }


    std::string line;
    while (std::getline(txt_file, line)) {
        std::istringstream iss(line);
        int source, target;
        float weight = 0.0f;


        if (edge_type == 0) {
            if (!(iss >> source >> target)) continue;
            bin_file.write(reinterpret_cast<char*>(&source), sizeof(int));
            bin_file.write(reinterpret_cast<char*>(&target), sizeof(int));
        } else if (edge_type == 1) {
            if (!(iss >> source >> target >> weight)) continue;
            bin_file.write(reinterpret_cast<char*>(&source), sizeof(int));
            bin_file.write(reinterpret_cast<char*>(&target), sizeof(int));
            bin_file.write(reinterpret_cast<char*>(&weight), sizeof(float));
        }
    }


    std::cout << "转换完成，生成二进制文件: " << bin_path << std::endl;
}


// 重编号顶点 ID
void remap_vertex_ids(const std::string& input_file, const std::string& output_file, const std::string& mapping_file, bool write_remapped_edges = true) {
    std::ifstream infile(input_file);
    std::ofstream outfile;
    std::ofstream mapfile(mapping_file);


    if (!infile.is_open() || !mapfile.is_open()) {
        std::cerr << "文件无法打开" << std::endl;
        return;
    }


    if (write_remapped_edges) {
        outfile.open(output_file);
        if (!outfile.is_open()) {
            std::cerr << "边文件无法打开" << std::endl;
            return;
        }
    }


    std::unordered_map<int, int> vertex_map;
    int next_id = 0;
    std::string line;
    std::vector<std::pair<int, int>> remapped_edges;


    while (std::getline(infile, line)) {
        std::istringstream iss(line);
        int source, target;
        if (!(iss >> source >> target)) continue;


        if (vertex_map.find(source) == vertex_map.end()) {
            vertex_map[source] = next_id++;
        }
        if (vertex_map.find(target) == vertex_map.end()) {
            vertex_map[target] = next_id++;
        }


        remapped_edges.emplace_back(vertex_map[source], vertex_map[target]);
    }


    if (write_remapped_edges) {
        for (const auto& edge : remapped_edges) {
            outfile << edge.first << "\t" << edge.second << "\n";
        }
    }


    // 根据新 ID 排序
    std::vector<std::pair<int, int>> sorted_map(vertex_map.begin(), vertex_map.end());
    std::sort(sorted_map.begin(), sorted_map.end(), [](const auto& a, const auto& b) {
        return a.second < b.second;
    });


    for (const auto& pair : sorted_map) {
        mapfile << pair.first << " " << pair.second << "\n";
    }


    std::cout << "顶点总数: " << vertex_map.size() << std::endl;
    if (write_remapped_edges) std::cout << "已写入重编号边文件: " << output_file << std::endl;
    std::cout << "已写入映射文件: " << mapping_file << std::endl;
}


int main(int argc, char* argv[]) {
    if (argc < 5) {
        std::cerr << "用法: " << argv[0] << " <text_input> <bin_output> <edge_type (0 or 1)> <remap (0 or 1)>" << std::endl;
        return 1;
    }


    std::string text_input = argv[1];
    std::string bin_output = argv[2];
    int edge_type = std::stoi(argv[3]);
    bool remap = std::stoi(argv[4]) != 0;


    std::string remap_output = text_input + ".remapped.txt";
    std::string map_output = text_input + ".mapping.txt";


    if (remap) {
        remap_vertex_ids(text_input, remap_output, map_output, true);
        convert_txt_to_bin(remap_output, bin_output, edge_type);
    } else {
        convert_txt_to_bin(text_input, bin_output, edge_type);
    }


    return 0;
}

你可以通过以下命令编译:

编译
# 注意c++标准, c++14以上
g++ -std=c++14 -o graph_converter graph_converter.cpp

运行编译后的文件:

运行
# 参数: 输入文件路径 输出文件路径 是否为有权图 是否输出编号重映射表
./graph_converter input.txt output.bin 0 0
GrapSO复现记录
https://www.raintrap341.com/posts/grapso复现记录/
作者
RainTrap341
发布于
2025-05-15
许可协议
CC BY-NC-SA 4.0
增强Fuwari中添加的系统栏
© 2025 RainTrap341. All Rights Reserved. / RSS / Sitemap
Powered by Astro & Fuwari