Vertices with different properties in boost graph library

Question

I have to write code that can parse a file like this:

digraph G {
0[label="person" name="James Cameron"];
1[label="film" title="Avatar 2" year="2022"];
0->1 [label="directed"];
}

Each vertex has label necessarily, but also it may have an unknown number of properties. Moreover, these properties can be own for each vertex. With edges everything is simple - only one label. I would like not to write my own parser, but to use read_graphviz. Tell me, please, how can this be done? It would be perfect if the code worked with such bundled property:

struct Vertex {
    std::string label;
    std::map<std::string, std::string> attributes;
};

I wrote a code that parses this:

digraph G {
0[label="person" attributes="name=James_Cameron"];
1[label="film" attributes="title=Avatar_2;year=2022"];
0->1 [label="directed"];
}

But this format looks creepy. My code:

#include <iostream>
#include <vector>
#include <map>

#include <boost/graph/graphviz.hpp>
#include <boost/graph/adjacency_list.hpp>

struct Vertex {
    std::string raw_attrs;
    std::string label;
    std::map<std::string, std::string> attributes;
};

struct Edge {
    std::string label;
};

typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::bidirectionalS, Vertex, Edge> Graph;

int main(int argc, char** argv) {
    Graph graph;
    boost::dynamic_properties dp(boost::ignore_other_properties);
    dp.property("label", boost::get(&Vertex::label, graph));
    dp.property("attributes", boost::get(&Vertex::raw_attrs, graph));
    dp.property("label", boost::get(&Edge::label, graph));
    std::ifstream f("file.txt");
    boost::read_graphviz(f, graph, dp);

    // transform raw_attrs to attributes
}

Answer 1

I promised to find the time to demonstrate the support for dynamic attributes in BGL read_graphviz.

I'll do that by implementing a roundtripping

int main() {
    std::istringstream iss(R"(digraph G {
            0[label="person" name="James Cameron"];
            1[label="film" title="Avatar 2" year="2022"];
            0->1 [label="directed"];
        })");

    auto g = do_read(iss);
    do_write(std::cout, g);
}

Note that it's a logical roundtrip. It doesn't promise to preserve formatting or node id numbering.

0. Preliminaries

Some useful definitions:

struct Vertex {
    int                                original_id;
    std::map<std::string, std::string> attributes;
};

struct Edge {
    std::string relation;
};

using G = boost::adjacency_list<boost::vecS, boost::vecS, boost::directedS, Vertex, Edge>;
using V = G::vertex_descriptor;

1. Writing The Graph

The simpler part first. We use the overload that takes a writer interface. We can hack it in few lines:

void do_write(std::ostream& os, G& g) {
    auto vw = boost::attributes_writer(get(&Vertex::attributes, g));
    auto ew = boost::label_writer{get(&Edge::relation, g)};
    write_graphviz(os, g, vw, ew);
}

We supply the vertex writer as the attributes writer, and write the one edge property (relation) as the label.

2. Reading The Graph

You can pass a generator function to the constructor of dynamic_properties. This will be invoked when a new attribute is found.

G do_read(std::istream& is) {
    G    g;
    // ...
    boost::dynamic_properties dp(newattr);
    dp.property("label", get(&Edge::relation, g));

    dp.property("node_id", get(&Vertex::original_id, g));
    read_graphviz(is, g, dp);

    return g;
}

Let's use a lambda to define the newattr generator function:

auto attrs   = get(&Vertex::attributes, g);
auto newattr = [=](std::string const& name, auto&& descr, auto&&) -> Ptr {
    if (typeid(V) == descr.type()) {
        return make_dyn(boost::make_function_property_map<V>(
            [=](V v) -> std::string& { return attrs[v][name]; }));
    } else
        return {};
};

Where make_dyn is a simple helper to wrap a concrete property map (like our function property map) in a shared pointer to a dynamic property map:

using Ptr = boost::shared_ptr<boost::dynamic_property_map>;

auto make_dyn = [](auto m) -> Ptr {
    using DM = boost::detail::dynamic_property_map_adaptor<decltype(m)>;
    auto sp = boost::make_shared<DM>(m);
    return boost::static_pointer_cast<boost::dynamic_property_map>(sp);
};

In production code you would probably make this a free function, which would be more re-usable and slightly more readable by getting rid of the decltype expression.

Full Demo

Live On Coliru

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/graphviz.hpp>
#include <boost/property_map/function_property_map.hpp>

struct Vertex {
    int                                original_id;
    std::map<std::string, std::string> attributes;
};

struct Edge {
    std::string relation;
};

using G = boost::adjacency_list<boost::vecS, boost::vecS, boost::directedS, Vertex, Edge>;
using V = G::vertex_descriptor;

void do_write(std::ostream& os, G& g) {
    auto vw = boost::attributes_writer(get(&Vertex::attributes, g));
    auto ew = boost::label_writer{get(&Edge::relation, g)};
    write_graphviz(os, g, vw, ew);
}

G do_read(std::istream& is) {
    using Ptr = boost::shared_ptr<boost::dynamic_property_map>;

    auto make_dyn = [](auto m) -> Ptr {
        using DM = boost::detail::dynamic_property_map_adaptor<decltype(m)>;
        auto sp = boost::make_shared<DM>(m);
        return boost::static_pointer_cast<boost::dynamic_property_map>(sp);
    };

    G    g;
    auto attrs   = get(&Vertex::attributes, g);
    auto newattr = [=](std::string const& name, auto&& descr, auto&&) -> Ptr {
        if (typeid(V) == descr.type()) {
            return make_dyn(boost::make_function_property_map<V>(
                [=](V v) -> std::string& { return attrs[v][name]; }));
        } else
            return {};
    };

    boost::dynamic_properties dp(newattr);
    dp.property("label", get(&Edge::relation, g));

    dp.property("node_id", get(&Vertex::original_id, g));
    read_graphviz(is, g, dp);

    return g;
}

int main() {
    std::istringstream iss(R"(digraph G {
            0[label="person" name="James Cameron"];
            1[label="film" title="Avatar 2" year="2022"];
            0->1 [label="directed"];
        })");

    auto g = do_read(iss);
    do_write(std::cout, g);
}

Prints

g++ -std=c++20 -O2 -pedantic -pthread main.cpp -lboost_graph && ./a.out
digraph G {
0[label=person, name="James Cameron"];
1[label=film, title="Avatar 2", year=2022];
0->1 [label=directed];
}