Использование boost :: graph isomorphism

Question

Использование boost :: graph isomorphism

Как мне указать boost::isomorphism_map когда используешь adjacency_list<vecS, vecS, undirectedS>?

То, что я пытаюсь выполнить, отмечено ?????????:

typedef adjacency_list<vecS, vecS, undirectedS> graph_t;
graph_t g1(n), g2(n);

add_edge(0, 1, g1); add_edge(1, 2, g1);

add_edge(9, 10, g2);  add_edge(10, 11, g2);

std::vector<graph_traits<graph_t>::vertex_descriptor> f(n);

bool ret = isomorphism
(g1, g2, isomorphism_map
(make_iterator_property_map(f.begin(), ?????????, f[0])));

1

boost c++c++11 graph isomorphism

Решение

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

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

Источник

Accepted Answer

Чтобы создать карту свойств итератора, вам нужно два аргумента:

make_iterator_property_map( RAIter iter, ID id )

Оставь свой третий аргумент.

Первое у вас есть: f.begin() является итератором произвольного доступа к первому элементу.

ID должна быть карта индекса вершины. В вашем случае вы можете запросить его из графика (потому что vecS приводит к неявному индексу вершины):

Жить на Колиру

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/isomorphism.hpp>
typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS> graph_t;

int main() {
int n = 12;
graph_t g1(n), g2(n);

add_edge(0, 1, g1);
add_edge(1, 2, g1);

add_edge(9, 10, g2);
add_edge(10, 11, g2);

std::vector<graph_t::vertex_descriptor> f(n);

bool ret = isomorphism(
g1, g2,
isomorphism_map(boost::make_iterator_property_map(f.begin(), boost::get(boost::vertex_index, g1)))
);
}

Заметки

Рассмотрите возможность создания безопасной карты итераторов:

boost::make_safe_iterator_property_map(f.begin(), n, boost::get(boost::vertex_index, g1))

Если вы не заинтересованы в безопасности (?! ??), вы можете сделать намного короче:

bool ret = isomorphism(g1, g2, boost::isomorphism_map(f.data()));

Это использует vertex_index автоматически.

1