Boost Graphs - 来自 JSON 的确定性图行为

Question

我正在从 JSON 数组文件创建图形，我希望这样当我遍历图形的边和顶点（例如 in_edges()、vertices() 或 topological_sort() ）时，它的位置完全相同顺序与插入顺序无关。换句话说，即使我打乱 JSON 的顺序，也会生成相同的图表。

JSON 可能如下所示：

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

举个例子，如果插入顺序是示例 JSON，10 -> 1 -> 99 -> 2 -> 85，那么 10 的父级将显示为 1 2 85。但是，如果插入顺序是85 -> 2 -> 1 -> 99 -> 10，那么 10 的父母会出现 85 2 1。这是我想避免的。

现在，我正在考虑在 boost 图周围添加一个包装器，并在调用 getParent() 时对顶点进行排序，但我想知道是否有更简单的方法可以通过原生 boost 实现此目的。

另一种可能性是预先对 JSON 进行排序，但我想避免这种时间复杂性。

Answer 1

我想避免时间复杂度

根据热力学定律，这是无法避免的。您明确声明您想要标准化/规范化的结果，这意味着您必须花费精力......标准化数据，无论它是在预处理还是后处理中完成。

记住 Boost Graph 已经是确定性的。您想要的是以标准化方式处理输入。让我们首先重现该问题，给出问题中的两个 JSON 文档

doc1

和

doc2

：

#include <boost/json.hpp>
namespace json = boost::json;

auto opts = json::parse_options{.allow_trailing_commas=true};
auto doc1 = json::parse(
    R"( [
    { "ID": 10, "PARENTS": [2,  1, 85] },
    { "ID": 1,  "PARENTS": []   },
    { "ID": 99, "PARENTS": [2]  },
    { "ID": 2,  "PARENTS": []   },
    { "ID": 85, "PARENTS": [99] },
])", {}, opts);

auto doc2 = json::parse(
    R"([
     { "PARENTS": [99]       , "ID": 85  },
     { "PARENTS": []         , "ID": 2   },
     { "PARENTS": []         , "ID": 1   },
     { "PARENTS": [2]        , "ID": 99  },
     { "PARENTS": [2,  1, 85], "ID": 10  },
])", {}, opts);

如果我们 1:1 将这些翻译为

boost::adjacency_list<>

:

#include <boost/graph/adjacency_list.hpp>
using Id = int64_t;

namespace Builder {
    struct Node {
        using Parents = std::vector<int64_t>;
        Id      id;
        Parents parents;

        friend Node tag_invoke(json::value_to_tag<Node>, json::value const& j) {
            return {j.at("ID").as_int64(), value_to<Parents>(j.at("PARENTS"))};
        }
    };

    auto Read(json::value const& doc) {
        boost::adjacency_list<boost::vecS, boost::listS, boost::directedS, Id> g;

        for (auto& [id, parents] : value_to<std::vector<Node>>(doc))
            for (auto parent : parents)
                add_edge(parent, id, g);

        return g;
    }
} // namespace Builder

我们确实看到了预期的不同图表：Live On Coliru

int main() {
    std::cout << doc1 << "\n";
    std::cout << doc2 << "\n";
    std::cout << (doc1 == doc2 ? "EQUAL" : "DIFFERENT") << "\n";

    auto g1 = Builder::Read(doc1);
    auto g2 = Builder::Read(doc2);

    std::cout << g1 << "\n";
    std::cout << g2 << "\n";

    auto s1 = boost::lexical_cast<std::string>(g1);
    auto s2 = boost::lexical_cast<std::string>(g2);
    std::cout << (s1 == s2 ? "EQUAL" : "DIFFERENT") << "\n";
}

印刷

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

85 --> 10 
99 --> 85 
2 --> 99 10 
10 --> 
1 --> 10 

DIFFERENT

预处理节点

在这种情况下，我们可以非常简单地通过替换来按照我们选择的规范顺序插入节点：

for (auto& [id, parents] : value_to<std::vector<Node>>(doc))

与

for (auto& [id, parents] : value_to<std::set<Node>>(doc))

为了简单起见，我们使用基于每个节点属性的默认排序：

struct Node { /*...*/
    auto operator<=>(Node const&) const = default;

现在我们得到 在 Coliru 上直播

// ...
10 --> 
2 --> 10 99 
1 --> 10 
85 --> 10 
99 --> 85 

EQUAL

奖励：邻接怎么样

你没问，但是家长的命令呢？

auto doc3 = json::parse(
    R"([
     { "PARENTS": [99]       , "ID": 85  },
     { "PARENTS": []         , "ID": 2   },
     { "PARENTS": []         , "ID": 1   },
     { "PARENTS": [2]        , "ID": 99  },
     { "PARENTS": [85, 2,  1], "ID": 10  },
])", {}, opts);

现在给

住在Coliru

g2 EQUAL
g3 DIFFERENT

在预处理中再次将邻接强制到有序容器中（Live）：

 using Parents = std::multiset<int64_t>; // g3 EQUAL

要禁止重复边缘，请使用

std::set

在具有

multisetS

的图形模型中，Live 做得还不够，因为它对描述符进行排序。