Boost :: Get с Boost :: Filter_graph на adjacency_list со свойствами netsed - PullRequest
Новая
       50

Boost :: Get с Boost :: Filter_graph на adjacency_list со свойствами netsed

0 голосов
/ 27 ноября 2018

Я написал небольшую оболочку для boost::adjacency_list: 

    template <typename T>
    using VertexWithIndexProperty =            
          boost::property<boost::vertex_index_t, int, T>;

    template <typename VertexProperty, typename EdgeProperty = 
                                    boost::no_property>
    class MutableGraph  : public boost::adjacency_list< boost::setS, 
                             boost::listS, boost::undirectedS, 
                             VertexWithIndexProperty<VertexProperty>, EdgeProperty> {
    public:
         using BoostBase =
          boost::adjacency_list<boost::setS, boost::listS, boost::undirectedS,
                                VertexWithIndexProperty<VertexProperty>,
                                EdgeProperty>;
      MutableGraph() {}
      MutableGraph(std::size_t n) : BoostBase(n) {}
      MutableGraph(const MutableGraph &rhs) : BoostBase(rhs) {}
      MutableGraph &operator=(const MutableGraph &rhs) {
        static_cast<BoostBase *>(this)->operator=(rhs);
        return *this;
      }
    };

Затем я использую ее следующим образом: я собираю несколько vertex_descriptors в наборах для создания boost::filtered_graph: `

using Graph = MutableGraph<boost::property<vertex_color_t, int>>;
Graph g;

std::set<int> C, H; //vertex_descriptors I collect

...

auto vertex_index_map = get(vertex_index, g);

std::function<bool(vertex_descriptor)> vertexes_filter =
      [&vertex_index_map, &C, &H](vertex_descriptor v) {

        auto index = vertex_index_map[v];
        return C.find(index) != C.end() || H.find(index) != H.end();
      };

   boost::filtered_graph<Graph, boost::keep_all, decltype(crown_vertexes_filter)>
           auxilary(g, boost::keep_all(), crown_vertexes_filter);

Все в порядке, но когда я пытаюсь получить любую карту-свойства для вершин, например: `

auto auxilary_vertex_index_map
          = get(boost::vertex_index, auxilary);

Я получаю следующую ошибку: 

could not convert

    boost::adj_list_vertex_property_map<boost::adjacency_list<boost::setS, 
boost::listS, boost::undirectedS, 
boost::property<boost::vertex_index_t, int, 
boost::property<boost::vertex_color_t, int> >, 
boost::no_property, boost::no_property, boost::listS>, int, 
int&, boost::vertex_index_t>

to 

 boost::adj_list_vertex_property_map<MutableGraph<
 boost::property<boost::vertex_color_t, int> >,
 int, 
 int&,
 boost::vertex_index_t>

Я получаю эту ошибкув 

template <typename G, typename EP, typename VP, typename Property>
  typename property_map<G, Property>::type
  get(Property p, filtered_graph<G, EP, VP>& g)
  {
    return get(p, const_cast<G&>(g.m_g));
  }

в filtered_graph.hpp.

Я не понимаю, почему это происходит, из-за моей оболочки или из-за того, что я решил использовать вложенные свойства вместо связанных.

Заранее спасибо!

1 Ответ

0 голосов
/ 27 ноября 2018

Вложенные свойства известны как "внутренние свойства".Это не ваша проблема.

Вместо этого ваша проблема связана с аргументом VertexContainerSelector (boost::listS).Это приводит к тому, что тип vertex_descriptor будет

  • не целым (вместо этого теперь это непрозрачный тип)
  • не удваивается как индекс де-фактора вершины

Вы уже знаете это, поэтому вы добавили свойство, которое будет служить картой индекса вершины.Однако то, что вы не ожидали, это то, что он делает результирующий тип для карты свойств vertex_index (boost::property_map<Graph, vertex_index_t>::type) другим, и, следовательно, оболочка переадресации в filtered_graph больше не подходит для счета: 

  template <typename G, typename EP, typename VP, typename Property>
  typename property_map<G, Property>::type
  get(Property p, filtered_graph<G, EP, VP>& g)
  {
    return get(p, const_cast<G&>(g.m_g));
  }

Если вы можете позволить себе просто переключиться на vecS, я бы пошел на это.В противном случае, тщательно продумайте ваши требования и последствия.Примечательно, что ваш VertexContainerSelector выбор listS приводит к vertex_descriptor как с эталонной, так и со стабильностью итератора.Любой vertex_descriptor из фильтрованного графа должен быть действительным для основного графа и наоборот.Почему бы просто не сохранить ту же карту:

Live On Coliru 

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/filtered_graph.hpp>
#include <boost/graph/graph_utility.hpp> // print_graph

template <typename T> using AddIndex = boost::property<boost::vertex_index_t, int, T>;

template <
    typename VertexProperty,
    typename EdgeProperty = boost::no_property, 
    typename Base = boost::adjacency_list<boost::setS, boost::listS, boost::undirectedS, AddIndex<VertexProperty>, EdgeProperty> >
struct MutableGraph : Base {
    using BoostBase = Base;

    MutableGraph(std::size_t n = 0) : BoostBase(n) {}
    using BoostBase::operator=;
};

int main() {
    using Graph = MutableGraph<boost::property<boost::vertex_color_t, int> >;
    using vertex_descriptor = Graph::vertex_descriptor;
    Graph g;
    auto a = add_vertex({1, 0}, g);
    auto b = add_vertex({2, 0}, g);
    auto c = add_vertex({3, 0}, g);
    auto d = add_vertex({4, 0}, g);
    add_edge(a, b, g);
    add_edge(a, c, g);
    add_edge(b, d, g);

    std::set<int> C{1,2}, H{/*3,*/4}; // vertex_descriptors I collect
    auto id = get(boost::vertex_index, g);
    std::function<bool(vertex_descriptor)> vertexes_filter = [id, &C, &H](vertex_descriptor v) {
        auto index = id[v];
        return C.count(index) || H.count(index);
    };

    boost::filtered_graph<Graph, boost::keep_all, decltype(vertexes_filter)> auxilary(g, boost::keep_all(), vertexes_filter);

    auto aux_id = id;
    print_graph(g,        id,     std::cout << "\n---- Original\n");
    print_graph(auxilary, aux_id, std::cout << "\n---- Filtered\n");
}

Печать: 

---- Original
1 <--> 2 3 
2 <--> 1 4 
3 <--> 1 
4 <--> 2 

---- Filtered
1 <--> 2 
2 <--> 1 4 
4 <--> 2

Это именно то, что вам нужно.

Дополнительные замечания

Обратите внимание на упрощения в коде.Ваш MutableGraph класс может быть записан как: 

template <
    typename VertexProperty,
    typename EdgeProperty = boost::no_property, 
    typename Base = boost::adjacency_list<boost::setS, boost::listS, boost::undirectedS, AddIndex<VertexProperty>, EdgeProperty> >
struct MutableGraph : Base {
    using BoostBase = Base;

    MutableGraph(std::size_t n = 0) : BoostBase(n) {}
    using BoostBase::operator=;
};

Хотя даже эти два члена могут быть просто опущены для использования в этом примере (operator= все равно будет сгенерирован правильно компилятором).

¹ за исключением, возможно, отфильтрованных ...

БОНУС

Обновление в ответ на комментарии: вы можете "автоматизировать" переадресацию типов, специализируя черту boost::property_map<>: 

namespace boost {
    // overriding the typedef to take the types from the BoostBase instead:
    template <typename Tag, typename... Args>
        struct property_map<MyGraph<Args...>, Tag> : property_map<typename MyGraph<Args...>::BoostBase, Tag> {
        };
}

Вот и все.Теперь вы можете выполнять печать из функции, которая не знает, с каким типом графика он имеет дело: 

template <typename WhateverGraph>
void some_naive_user_function(WhateverGraph const& g, std::ostream& os) {
    // we don't know whether WhateverGraph is filtered or not, but we don't care
    print_graph(g, get(boost::vertex_index, g), os);
}

get(boost::vertex_index, g) просто работает из-за специализации: 

boost::filtered_graph<Graph, boost::keep_all, decltype(vertexes_filter)> auxilary(g, boost::keep_all(), vertexes_filter);

some_naive_user_function(g,        std::cout << "\n---- Origina (via naive user function)\n");
some_naive_user_function(auxilary, std::cout << "\n---- Filtered (via naive user function)\n");

Посмотреть Live On Coliru

...