2

私は igraph ライブラリを使用して C で作業しています。

次の呼び出しを使用して、グラフの最小スパニング ツリーを計算する必要があります。

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ベクトルの最初の要素によって与えられる重みがあり、2 番目のエッジの重みは次のように与えられます。 wベクトル の 2 番目の要素など。

mst_treeのエッジはinput_graph のエッジのサブセットであるため (したがって、input_graph と mst_tree のエッジの量は異なります) 、インデックスを関連付けてmst_treeのエッジの重みを取得することはできません。

mst_tree、input_graph、および wのみを知っているmst_treeの各エッジの重みを取得する igraph 関数がいくつかありますか?

ギレルモ。

4

1 に答える 1

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);

whereresには、スパニング ツリーを構成するエッジのインデックスが含まれます。igraph 0.6 はまだリリースされていませんが、かなり安定しているため、igraph 0.6 にアップグレードしてみてください (いくつかの API の変更を気にしない場合)。

免責事項: 私は igraph の作成者の 1 人です。

于 2011-08-08T13:28:22.410 に答える