Эта проблема похожа на BGL: пример изоморфизма с инвариантами вершин
Я работаю над учебником Boost.Graph, и вызвать boost::is_isomorphism на двух графиках без свойств очень просто . Но я не могу заставить его работать, когда у вершин теперь есть имена.
Этот код показывает:
- Как я создаю графы путей с именованными вершинами (неважно)
- Мой тестовый код
- Моя функция для проверки изоморфизма с именованной вершиной
Вот как я создаю графы путей с именованными вершинами (что довольно неважно, но показано для завершения):
boost::adjacency_list<
boost::vecS,
boost::vecS,
boost::undirectedS,
boost::property<
boost::vertex_name_t, std::string
>
>
create_named_vertices_path_graph(
const std::vector<std::string>& names
) noexcept
{
auto g = create_empty_undirected_named_vertices_graph();
if (names.size() == 0) { return g; }
auto vertex_name_map
= get( //not boost::get
boost::vertex_name,
g
);
auto vd_1 = boost::add_vertex(g);
vertex_name_map[vd_1] = *names.begin();
if (names.size() == 1) return g;
const auto j = std::end(names);
auto i = std::begin(names);
for (++i; i!=j; ++i) //Skip first
{
auto vd_2 = boost::add_vertex(g);
vertex_name_map[vd_2] = *i;
const auto aer = boost::add_edge(vd_1, vd_2, g);
assert(aer.second);
vd_1 = vd_2;
}
return g;
}
Вот мой тест:
void is_named_vertices_isomorphic_demo() noexcept
{
const auto g = create_named_vertices_path_graph(
{ "Alpha", "Beta", "Gamma" }
);
const auto h = create_named_vertices_path_graph(
{ "Alpha", "Gamma", "Beta" }
);
assert( is_named_vertices_isomorphic(g,g));
assert(!is_named_vertices_isomorphic(g,h));
}
Я хотел бы написать функцию is_named_vertices_isomorphic
более или менее как таковую (обратите внимание: она будет скомпилирована, но не пройдет тест, как вдохновлено BGL: Пример изоморфизма с вершинными инвариантами ):
template <typename graph1, typename graph2>
bool is_named_vertices_isomorphic_correct(
const graph1& g,
const graph2& h
) noexcept
{
auto ref_index_map = get(boost::vertex_index, g);
using vd = typename boost::graph_traits<graph1>::vertex_descriptor;
std::vector<vd> iso(boost::num_vertices(g));
return boost::isomorphism(g,h,
boost::isomorphism_map(
make_iterator_property_map(iso.begin(), ref_index_map, iso[0])
)
);
}
Глядя на вопрос BGL: пример изоморфизма с вершинными инвариантами, я придумать это:
template <typename Graph>
std::string discrete_vertex_invariant(
const typename boost::graph_traits<Graph>::vertex_descriptor& vd,
const Graph &g
)
{
const auto name_map = get(boost::vertex_name,g);
return name_map[vd];
}
template <typename Graph>
class discrete_vertex_invariant_functor
{
using vertex_t = typename boost::graph_traits<Graph>::vertex_descriptor;
const Graph& m_graph;
public:
using result_type = std::string;
using argument_type = vertex_t;
discrete_vertex_invariant_functor(const Graph &g) : m_graph(g) {}
result_type operator()(const vertex_t& vd) const
{
return discrete_vertex_invariant(vd,m_graph);
}
result_type max() const
{
return "";
}
};
//helper function to help with argument deduction
template <typename Graph>
discrete_vertex_invariant_functor<Graph> make_discrete_vertex_invariant(
const Graph &g
)
{
return discrete_vertex_invariant_functor<Graph>(g);
}
template <typename graph1, typename graph2>
bool is_named_vertices_isomorphic_correct(
const graph1& g,
const graph2& h
) noexcept
{
auto ref_index_map = get(boost::vertex_index, g);
using vd = typename boost::graph_traits<graph1>::vertex_descriptor;
std::vector<vd> iso(boost::num_vertices(g));
return boost::isomorphism(
g,
h,
isomorphism_map(
make_iterator_property_map(iso.begin(), ref_index_map, iso[0])
).vertex_invariant1(make_discrete_vertex_invariant(g))
.vertex_invariant2(make_discrete_vertex_invariant(h))
);
}
Оба решения терпят неудачу. Кто может мне помочь?
max()
не возвращает верхнюю границу возможных значений вашего инварианта, кажется неверным. Кроме того, добавление тега boost-graph может повысить вероятность того, что ваш вопрос дойдет до эксперта по библиотеке. - person llonesmiz   schedule 29.12.2015