Как я могу обнаружить изоморфизм подграфа на мультиграфе, используя Boost vf2_subgraph_iso?

Я пытаюсь использовать Boost’s vf2_subgraph_iso() выявить изоморфизм подграфа.

Я могу успешно сделать это на простом графике, но не могу на мультиграф (график, которому разрешено иметь несколько ребер).

Рассмотрим обнаружение изоморфизма подграфа между следующими G1 и G2:

диаграммы

G1 является подграфом G2, и я хочу обнаружить это, используя следующий код:

#include <vector>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/vf2_sub_graph_iso.hpp>

int main()
{
// Define edge property
typedef boost::property<
boost::edge_name_t,
char
> edge_property;

// Define graph type
typedef boost::adjacency_list<
boost::vecS,           // OutEdgeListS
boost::vecS,           // VertexListS
boost::bidirectionalS, // DirectedS
boost::no_property,    // VertexProperties
edge_property,         // EdgeProperties
boost::no_property,    // GraphProperties
boost::listS           // EdgeListS
> MyGraphType;

// Build graph G1
MyGraphType g1;
std::vector<MyGraphType::vertex_descriptor> v1(3);
for (auto itr = v1.begin(); itr != v1.end(); ++itr) {
*itr = boost::add_vertex(g1);
}
boost::add_edge(v1[0], v1[1], edge_property('a'), g1);
boost::add_edge(v1[0], v1[2], edge_property('a'), g1);
boost::add_edge(v1[1], v1[2], edge_property('b'), g1);

// Build graph G2
MyGraphType g2;
std::vector<MyGraphType::vertex_descriptor> v2(3);
for (auto itr = v2.begin(); itr != v2.end(); ++itr) {
*itr = boost::add_vertex(g2);
}
boost::add_edge(v2[0], v2[1], edge_property('a'), g2);
boost::add_edge(v2[0], v2[2], edge_property('a'), g2);
boost::add_edge(v2[1], v2[2], edge_property('a'), g2);
boost::add_edge(v2[1], v2[2], edge_property('b'), g2);

// Create predicate of edge
typedef boost::property_map<MyGraphType, boost::edge_name_t>::type edge_name_map_t;
typedef boost::property_map_equivalent<edge_name_map_t, edge_name_map_t> edge_comp_t;
edge_comp_t edge_comp = boost::make_property_map_equivalent(
boost::get(boost::edge_name, g1), boost::get(boost::edge_name, g2));

// Create callback
boost::vf2_print_callback<MyGraphType, MyGraphType> callback(g1, g2);

// Execute
const bool result = boost::vf2_subgraph_iso(
g1, g2, callback, boost::vertex_order_by_mult(g1),
boost::edges_equivalent(edge_comp));

std::cout << "subgraph isomorphic? " << std::boolalpha << result << std::endl;

return 0;
}

Ожидаемый результат:

(0, 0) (1, 1) (2, 2)
subgraph isomorphic? true

Фактический результат:

subgraph isomorphic? false

Где мой код не так?

Извините за мой плохой английский. Спасибо!

5

Решение

Задача ещё не решена.

Другие решения

Других решений пока нет …

По вопросам рекламы [email protected]