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?
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:
#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.
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!
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:
#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");
}