Edge - весовая ассоциация

Question

Я работаю в C с библиотекой igraph.

Мне нужно вычислить минимальное остовное дерево графа, используя следующий вызов:

igraph_minimum_spanning_tree_prim( &input_graph, &mst_tree, &w); 

где:

• input_graph: График для обработки.Тип igraph_t .
• mst_tree: дерево mst, возвращаемое функцией.Тип igraph_t .
• w: Вектор с весом каждого ребра графа input_graph. Тип igraph_vector_t .

, как запрашивается в библиотеке igraph, связь между ребрами и весами определяется их индексом, то есть первым ребром в input_graph имеет вес, заданный первым элементом вектора w , вес второго ребра задан вторым элементом w вектор и тд.

Поскольку ребра mst_tree являются подмножеством ребер input_graph (следовательно, количество реберв input_graph и в mst_tree являются разными), невозможно получить вес ребер mst_tree , связав их индекс.

Существует некоторая функция igraph для получения веса каждого ребра в mst_tree , только зная mst_tree , input_graph и ш?

Гильермо.

Answer 1

В igraph 0.5.4 такой функции нет, извините :( В igraph 0.6 API минимального связующего дерева немного изменится, поэтому будет другая функция со следующей сигнатурой:

int igraph_minimum_spanning_tree(const igraph_t* graph, igraph_vector_t* res, const igraph_vector_t* weights);

, где res будет содержать индексы ребер, которые составляют остовное дерево. igraph 0.6 еще не выпущен, но он довольно стабилен, поэтому вы можете попробовать обновить его до igraph 0.6 (если вы не возражаете против нескольких изменений API тут и там).

Отказ от ответственности: я один из авторов igraph.