rucdatascience / classcode2023 Goto Github PK

需要补全代码的位置:
1. Hop/HBPLL_TODO.h#HB_thread_function_HBDIJ_Qhandle 函数中 while 循环内TODO部分
2. Hop/HBPLL_TODO.h#HB_extract_distance_v1 函数内TODO部分
3. Hop/HBPLL_TODO.h#HB_extract_path_v1 函数内TODO部分

除Hop文件夹外, 其余文件均为辅助实现的部分代码, 可以不重点关注
下面对Hop文件夹内文件及内部函数做简要释义

Hop/test_HBPLL.h
    测试函数, 整个算法的调用入口在此, 开头的注释部注明了如何调用函数, 以及编译运行的参数
    根据参数随机生成图,执行HBPLL算法并执行正确性检查
    其中含有多个控制参数便于debug测试,请详细读代码

Hop/HBPLL_main.h
    HBPLL的实现文件
    --HB_v1_sort_labels_thread 和 HB_v1_sort_labels：在生成索引之后, 根据节点大小并行地对索引进行排序
    --HBPLL_v1: HBPLL实现函数, 分为初始化, 索引生成, 索引整理三个部分, 需要补全的是索引生成部分.
                在索引生成部分中, 会并行地调用 HB_thread_function_HBDIJ_Qhandle 函数, 从不同的顶点出发执行Hop-Bounded Dijkstra.

Hop/HBPLL_TODO.h
    需要补全代码的文件, 包含三个需要补全的函数, 提交代码时仅提交该文件即可
    --HBPLL_v1_node: HBDIJ遍历过程中使用的数据结构, 保存每个节点的相关信息
    --HB_thread_function_HBDIJ_Qhandle: 需要补全的HBDIJ函数, 对应的伪代码参考阅读材料
    --HB_extract_distance_v1: 最短距离查询实现, 利用生成的索引进行最短距离查询
    --HB_extract_path_v1: 最短路径查询实现, 利用生成的索引进行最短路径查询

Hop/HBPLL_two_hop_labels.h
    --two_hop_label_v1: 索引结构
    --two_hop_case_info: 存储HBPLL相关参数和用时用量信息,主要用于传参; 同时存储生成的索引,因此想要查看生成的索引只需要调用print_L函数即可

Hop/HBPLL_check_correctness.h
    检查生成的索引正确性的函数, 会被 test_HBPLL 调用