有効グラフの経路の重みを合計する方法

2 views (last 30 days)
Kayo
Kayo on 16 Oct 2024
Edited: Kayo on 17 Oct 2024
次のような有向グラフからallpathで特定のノード間の経路を求め、その経路内のエッジの重みを合計する方法を考えていますが、うまくいきません。教えていただけないでしょうか。
s=[ 1 1 1 1 2 2 2 2 3 3 3 3 3 3 3 4 4 4 5 5 5 5 6 6 6 7 7 7 8 8 8 8 8 8 8 9 9 9 9 9 9 9 10 10 10 10 10 11 11 11 11 11 11 11 12 12 12 12 12 12 13 13 13 13 14 14 14 14 14 14 15 15 15 15 15 15 16 16 16 16 17 17 17 17 18 18 18 18 18 19 19 19 19 19 20 20 21 21 22 22 22 22 23 23 23 23 23 24 24 24 24 25 25 25 25 25 26 26 26 27 27 28 28 28 ]
t=[ 2 3 4 5 3 6 7 8 2 4 8 9 10 11 12 3 5 12 4 12 13 19 2 7 8 2 6 8 2 3 6 7 9 27 28 3 8 10 14 22 26 28 3 9 11 14 15 3 10 12 15 16 17 18 3 4 5 11 17 19 5 19 20 21 9 10 15 22 23 24 10 11 14 16 24 25 11 15 18 25 11 12 18 19 11 16 17 19 25 5 12 13 17 18 13 21 13 20 9 14 23 26 14 22 24 25 26 14 15 23 25 15 16 18 23 24 9 22 23 8 28 8 9 27 ]
weight=[ 22.461 21.11 22.533 24.435 38.527 25.631 38.634 26.326 38.527 15.115 49.658 30.705 9.086 21.328 22.853 15.115 6.555 26.404 6.555 31.488 17.012 37.846 25.631 23.91 28.851 38.634 23.91 20.704 26.326 49.658 28.851 20.704 41.859 18.229 18.165 30.705 41.859 21.853 7.442 5.078 7.333 40.476 9.086 21.853 17.131 16.971 11.509 21.328 17.131 7.832 11.087 6.976 8.852 21.659 22.853 26.404 31.488 7.832 6.318 16.27 17.012 53.693 16.604 16.034 7.442 16.971 9.887 6.301 6.204 4.8 11.509 11.087 9.887 11.188 9.168 13.3 6.976 11.188 17.91 10.305 8.852 6.318 15.554 15.476 21.659 17.91 15.554 22.357 22.044 37.846 16.27 53.693 15.476 22.357 16.604 12.461 16.034 12.461 5.078 6.301 2.724 4.146 6.204 2.724 5.809 12.357 5.297 4.8 9.168 5.809 9.008 13.3 10.305 22.044 12.357 9.008 7.333 4.146 5.297 18.229 8.066 18.165 40.476 8.066 ]

Accepted Answer

Akira Agata
Akira Agata on 17 Oct 2024
allpaths 関数の第2出力引数として、経由するエッジの番号のリストが出力されます。これを使って経路内のエッジの重みを合計することができます。
たとえば今回対象となるグラフの1番目のノードから28番目のノードまでの全経路を allpaths 関数で求めて、そのうち最初の経路上にある全てのエッジの重みを合計するには、以下のようになります。
% 対象となるグラフ情報
s=[ 1 1 1 1 2 2 2 2 3 3 3 3 3 3 3 4 4 4 5 5 5 5 6 6 6 7 7 7 8 8 8 8 8 8 8 9 9 9 9 9 9 9 10 10 10 10 10 11 11 11 11 11 11 11 12 12 12 12 12 12 13 13 13 13 14 14 14 14 14 14 15 15 15 15 15 15 16 16 16 16 17 17 17 17 18 18 18 18 18 19 19 19 19 19 20 20 21 21 22 22 22 22 23 23 23 23 23 24 24 24 24 25 25 25 25 25 26 26 26 27 27 28 28 28 ];
t=[ 2 3 4 5 3 6 7 8 2 4 8 9 10 11 12 3 5 12 4 12 13 19 2 7 8 2 6 8 2 3 6 7 9 27 28 3 8 10 14 22 26 28 3 9 11 14 15 3 10 12 15 16 17 18 3 4 5 11 17 19 5 19 20 21 9 10 15 22 23 24 10 11 14 16 24 25 11 15 18 25 11 12 18 19 11 16 17 19 25 5 12 13 17 18 13 21 13 20 9 14 23 26 14 22 24 25 26 14 15 23 25 15 16 18 23 24 9 22 23 8 28 8 9 27 ];
weight=[ 22.461 21.11 22.533 24.435 38.527 25.631 38.634 26.326 38.527 15.115 49.658 30.705 9.086 21.328 22.853 15.115 6.555 26.404 6.555 31.488 17.012 37.846 25.631 23.91 28.851 38.634 23.91 20.704 26.326 49.658 28.851 20.704 41.859 18.229 18.165 30.705 41.859 21.853 7.442 5.078 7.333 40.476 9.086 21.853 17.131 16.971 11.509 21.328 17.131 7.832 11.087 6.976 8.852 21.659 22.853 26.404 31.488 7.832 6.318 16.27 17.012 53.693 16.604 16.034 7.442 16.971 9.887 6.301 6.204 4.8 11.509 11.087 9.887 11.188 9.168 13.3 6.976 11.188 17.91 10.305 8.852 6.318 15.554 15.476 21.659 17.91 15.554 22.357 22.044 37.846 16.27 53.693 15.476 22.357 16.604 12.461 16.034 12.461 5.078 6.301 2.724 4.146 6.204 2.724 5.809 12.357 5.297 4.8 9.168 5.809 9.008 13.3 10.305 22.044 12.357 9.008 7.333 4.146 5.297 18.229 8.066 18.165 40.476 8.066 ];
% 有向グラフを作成
G = digraph(s, t, weight);
% ノード1からノード28での全経路を計算
[paths, edgepaths] = allpaths(G, 1, 28);
% 得られる経路の数を確認
disp(compose("Pathの数: %d個", numel(paths)))
Pathの数: 4219716個
% 1番目の経路上の重みをすべて加算
nPath = 1;
len = sum(weight(edgepaths{nPath}));
% 結果を可視化
figure
p = plot(G);
highlight(p, ...
Edges = edgepaths{nPath}, ...
EdgeColor = "r", ...
LineWidth = 1.5)
title(compose("Edge Path #%d, L = %.1f", nPath, len), ...
FontSize = 14)
  1 Comment
Kayo
Kayo on 17 Oct 2024
Edited: Kayo on 17 Oct 2024
ありがとうございます。質問投稿後に一応計算できたのですが、自分で考えたものよりもずっと速く計算が出来ました。

Sign in to comment.

More Answers (0)

Categories

Find more on ビッグ データの処理 in Help Center and File Exchange

Tags

Products

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!