c - 边权重关联

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 图每条边的权重的 vector 。是 igraph_vector_t 类型。

按照 igraph 库中的要求，边和权重之间的关联由它们的索引给出，也就是说，input_graph 中的第一条边具有给定的权重通过 w vector 的第一个元素，第二条边的权重由 w 的第二个元素给出 vector 等等。

由于 mst_tree 的边是 input_graph 的边的子集(因此， input_graph 和 mst_tree 中的边是不同的)，不可能通过关联获得 mst_tree 的边权重他们的指数。

有一些igraph函数可以获取mst_tree中每条边的权重，只知道mst_tree， input_graph 和 w?

吉列尔莫。

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 的作者之一。