Vertices with different properties in boost graph library-CodePudding

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
}

CodePudding user response：

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

Again, 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];
}

CodePudding user response：

Writing a parser is not difficult. Here is the code for an application that parses the vertices. I hope you do not think it is creepy.

#include <string>
#include <fstream>
#include <sstream>
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>

class cVertex
{
    int userIndex;
    std::string label;
    std::map<std::string, std::string> attributes;
    static std::vector<cVertex> myVertex;

public:
    void read(const std::string &fname);
    std::string textVertexList();

private:
    void parseVertexLine(const std::string &line);
};

std::vector<cVertex> cVertex::myVertex;

void cVertex::read(const std::string &fname)
{
    std::ifstream ifs(fname);
    if (!ifs.is_open())
    {
        std::cout << "Cannot open file\n";
        exit(1);
    }
    std::string line;
    getline(ifs, line);
    while (getline(ifs, line))
    {
        if (line.find("->") != -1)
            break;
        parseVertexLine(line);
    }
}

std::string cVertex::textVertexList()
{
    std::stringstream ss;
    for (auto &v : myVertex)
    {
        ss << "\nvertex " << v.userIndex
           << " label is " << v.label << "\n";
        for (auto &a : v.attributes)
        {
            ss << a.first << " | " << a.second << "\n";
        }
    }
    return ss.str();
}

void cVertex::parseVertexLine(const std::string &line)
{
    cVertex v;
    v.userIndex = atoi(line.c_str());
    int p = line.find("label");
    int q = line.find("\"", p   7);
    v.label = line.substr(p   7, q - p - 7);

    while (1)
    {
        std::pair< std::string,std::string > ap;
        p = line.find("=", q);
        if (p == -1)
            break;
        ap.first = line.substr(q   2, p - q - 2);
        p = line.find("\"", p);
        q = line.find("\"", p   1);
        ap.second = line.substr(p   1, q - p - 1);
        v.attributes.insert(ap);
        int dbg = 0;
    }

    myVertex.push_back(v);
}

main()
{
    cVertex theVertex;
    theVertex.read("data.txt");
    std::cout << theVertex.textVertexList();
    return 0;
}