Boost Graphs - ensuring deterministic graph behaviour

Question

I'm creating graphs from data from a JSON file and I'd like it so that when I traverse through both edges and vertices (e.g. in_edges(), vertices() or topological_sort() ) of the graph, it's in the exact same order regardless of the insertion order. In other words, to produce the same graph even if I shuffle the order of the JSON.

What would be the best way to do this? I'm currently using VecS as my Vertex and Edge types - would switching to SetS achieve this?

I'm currently thinking about using a wrapper struct around VertexDescriptors and EdgeDescriptors and also a wrapper class around a boost graph so that I can iterate over the graph internally, and return a sorted ordering of the Vertex/EdgeDescriptor wrapper struct instead.

Answer 1

You don't really show any examples, so let me dream up an example, and how I'd probably parse these.

Let the following JSON documents represent the same graphs:

{ "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]
    ]
}

And then flipping all possible properties at random and re-ordering the array elements at random, reformatting strings to contain escapes etc.:

{ "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"}
    ]
}

I'd propose a helper function to build equivalent graphs from those documents:

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

    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 now, I've assumed simple vertex ids [0, numvertices). Note how the edges are sorted in a set<> before adding them to the graph.

Here's the combined listing showing equivalence after building the adjacency list:

Live On 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; };
    boost::adjacency_list<boost::vecS, boost::vecS, boost::directedS, VertexProperty> g;

    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);
    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";
}

Printing

{"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