Boost Graphs - 确保确定性的图行为

Question

我正在根据 JSON 文件中的数据创建图形，并且我希望这样当我遍历图形的边和顶点（例如 in_edges()、vertices() 或 topological_sort() ）时，它是准确的无论插入顺序如何，顺序都相同。换句话说，即使我打乱 JSON 的顺序，也会生成相同的图表。

最好的方法是什么？我目前使用 VecS 作为我的顶点和边类型 - 切换到 SetS 可以实现这一点吗？

我目前正在考虑使用围绕 VertexDescriptors 和 EdgeDescriptors 的包装器结构，以及围绕升压图的包装器类，以便我可以在内部迭代该图，并返回 Vertex/EdgeDescriptor 包装器结构的排序顺序。

Answer 1

您并没有真正展示任何示例，所以让我想象一个示例，以及我可能如何解析这些示例。

让以下 JSON 文档表示相同的图：

auto doc1 = json::parse(
    R"( {
  "vertices": [
    {"name": "Cinderella", "id": 0},
    {"name": "Luke Skywalker", "id": 1},
    {"name": "Aurora", "id": 2},
    {"name": "Darth Vader", "id": 3},
    {"name": "Belle", "id": 4},
    {"name": "Han Solo", "id": 5},
    {"name": "Elsa", "id": 6},
    {"name": "Obi-Wan Kenobi", "id": 7},
    {"name": "Rumpelstiltskin", "id": 8},
    {"name": "Princess Leia", "id": 9}
  ],
  "edges": [
    [0, 1], [0, 5],
    [1, 0], [1, 2],
    [2, 3], [2, 7],
    [3, 4], [3, 8],
    [4, 5], [4, 9],
    [5, 2], [5, 6],
    [6, 3], [6, 7],
    [7, 4], [7, 8],
    [8, 1], [8, 9],
    [9, 0], [9, 6]
  ]
})");

auto doc2 = json::parse(
    R"( {
  "edges": [
    [2, 7], [8, 9], [6, 3], [1, 0], [4, 5], [9, 6],
    [4, 9], [3, 8], [7, 8], [0, 1], [3, 4], [5, 6], [7, 4],
    [1, 2], [5, 2], [9, 0], [2, 3], [6, 7], [0, 5], [8, 1] ],
  "vertices": [
    {"id": 9, "name": "Princess L\u0065ia"},
    {"id": 8, "name": "Rump\u0065lstiltskin"},
    {"id": 5, "name": "Han Solo"},
    {"name": "Luk\u0065 Skywalker", "id": 1},
    {"name": "Bell\u0065", "id": 4},
    {"id": 2, "name": "Aurora"},
    {"id": 7, "name": "Obi-Wan K\u0065nobi"},
    {"id": 0, "name": "C\u0069nderella"},
    {"id": 3, "name": "Darth V\u0061der"},
    {"id": 6, "name": "Elsa"}
  ]
})");

我建议使用一个辅助函数来从这些文档构建等效图表：

auto BuildGraph(json::value const& doc) {
    struct VertexProperty {
        std::string name;
        auto operator<=>(VertexProperty const&) const = default;
    };
    boost::adjacency_list<boost::vecS, boost::vecS, boost::directedS, VertexProperty> g;

    // tmp datastructures
    using Edge = std::tuple<int64_t, int64_t>;

    for (auto [s, t] : value_to<std::set<Edge>>(doc.at("edges")))
        add_edge(s, t, g);

    for (auto& v : doc.at("vertices").as_array()) {
        auto id = v.at("id").as_int64();
        g[id].name = v.at("name").as_string();
    }
    return g;
}

目前，我假设了简单的顶点 ID

[0, numvertices)

。在将边添加到图表之前，请注意边是如何在

set<>

中排序的。

这是构建邻接列表后显示等效性的组合列表：

住在Coliru

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

auto doc1 = json::parse(
    R"( {
  "vertices": [
    {"name": "Cinderella", "id": 0},
    {"name": "Luke Skywalker", "id": 1},
    {"name": "Aurora", "id": 2},
    {"name": "Darth Vader", "id": 3},
    {"name": "Belle", "id": 4},
    {"name": "Han Solo", "id": 5},
    {"name": "Elsa", "id": 6},
    {"name": "Obi-Wan Kenobi", "id": 7},
    {"name": "Rumpelstiltskin", "id": 8},
    {"name": "Princess Leia", "id": 9}
  ],
  "edges": [
    [0, 1], [0, 5],
    [1, 0], [1, 2],
    [2, 3], [2, 7],
    [3, 4], [3, 8],
    [4, 5], [4, 9],
    [5, 2], [5, 6],
    [6, 3], [6, 7],
    [7, 4], [7, 8],
    [8, 1], [8, 9],
    [9, 0], [9, 6]
  ]
})");

auto doc2 = json::parse(
    R"( {
  "edges": [
    [2, 7], [8, 9], [6, 3], [1, 0], [4, 5], [9, 6],
    [4, 9], [3, 8], [7, 8], [0, 1], [3, 4], [5, 6], [7, 4],
    [1, 2], [5, 2], [9, 0], [2, 3], [6, 7], [0, 5], [8, 1] ],
  "vertices": [
    {"id": 9, "name": "Princess L\u0065ia"},
    {"id": 8, "name": "Rump\u0065lstiltskin"},
    {"id": 5, "name": "Han Solo"},
    {"name": "Luk\u0065 Skywalker", "id": 1},
    {"name": "Bell\u0065", "id": 4},
    {"id": 2, "name": "Aurora"},
    {"id": 7, "name": "Obi-Wan K\u0065nobi"},
    {"id": 0, "name": "C\u0069nderella"},
    {"id": 3, "name": "Darth V\u0061der"},
    {"id": 6, "name": "Elsa"}
  ]
})");

#include <boost/graph/adjacency_list.hpp>
auto BuildGraph(json::value const& doc) {
    struct VertexProperty {
        std::string name;
        auto operator<=>(VertexProperty const&) const = default;
    };
    boost::adjacency_list<boost::vecS, boost::vecS, boost::directedS, VertexProperty> g;

    // tmp datastructures
    using Edge = std::tuple<int64_t, int64_t>;

    for (auto [s, t] : value_to<std::set<Edge>>(doc.at("edges")))
        add_edge(s, t, g);

    for (auto& v : doc.at("vertices").as_array()) {
        auto id = v.at("id").as_int64();
        g[id].name = v.at("name").as_string();
    }
    return g;
}

// For demo output
#include <boost/graph/graph_utility.hpp>
#include <boost/lexical_cast.hpp>
#include <boost/property_map/function_property_map.hpp>
#include <iomanip>

template <typename... Ts>
static std::ostream& operator<<(std::ostream& os, boost::adjacency_list<Ts...> const& g) {
    using G = boost::adjacency_list<Ts...>;
    using V = G::vertex_descriptor;
    auto n  = boost::make_function_property_map<V>([&g](V v) { return quoted(g[v].name); });
    print_graph(g, n, os << "\n");
    return os;
}

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

    auto g1 = BuildGraph(doc1);
    auto g2 = BuildGraph(doc2);

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

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

打印

{"vertices":[{"name":"Cinderella","id":0},{"name":"Luke Skywalker","id":1},{"name":"Aurora","id":2},{"name":"Darth Vader","id":3},{"name":"Belle","id":4},{"name":"Han Solo","id":5},{"name":"Elsa","id":6},{"name":"Obi-Wan Kenobi","id":7},{"name":"Rumpelstiltskin","id":8},{"name":"Princess Leia","id":9}],"edges":[[0,1],[0,5],[1,0],[1,2],[2,3],[2,7],[3,4],[3,8],[4,5],[4,9],[5,2],[5,6],[6,3],[6,7],[7,4],[7,8],[8,1],[8,9],[9,0],[9,6]]}

{"edges":[[2,7],[8,9],[6,3],[1,0],[4,5],[9,6],[4,9],[3,8],[7,8],[0,1],[3,4],[5,6],[7,4],[1,2],[5,2],[9,0],[2,3],[6,7],[0,5],[8,1]],"vertices":[{"id":9,"name":"Princess Leia"},{"id":8,"name":"Rumpelstiltskin"},{"id":5,"name":"Han Solo"},{"name":"Luke Skywalker","id":1},{"name":"Belle","id":4},{"id":2,"name":"Aurora"},{"id":7,"name":"Obi-Wan Kenobi"},{"id":0,"name":"Cinderella"},{"id":3,"name":"Darth Vader"},{"id":6,"name":"Elsa"}]}

DIFFERENT

"Cinderella" --> "Luke Skywalker" "Han Solo" 
"Luke Skywalker" --> "Cinderella" "Aurora" 
"Aurora" --> "Darth Vader" "Obi-Wan Kenobi" 
"Darth Vader" --> "Belle" "Rumpelstiltskin" 
"Belle" --> "Han Solo" "Princess Leia" 
"Han Solo" --> "Aurora" "Elsa" 
"Elsa" --> "Darth Vader" "Obi-Wan Kenobi" 
"Obi-Wan Kenobi" --> "Belle" "Rumpelstiltskin" 
"Rumpelstiltskin" --> "Luke Skywalker" "Princess Leia" 
"Princess Leia" --> "Cinderella" "Elsa" 



"Cinderella" --> "Luke Skywalker" "Han Solo" 
"Luke Skywalker" --> "Cinderella" "Aurora" 
"Aurora" --> "Darth Vader" "Obi-Wan Kenobi" 
"Darth Vader" --> "Belle" "Rumpelstiltskin" 
"Belle" --> "Han Solo" "Princess Leia" 
"Han Solo" --> "Aurora" "Elsa" 
"Elsa" --> "Darth Vader" "Obi-Wan Kenobi" 
"Obi-Wan Kenobi" --> "Belle" "Rumpelstiltskin" 
"Rumpelstiltskin" --> "Luke Skywalker" "Princess Leia" 
"Princess Leia" --> "Cinderella" "Elsa" 


EQUAL