This Issue is similar to BGL: Example of isomorphism with vertex invariants
I am working on a Boost.Graph tutorial and calling boost::is_isomorphism on two graphs without properties is easy. But I cannot get it working when the vertices now have names.
This code shows:
Here is how I create path graphs with named vertices (which is rather unimportant, but shown for completion):
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;
}
Here is my test:
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));
}
I would like to write the function is_named_vertices_isomorphic more or less as such (note: this will compile, but fail the test, as inspired by 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])
)
);
}
Looking at the question BGL: Example of isomorphism with vertex invariants made me come up with this:
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))
);
}
Both solutions fail. Who can help me out?
It does seem you're not after iso-morphism, at least not strictly according to the definition.
If you actually wished to compare graphs regardless of the Vertex Index ordering, but strictly comparing vertex names, you will have to map the names onto integral types (because the max_vertex_invariant value is expected to be unsigned integral).
Here's a simplistic way to achieve it:
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));
VertexInvariant::Map shared_names;
VertexInvariant inv1 { g, shared_names };
VertexInvariant inv2 { h, shared_names };
inv1.collect_names();
inv2.collect_names();
return boost::isomorphism(g, h,
boost::isomorphism_map(make_iterator_property_map(iso.begin(), ref_index_map))
.vertex_invariant1(inv1)
.vertex_invariant2(inv2)
);
}
I've not made things generic yet, because it distracts.
For good form, you'd need to use
boost::property_maps::property_traits<boost::property_map<graph1, boost::vertex_name_t>::const_type>::value_typeor similar, and check that the resultant type is actually compatible for comparison betweengraph1andgraph1etc.To be "actually" generic you'd want to pass in a deduced property map instead of
boost::get(boost::vertex_name, g)and so on.To be honest, I feel that this doesn't make much sense for such semantic-laden things as the iso-morphism invariants. You can obviously make things as generic as you need them to be for your application.
struct VertexInvariant {
using Map = std::map<std::string, size_t>;
Graph const& _graph;
Map& _mappings;
using result_type = size_t;
using argument_type = Graph::vertex_descriptor;
size_t operator()(argument_type u) const {
return _mappings.at(boost::get(boost::vertex_name, _graph, u));
}
size_t max() const { return _mappings.size(); }
void collect_names() {
for (auto vd : boost::make_iterator_range(boost::vertices(_graph))) {
size_t next_id = _mappings.size();
auto ins = _mappings.insert({ boost::get(boost::vertex_name, _graph, vd), next_id});
if (ins.second) {
//std::cout << "Mapped '" << ins.first->first << "' to " << ins.first->second << "\n";
}
}
}
};
Where the helper VertexInvariant is defined as:
struct VertexInvariant {
using Map = std::map<std::string, size_t>;
Graph const& _graph;
Map& _mappings;
using result_type = size_t;
using argument_type = Graph::vertex_descriptor;
size_t operator()(argument_type u) const {
return _mappings.at(boost::get(boost::vertex_name, _graph, u));
}
size_t max() const { return _mappings.size(); }
void collect_names() {
for (auto vd : boost::make_iterator_range(boost::vertices(_graph))) {
size_t next_id = _mappings.size();
auto ins = _mappings.insert({ boost::get(boost::vertex_name, _graph, vd), next_id});
if (ins.second) {
//std::cout << "Mapped '" << ins.first->first << "' to " << ins.first->second << "\n";
}
}
}
};
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/isomorphism.hpp>
#include <boost/graph/vf2_sub_graph_iso.hpp>
#include <boost/graph/graph_utility.hpp>
using Graph = boost::adjacency_list<boost::vecS, boost::vecS, boost::directedS,
boost::property<boost::vertex_name_t, std::string> >;
Graph create_empty_undirected_named_vertices_graph() { return {}; }
Graph 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(boost::vertex_name, g); // not boost::get
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 name_it = std::begin(names);
for (++name_it; name_it != j; ++name_it) // Skip first
{
auto vd_2 = boost::add_vertex(g);
vertex_name_map[vd_2] = *name_it;
const auto aer = boost::add_edge(vd_1, vd_2, g);
assert(aer.second);
vd_1 = vd_2;
}
return g;
}
//////////////////////////////////////// {{{
namespace {
struct VertexInvariant {
using Map = std::map<std::string, size_t>;
Graph const& _graph;
Map& _mappings;
using result_type = size_t;
using argument_type = Graph::vertex_descriptor;
size_t operator()(argument_type u) const {
return _mappings.at(boost::get(boost::vertex_name, _graph, u));
}
size_t max() const { return _mappings.size(); }
void collect_names() {
for (auto vd : boost::make_iterator_range(boost::vertices(_graph))) {
size_t next_id = _mappings.size();
auto ins = _mappings.insert({ boost::get(boost::vertex_name, _graph, vd), next_id});
if (ins.second) {
//std::cout << "Mapped '" << ins.first->first << "' to " << ins.first->second << "\n";
}
}
}
};
}
//////////////////////////////////////// }}}
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));
VertexInvariant::Map shared_names;
VertexInvariant inv1 { g, shared_names };
VertexInvariant inv2 { h, shared_names };
inv1.collect_names();
inv2.collect_names();
return boost::isomorphism(g, h,
boost::isomorphism_map(make_iterator_property_map(iso.begin(), ref_index_map))
.vertex_invariant1(inv1)
.vertex_invariant2(inv2)
);
}
void is_named_vertices_isomorphic_demo() noexcept {
const auto g = create_named_vertices_path_graph({ "Alpha", "Beta", "Gamma" });
std::cout << "\n==== g:\n"; boost::print_graph(g, boost::get(boost::vertex_name, g));
const auto h = create_named_vertices_path_graph({ "Alpha", "Gamma", "Beta" });
std::cout << "\n==== h:\n"; boost::print_graph(h, boost::get(boost::vertex_name, h));
assert(is_named_vertices_isomorphic(g, g));
assert(!is_named_vertices_isomorphic(g, h));
}
int main() { is_named_vertices_isomorphic_demo(); }
Prints:
==== g:
Alpha --> Beta
Beta --> Gamma
Gamma -->
==== h:
Alpha --> Gamma
Gamma --> Beta
Beta -->