基于Boost Graph实现JSON生成图的确定性遍历行为

核心需求 #

从JSON数组生成图时，要求遍历图的边（如in_edges()）、顶点（如vertices()）或拓扑排序（topological_sort()）的顺序完全不受JSON插入顺序影响——即使打乱JSON节点的顺序，生成的图遍历行为也完全一致。例如避免因JSON插入顺序不同，导致节点10的父节点遍历顺序在[1,2,85]和[85,2,1]之间变化。

示例JSON #

[
    {
        "ID": 10,
        "PARENTS": [2, 1, 85]
    },
    {
        "ID": 1,
        "PARENTS": []
    },
    {
        "ID": 99,
        "PARENTS": [2]
    },
    {
        "ID": 2,
        "PARENTS": []
    }, 
    {
        "ID": 85,
        "PARENTS": [99]
    }
]

Boost Graph 原生解决方案 #

Boost Graph库允许通过选择有序容器类型作为顶点/边的存储模板参数，直接实现固定顺序的遍历，无需额外封装或预排序JSON：

1. 选择有序容器模板参数 #

Boost提供了ordered_setS和ordered_multisetS两种有序容器选择器，底层基于红黑树实现，插入时自动按键排序，遍历顺序固定：

• ordered_setS：用于顶点容器，保证vertices()遍历顶点时按ID有序排列
• ordered_multisetS：用于边容器，保证in_edges()/out_edges()遍历边时按关联顶点的ID有序排列

2. 代码示例 #

#include <boost/graph/adjacency_list.hpp>

// 定义顶点属性，存储节点ID
struct VertexProps {
    int id;
};

// 定义有序图类型：双向图+有序顶点/边容器
using OrderedGraph = boost::adjacency_list<
    boost::ordered_multisetS,  // 出边容器：有序存储，保证遍历顺序固定
    boost::ordered_setS,        // 顶点容器：有序存储，vertices()按ID排序
    boost::bidirectionalS,      // 双向图，支持in_edges()查询入边（父节点）
    VertexProps                 // 顶点属性结构
>;

3. 关键优势 #

• 无需预排序JSON：插入时增量排序，时间复杂度为O(log n) per 顶点/边插入，比预排序整个JSON的O(n log n)更高效，尤其适合大型数据集
• 原生支持，无需额外封装：直接利用Boost Graph的容器机制，代码简洁可靠
• 遍历顺序完全固定：无论JSON插入顺序如何，vertices()、in_edges()等操作的结果顺序始终一致（默认按ID升序）

4. 自定义排序规则 #

如果需要按非默认顺序（如ID降序）遍历，可自定义比较器并传递给有序容器：

// 自定义降序比较器
struct DescendingIdCompare {
    template <typename Vertex>
    bool operator()(const Vertex& a, const Vertex& b) const {
        return get(&VertexProps::id, a) > get(&VertexProps::id, b);
    }
};

// 使用自定义比较器的图类型
using DescOrderedGraph = boost::adjacency_list<
    boost::ordered_multisetS<DescendingIdCompare>,
    boost::ordered_setS<DescendingIdCompare>,
    boost::bidirectionalS,
    VertexProps
>;

5. 拓扑排序的一致性 #

使用有序容器后，topological_sort()的结果也会保持一致——因为顶点和边的遍历顺序固定，算法的执行路径不会因插入顺序而改变，最终生成的拓扑序列完全由图的结构决定。

内容的提问来源于stack exchange，提问作者terrabyte