1

我有一个图结构，其中顶点可以有多种类型的边。

顶点类型是多态的，它们必须能够根据它们的类型“分类”边并相应地存储它们，但我希望能够在“基本级别”检索所有边而不知道它们是如何存储的。

我正在尝试使用 boost::adaptors::transformed、boost::range::join 和 boost::any_range 来实现这一点。

一个例子：

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

这在 getEdges() 评估时给了我段错误。据我了解，any_range 保留对临时变量 boost::adaptors::transformed 的引用。我试图将转换适配器范围保留为类成员变量，但它不起作用。

有没有使用any_range 实现这一目标的正确方法？transform_iterator / any_iterator 类型可以作为答案还是我会面临类似的问题？

4

1 回答 1

1

该错误是由于boost::range::detail::any_iterator 不能很好地与 boost::zip_iterator 配合使用（Trac Issue #10493）

解决方法是将 any_range 的引用类型设为 const 值：

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

查看演示Live On Coliru

我可以建议对顶点使用带有变体类型的面向值的图形表示。有一个较旧的答案显示Graph 具有两种类型的节点

注意这仍然存在由于自边缘而导致内存泄漏的设计问题。

我可以建议简化单个边缘集合：

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

注意这仍然存在由于自边缘而导致内存泄漏的设计问题。

概念性思考

如果有单独的边集合的原因仅仅是因为顶点同时是不同图的一部分，那就这样做吧！

Live On Coliru

印刷

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

在这种情况下，我建议进行更多简化：

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");
}
于 2017-09-26T08:40:41.820 回答