此问题类似于BGL: Example of isomorphism with vertex invariants
我正在研究一个Boost.Graph tutorial并且在没有属性的两个图上调用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: Example of isomorphism with vertex invariants的启发而未通过测试）：
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: Example of isomorphism with vertex invariants这个问题让我想到了这个：
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))
);
}
两种解决方案均失谁能帮助我？
2 回答
该函数没有named_vertex_invariant类：
named_vertex_invariant类：
看起来你似乎不是在同态之后，至少不是严格按照定义 .
如果您实际上希望比较图形而不管顶点索引排序，但严格比较顶点名称，则必须将名称映射到整数类型（因为
max_vertex_invariant值应该是无符号整数） .这是一种实现它的简单方法：
我还没有通用，因为它分散了注意力 .
帮助者
VertexInvariant定义为：完整演示
Live On Coliru
打印：