How to copy vertex properties of boost graph which contains a graph itself?

Question

I have a boost graph with custom properties. I want to make a copy of it. I tried it by following way.

using BGType = boost::adjacency_list<boost::vecS, boost::vecS, boost::bidirectionalS,
                                     // Vertex Properties...
                                     vertexProps,
                                     // Edge Propereties...
                                     edgeProps,
                                     // Graph Properties
                                     graphProps>;

vertexProps.h

class vertexProps {
   public:
    explicit vertexProps(const std::string *moduleName = nullptr, const std::string *name = nullptr,
                            long refPtr = 0 )
     : _refPtr(refPtr),
    {
        _moduleName = moduleName ? *moduleName : "";
        _name = name ? *name : "";
    };
   std::string _moduleName;
   std::string _name;
   BGType *_subGraph = nullptr;
   BGType *_graph = nullptr;

struct CustomVertexCopy {
    BGType const &g1;
    BGType &g2;
    void operator()(BGType::vertex_descriptor v1, BGType::vertex_descriptor v2) const
    {
        schVertexProps const &p1 = g1[v1];
        schVertexProps &p2 = g2[v2];
        p2._subGraph = p1._subGraph;
        p2._graph = p1._graph;
        p2._moduleName = p1._moduleName;
        p2._name = p1._name;
    }
};

edgeProps.h

class edgeProps {
   public:
    explicit edgeProps(std::string name = "")
        : _name(name){};
    std::string _name;
};

struct CustomEdgeCopy {
    BGType const &g1;
    BGType &g2;

    void operator()(BGType::edge_descriptor e1, BGType::edge_descriptor e2) const { g2[e2]._name = g1[e1]._name; }
};

someFunction.cpp

OnClick(BGType* bgNew)
{
   // some code
  BGType* oldBg = new BGType;
  boost::copy_graph(
                  *bgNew, *oldBg,
                  boost::vertex_copy(CustomVertexCopy{*bgNew, *oldBg}).edge_copy(CustomEdgeCopy{*bgNew, *oldBg}));
  boost::get_property(*oldBg) = boost::get_property(*bgNew);
  // Copying graph properties
  DeepCopyOfBG(bgNew, oldBg);
}

void someFunction::DeepCopyOfBG(BGType* bGraph, BGType* oldBg)
{
    // Iterate through the source map and copy its contents
    for (const auto& entry : (*bGraph)[boost::graph_bundle]._modInfo) {
        const std::string& key = entry.first;
        const auto& value = entry.second;

        // Create a deep copy of value (a tuple containing vectors of schPinInfo)
        std::tuple<std::vector<schPinInfo*>, std::vector<schPinInfo*>, std::vector<schPinInfo*>> deepCopyValue = value;

        // Add the deep copy to the target map
        (*oldBg)[boost::graph_bundle]._modInfo[key] = deepCopyValue;
    }
    // some more properties.
}

Above way working fine. But it has 1 issue. Vertex property has 1 field which itself is a boost graph.

p2._subGraph = p1._subGraph;

And above line merely copying pointers. So in old boost graph, I am getting new boost graph's sub graph which I dont want. So how to deep copy this _subGraph field ?

Answer 1

Vertex property has 1 field which itself is a boost graph

It really doesn't. As you noted yourself, it contains pointers to graphs. That's just not the same thing.

And above line merely copying pointers. So in old boost graph, I am getting new boost graph's sub graph which I dont want. So how to deep copy this _subGraph field ?

I suspect you do want it, because copying graphs for every vertex is expensive. So unless you are using tiny graphs, I'd suggest embracing the indirection by using shared_ptr<BGType const> which also solves the lifetime problems (your code almost inevitably suffers from memory leaks as it is now).

Side note:

    p2._graph = p1._graph;

looks suspect too. Should it be p2._graph = &g2;?

Solution 1

If you want full copies, the simplest way would be to not use pointers, so the line

p2._subGraph = p1._subGraph;

actually copies the object.

Solution 2

You can obviously spell it out, introducing fresh opportunities for memory leaks by using raw pointers:

p2._subGraph = new BTType(*p1._subGraph);

Since you're still doing complicated dances to copy the graph in other spots, you might need to repeat that here. I suggest making a function that does it:

p2._subGraph = my_graph_copy_function(p1._subGraph);

DEMO

I'm going to supply a demo - as customary - but I'm going to base it on my earlier suggestions that show full value-semantics avoiding all the unnecessary complication of copying the graph in the first place.

Now, because there's recursion here (graphs have nodes which contain graphs which contain nodes which ... etc), we have to use some kind of dynamic allocation. I chose a "value_ptr" which is basically a unique_ptr that copies by deep-copy:

struct BGType; // forward
using SubGraph = value_ptr<BGType>;

struct vertexProps {
    std::string _moduleName;
    std::string _name;
    long        _refPtr;
    SubGraph    _subGraph;
};

Now the default copy assignment will do what you want, without risk of memory leaks, and without writing over-complicated code.

Because BGType needs to be forward declared here, we have to define it as a struct - which we can do by inheriting:

using BGTypeImpl = boost::adjacency_list<            //
    boost::vecS, boost::vecS, boost::bidirectionalS, //
    vertexProps, edgeProps, graphProps>;

struct BGType : BGTypeImpl {
    using BGTypeImpl::BGTypeImpl;
    using BGTypeImpl::operator=;
};

Now with main like:

int main() {
    BGType g1 = make_graph();
    BGType g2;
    g2 = g1; // FULL COPY

    std::cout << "g2:\n" << g2 << "\n";
    std::cout << "address of subgraph in g1: " << g1[2]._subGraph.address() << "\n";
    std::cout << "address of subgraph in g2: " << g2[2]._subGraph.address() << "\n";
}

We can have the output

g2:
digraph G {
    label=name;
    0 [moduleName=Hello, name=world, ref=111, subGraph="(none)"];
    1 [moduleName=Goodbye, name=moon, ref=222, subGraph="(none)"];
    2 [moduleName=Greetings, name=Cosmos, ref=333,
       subGraph="digraph G {
            label=sub;
            0 [moduleName=Greetings, name=Cosmos, ref=333, subGraph=\"(none)\"];
            1 [moduleName=\"\", name=\"\", ref=0, subGraph=\"(none)\"];
            0->0  [name=nested];
       }
     "];
    0->1  [name=one];
    2->0  [name=two];
}
    
address of subgraph in g1: 0x1025900
address of subgraph in g2: 0x1025ba0

Note that the subgraph addresses are distinct. There is no memory leak here.

Full Listing

Live On Coliru

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

// forward declarations so we can have recursive object structure
template <typename T> struct value_ptr {
    /*explicit*/ value_ptr(std::nullptr_t = {}) {}
    /*explicit*/ value_ptr(T v) : p_(std::make_unique<T>(std::move(v))) {}
    value_ptr(value_ptr const& rhs) : p_(rhs.p_ ? std::make_unique<T>(*rhs.p_) : nullptr) {}
    value_ptr& operator=(value_ptr const& rhs) {
        p_ = rhs.p_ ? std::make_unique<T>(*rhs.p_) : nullptr;
        return *this;
    }

    value_ptr(value_ptr&& rhs)                    = default;
    value_ptr&         operator=(value_ptr&& rhs) = default;

    explicit operator bool() const { return !!p_; }

    auto& operator*() const { return *p_; }
    auto& operator->() const { return *p_; }

    auto address() const { return p_.get(); }

  private:
    std::unique_ptr<T> p_;

    friend std::ostream& operator<<(std::ostream& os, value_ptr const& p) {
        if (!p)
            return os << "(none)";
        return os << *p;
    }
    friend std::istream& operator>>(std::istream& is, value_ptr&) { // dynamic properties cannot be readonly
        is.setstate(std::ios::failbit);
        return is;
    }
};

struct BGType; // forward
using SubGraph = value_ptr<BGType>;

struct vertexProps {
    std::string _moduleName;
    std::string _name;
    long        _refPtr = 0;
    SubGraph    _subGraph;
};

struct edgeProps {
    edgeProps(edgeProps const&)            = default;
    edgeProps& operator=(edgeProps const&) = default;
    explicit edgeProps(std::string name = "") : _name(name){};

    std::string _name;
};

struct schPinInfo { std::string id; };
schPinInfo const wellknownPins[] = {
    {"i1"}, {"i2"}, {"i3"}, {"o4"}, {"o5"}, {"i6"}, {"i7"}, {"i8"}, {"o9"}, {"o10"},
};

static schPinInfo const* const i1  = wellknownPins + 0;
static schPinInfo const* const i2  = wellknownPins + 1;
static schPinInfo const* const i3  = wellknownPins + 2;
static schPinInfo const* const o4  = wellknownPins + 3;
static schPinInfo const* const o5  = wellknownPins + 4;
static schPinInfo const* const i6  = wellknownPins + 5;
static schPinInfo const* const i7  = wellknownPins + 6;
static schPinInfo const* const i8  = wellknownPins + 7;
static schPinInfo const* const o9  = wellknownPins + 8;
static schPinInfo const* const o10 = wellknownPins + 9;

using Pins = std::vector<schPinInfo const*>;
struct Layout {
    Pins input, inout, output;
};
struct schSymbol {};

struct graphProps {
    graphProps& operator=(graphProps const&) = default;
    explicit graphProps(std::string name = {}) : _name(std::move(name)) {}

    std::string                                     _name;
    std::map<std::string, Layout>                   _modInfo;
    std::map<std::string, std::vector<std::string>> _altNames;
    std::map<std::string, schSymbol>                _modSymbol;
};

using BGTypeImpl = boost::adjacency_list<            //
    boost::vecS, boost::vecS, boost::bidirectionalS, //
    vertexProps, edgeProps, graphProps>;

struct BGType : BGTypeImpl {
    using BGTypeImpl::BGTypeImpl;
    using BGTypeImpl::operator=;

    friend auto& get_property(BGType& g, boost::graph_bundle_t prop) {
        return boost::get_property(static_cast<BGTypeImpl&>(g), prop);
    }
    friend auto& get_property(BGType const& g, boost::graph_bundle_t prop) {
        return boost::get_property(static_cast<BGTypeImpl const&>(g), prop);
    }
    friend std::ostream& operator<<(std::ostream& os, BGType const& g) {
        boost::dynamic_properties dp;
        // this is ugly, but see https://stackoverflow.com/a/27238425/85371
        auto& ncg = const_cast<BGType&>(g);
        dp.property("node_id",    get (boost::vertex_index, g));
        dp.property("moduleName", get (&vertexProps::_moduleName, ncg));
        dp.property("name",       get (&vertexProps::_name, ncg));
        dp.property("subGraph",   get (&vertexProps::_subGraph, ncg));
        dp.property("ref",        get (&vertexProps::_refPtr, ncg));
        dp.property("name",       get (&edgeProps::_name, ncg));
        dp.property("label", boost::make_constant_property<BGType*>(get_property(g)._name));
        write_graphviz_dp(os, g, dp);
        return os;
    }
};

// implement functions now that BGType is complete

BGType make_graph() {
    BGType g{3, graphProps{"name"}};
    boost::get_property(g)._modInfo = {
        {"mod1", Layout{{i1, i2, i3}, {}, {o4, o5}}},
        {"mod2", Layout{{i6, i7, i8}, {}, {o9, o10}}},
    };
    boost::get_property(g)._altNames = {
        {"mod1", {"MOD1", "MOD_1"}},
        {"mod2", {"MOD2", "MOD_2"}},
    };
    boost::get_property(g)._modSymbol = {
        {"mod1", schSymbol{}},
        {"mod2", schSymbol{}},
    };

    g[0] = vertexProps{"Hello", "world", 111, {}};
    g[1] = vertexProps{"Goodbye", "moon", 222, {}};
    g[2] = vertexProps{"Greetings", "Cosmos", 333, {}};

    { // add a subgraph to vertex 2
        BGType sub(2, graphProps{"sub"});
        sub[0] = vertexProps{"Greetings", "Cosmos", 333, {}};
        add_edge(0, 0, edgeProps{"nested"}, sub);

        g[2]._subGraph = sub;
    }

    add_edge(0, 1, edgeProps{"one"}, g);
    add_edge(2, 0, edgeProps{"two"}, g);
    return g;
}

int main() {
    BGType g1 = make_graph();
    BGType g2;
    g2 = g1; // FULL COPY

    std::cout << "g2:\n" << g2 << "\n";
    std::cout << "address of subgraph in g1: " << g1[2]._subGraph.address() << "\n";
    std::cout << "address of subgraph in g2: " << g2[2]._subGraph.address() << "\n";
}