Is possible to hide underlying containers with boost range?

Question

I have a graph structure where vertices can have several types of edges.

Vertex types are polymorphic and they must be able to "classify" edges depending on their type and store them accordingly, but I want to be able to retrieve all edges at "base level" without knowing how they are stored.

I'm trying to achieve this using boost::adaptors::transformed, boost::range::join and boost::any_range.

A example of this:

#include <iostream>
#include <sstream>
#include <set>
#include <memory>

#include <boost/range/adaptor/transformed.hpp>
#include <boost/range/join.hpp>
#include <boost/range/any_range.hpp>

// forward declarations
class BaseVertex;
class DerivedVertex1;
class DerivedVertex2;

struct TransformCaster
{
    typedef std::shared_ptr<BaseVertex> result_type;
    std::shared_ptr<BaseVertex> operator()(std::shared_ptr<DerivedVertex1> d1) const { return std::static_pointer_cast<BaseVertex>(d1); }
    std::shared_ptr<BaseVertex> operator()(std::shared_ptr<DerivedVertex2> d2) const { return std::static_pointer_cast<BaseVertex>(d2); }
};

class BaseVertex
{
  public:
    BaseVertex(size_t id): id_(id){}
    virtual ~BaseVertex () {}

    virtual std::stringstream name()
    {std::stringstream ss; ss << "Base " << id_; return ss;}

    virtual boost::any_range<std::shared_ptr<BaseVertex>,boost::forward_traversal_tag> getEdges() const = 0;

  protected:
    size_t id_;

};

class DerivedVertex1 : public BaseVertex
{
  public:
    DerivedVertex1(size_t id): BaseVertex(id){}

    virtual std::stringstream name()
    {std::stringstream ss; ss << "Derived1 " << id_; return ss;}

    void addEdge1(const std::shared_ptr<DerivedVertex1>& rel)
      { relations_1_.insert(rel); }
    void addEdge2(const std::shared_ptr<DerivedVertex2>& rel)
      { relations_2_.insert(rel); }

    virtual boost::any_range<std::shared_ptr<BaseVertex>,boost::forward_traversal_tag> getEdges() const
    {
      // These are temporary, right?
      auto range1 = relations_1_ | boost::adaptors::transformed(TransformCaster());
      auto range2 =  relations_2_ | boost::adaptors::transformed(TransformCaster());

      auto joined_range = boost::range::join(range1, range2);

      // This is wrapping temporary transformed ranges?
      boost::any_range<std::shared_ptr<BaseVertex>,boost::forward_traversal_tag> poly_range(joined_range);

      return poly_range;
    }

  private:
    std::set<std::shared_ptr<DerivedVertex1>> relations_1_;
    std::set<std::shared_ptr<DerivedVertex2>> relations_2_;
};

class DerivedVertex2 : public BaseVertex
{
  public:
    DerivedVertex2(size_t id): BaseVertex(id){}

    virtual std::stringstream name()
    {std::stringstream ss; ss << "Derived2 " << id_; return ss;}

    void addEdge1(const std::shared_ptr<DerivedVertex1>& rel)
      { relations_1_.insert(rel); }
    void addEdge2(const std::shared_ptr<DerivedVertex2>& rel)
      { relations_2_.insert(rel); }

    virtual boost::any_range<std::shared_ptr<BaseVertex>,boost::forward_traversal_tag> getEdges() const
    {
      // These are temporary, right?
      auto range1 = relations_1_ | boost::adaptors::transformed(TransformCaster());
      auto range2 =  relations_2_ | boost::adaptors::transformed(TransformCaster());

      auto joined_range = boost::range::join(range1, range2);

      // This is wrapping temporary transformed ranges?
      boost::any_range<std::shared_ptr<BaseVertex>,boost::forward_traversal_tag> poly_range(joined_range);

      return poly_range;
    }

  private:
    std::set<std::shared_ptr<DerivedVertex1>> relations_1_;
    std::set<std::shared_ptr<DerivedVertex2>> relations_2_;
};

int main()
{

  std::shared_ptr<DerivedVertex1> derived1 = std::make_shared<DerivedVertex1>(0);
  std::shared_ptr<DerivedVertex2> derived2 = std::make_shared<DerivedVertex2>(1);

  derived1->addEdge1(derived1); // self pointing edge
  derived1->addEdge2(derived2); // edge towards other

  std::shared_ptr<BaseVertex> base = std::static_pointer_cast<BaseVertex>(derived1);

  // segfault on getEdges()
  for(auto& e : base->getEdges())
    std::cout << e->name().str() << std::endl;

  return 0;
}

This is giving me segfault at getEdges() evaluation. As I understand, any_range is keeping a reference to temporary variables boost::adaptors::tranformed. I tried to keep the transform adaptors ranges as class member variables but it didn't work.

Is there a correct way to achieve this with any_range? Could transform_iterator / any_iterator types be the answer or would I face similar issues?

You do understand that `boost::any_range` has **horrible** performance right? Every one of many iterator operations becomes an indirect virtual function call... Second, have you tried moving? If I was writing range adapters, I'd store copies of things that where moved into me, and store references to things that are not moved into me. — Yakk - Adam Nevraumont, Sep 25 '17 at 19:54
I intend to use this feature on an asynchronous communication layer prior to send data. Could you elaborate a bit on the moving idea? you mean that I should write a completely new adaptor that hold copies of ranges? There is no support for this on boost range? — CaTo, Sep 25 '17 at 20:41
It may be cheaper to just return a `vector>` rather than iterating through an `any_range`, and definitely simpler. Or, to be fancy, have a method that takes a `std::function< void(gsl::span>)>` sink function. Then the producer can use a fixed sized buffer, populate it in chunks, sink it into the processing code, and continue on its way. — Yakk - Adam Nevraumont, Sep 25 '17 at 23:32

sehe · Accepted Answer · 2017-09-26T09:18:28.250

The bug is due to boost::range::detail::any_iterator doesn't play well with boost::zip_iterator (Trac Issue #10493)

The workaround is to make the reference type of the any_range a const value:

using BaseVertexRange = boost::any_range<BaseVertexPtr, boost::forward_traversal_tag, BaseVertexPtr const>;

See a demo Live On Coliru

May I suggest using a value-oriented graph representation with a variant type for the vertex. There's an older answer showing that Graph with two types of nodes

NOTE This still leaves the design issue of leaked memory due the self-edge.

May I suggest the simplification of a single collection of edges:

Live On Coliru

#include <iostream>
#include <memory>
#include <set>
#include <sstream>

class BaseVertex {
  public:
    BaseVertex(size_t id) : id_(id) {}
    virtual ~BaseVertex() {}

    virtual std::string name() { return "Base " + std::to_string(id_); }

    void addEdge(std::shared_ptr<BaseVertex> rel) { _relations.insert(std::move(rel)); }

    auto getEdges() const {
        return _relations;
    }

  protected:
    int id_;
    std::set<std::shared_ptr<BaseVertex> > _relations;
};

class DerivedVertex1 : public BaseVertex {
  public:
    DerivedVertex1(size_t id) : BaseVertex(id) {}

    virtual std::string name() { return "DerivedVertex1 " + std::to_string(id_); }
};

class DerivedVertex2 : public BaseVertex {
  public:
    DerivedVertex2(size_t id) : BaseVertex(id) {}

    virtual std::string name() { return "DerivedVertex2 " + std::to_string(id_); }
};

int main() {

    auto derived1 = std::make_shared<DerivedVertex1>(0);
    auto derived2 = std::make_shared<DerivedVertex2>(1);

    derived1->addEdge(derived1); // self pointing edge
    derived1->addEdge(derived2); // edge towards other

    for (auto& e : derived1->getEdges())
        std::cout << e->name() << std::endl;
}

NOTE This still leaves the design issue of leaked memory due the self-edge.

Conceptual Thoughts

If the reason to have separate collections of edges is merely because vertices are part of different graphs at the same time, make it so!

Live On Coliru

Prints

==== first graph
DerivedVertex1 0 --> DerivedVertex1 0 
==== second graph
DerivedVertex1 0 --> DerivedVertex2 1 
DerivedVertex2 1 -->

I'd suggest a few more simplifications in such a case:

Live On Coliru

#include <iostream>
#include <memory>
#include <set>
#include <sstream>

class BaseVertex {
  public:
    BaseVertex(size_t id) : id_(id) {}
    virtual ~BaseVertex() {}

    virtual std::string name() { return "Base " + std::to_string(id_); }
  protected:
    int id_;
};

class DerivedVertex1 : public BaseVertex {
  public:
    DerivedVertex1(size_t id) : BaseVertex(id) {}

    virtual std::string name() { return "DerivedVertex1 " + std::to_string(id_); }
};

class DerivedVertex2 : public BaseVertex {
  public:
    DerivedVertex2(size_t id) : BaseVertex(id) {}

    virtual std::string name() { return "DerivedVertex2 " + std::to_string(id_); }
};

#include <boost/graph/adjacency_list.hpp>
#include <boost/property_map/transform_value_property_map.hpp>

using Graph = boost::adjacency_list<boost::vecS, boost::vecS, boost::directedS, std::shared_ptr<BaseVertex> >;

void DebugPrint(std::string const& caption, Graph const& g);

int main() {

    auto derived1 = std::make_shared<DerivedVertex1>(0);
    auto derived2 = std::make_shared<DerivedVertex2>(1);

    Graph g1, g2;

    {
        auto v1 = add_vertex(derived1, g1);
        add_edge(v1, v1, g1);
    }

    {
        auto v1 = add_vertex(derived1, g2);
        auto v2 = add_vertex(derived2, g2);
        add_edge(v1, v2, g2);
    }

    DebugPrint("first graph", g1);
    DebugPrint("second graph", g2);
}

#include <boost/graph/graph_utility.hpp>
void DebugPrint(std::string const& caption, Graph const& g) {
    auto name_map = boost::make_transform_value_property_map(std::mem_fn(&BaseVertex::name), get(boost::vertex_bundle, g));

    boost::print_graph(g, name_map, std::cout << "==== " << caption << "\n");
}

I added some conceptual thoughts, that also address the problem of the memory leak (by making the relations owned by their respective graphs, instead of the vertices involved) — sehe, Sep 26 '17 at 09:19
The 'const solution' works great, but let me ask you: this works only by the fact that const extends the lifetime of wrapped iterators? or any_range is actually intended to be use in this way and this is just a bug? I'm new to boost and getting use to his documentation, what's the point of that third template "reference" parameter? Regarding graph ideas: In my case graph vertices are accessed by several agents in a concurrent way. The graph is not completely known by any of them and cannot have a central contention point such as boost::graph (Parallel BGL synchronization model scared me) — CaTo, Sep 27 '17 at 03:27
The `reference_type` is for the case where you want a proxy type returned (best bad example: `vector::iterator`). Re. you use case: it seems that synchronization is missing ([ref](https://cppwisdom.quora.com/shared_ptr-is-almost-thread-safe)). Also, the ownership problems seems to indicate weak pointers are called for. (I the ownership really shared? Finally, having lots of tiny actors could well prove to be slower than synchronizing access to the graph. I'll let you figure those out, assuming you've given them some thought already. — sehe, Sep 27 '17 at 06:55

Is possible to hide underlying containers with boost range?

1 Answers1

Conceptual Thoughts