Максимальное соответствие Эдмондса в Boost Graph Library работает вечно? - PullRequest
Новая
       15

Максимальное соответствие Эдмондса в Boost Graph Library работает вечно?

0 голосов
/ 20 октября 2019

Я не вижу нигде в документации, где упоминается слово «застрял» или «бесконечный»: https://www.boost.org/doc/libs/1_71_0/libs/graph/doc/maximum_matching.html

На некоторых графиках алгоритм работает очень долго. Пример, в котором функция зацикливается навсегда (кажется) довольно большой, поэтому я не знаю, как разместить их здесь ...

Я просто вызываю функцию так: 

boost::edmonds_maximum_cardinality_matching(G,
    boost::make_iterator_property_map(mate_map.begin(), boost::get(boost::vertex_index, G)));

Где G - граф, а mate_map - вектор дескриптора вершины.

РЕДАКТИРОВАТЬ: я забыл включить самый важный бит 

typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::directedS> graph;

1 Ответ

0 голосов
/ 20 октября 2019

Использование ориентированного графа может привести к бесконечному циклу.

Использовать 

typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::undirectedS> graph;

Вместо неориентированного графа.

...