allpaths

2 つのグラフ ノード間のすべての経路の検出

R2021a 以降

構文

paths = allpaths(G,s,t)

[paths,edgepaths] = allpaths(G,s,t)

[___] = allpaths(G,s,t,Name,Value)

説明

paths = allpaths(G,s,t) は、グラフ G のソース ノード s から始まりターゲット ノード t で終了するすべての経路を返します。出力 paths は cell 配列で、各 cell paths{k} の内容は経路上にあるノードのリストになります。

[paths,edgepaths] = allpaths(G,s,t) は、s から t までの各経路上にあるエッジを追加で返します。出力 edgepaths は cell 配列で、edgepaths{k} は対応する経路 paths{k} にあるエッジを示します。

[___] = allpaths(G,s,t,Name,Value) は、1 つ以上の名前と値の引数を使用して追加のオプションを指定します。前述の構文にある任意の出力引数の組み合わせが使用できます。たとえば、MaxNumPaths とスカラーを指定して、返される経路の数を制限できます。

例

無向グラフのすべての経路

4 つのノードをもつ完全グラフの隣接行列を作成し、その隣接行列から無向グラフを作成します。グラフをプロットします。

A = ones(4);
G = graph(A);
plot(G)

グラフのノード 1 から始まりノード 3 で終了するすべての経路を計算します。

paths = allpaths(G,1,3)

paths=5×1 cell array
    {[  1 2 3]}
    {[1 2 4 3]}
    {[    1 3]}
    {[1 4 2 3]}
    {[  1 4 3]}

経路上のエッジ

allpaths の 2 番目の出力引数は、各経路上にあるエッジを返します。これは、多重グラフにおいて、経路上のエッジを一意に識別するためにエッジ インデックスが必要な場合に特に便利です。

8 つのノードと 18 本のエッジをもつ有向多重グラフを作成します。ノードの名前を指定します。ラベル付きのノードとエッジを使用してグラフをプロットします。

s = [1 1 2 2 3 3 2 2 4 6 8 6 6 7 3 3 5 3];
t = [2 3 1 3 2 1 4 4 6 2 6 7 8 8 5 5 7 7];
names = {'A','B','C','D','E','F','G','H'};
G = digraph(s,t,[],names);
p = plot(G,'EdgeLabel',1:numedges(G));

ノード A とノード H の間のすべての経路を計算します。2 つの出力引数を指定して、各経路上にあるエッジのエッジ インデックスも返します。

[paths,edgepaths] = allpaths(G,'A','H');

最初の経路上にあるノードとエッジを表示します。

paths{1}

ans = 1x6 cell
    {'A'}    {'B'}    {'C'}    {'E'}    {'G'}    {'H'}

edgepaths{1}

ans = 1×5

     1     4     9    13    17

最初の経路上にあるノードとエッジを強調表示します。

highlight(p,'Edges',edgepaths{1},'EdgeColor','r','LineWidth',1.5,'NodeColor','r','MarkerSize',6)

返される経路数の制限

オプションの 'MaxNumPaths'、'MaxPathLength'、および 'MinPathLength' を使用して、allpaths で返される経路の数を制限します。

20 個のノードをもつ完全グラフの隣接行列を作成します。隣接行列から、自己ループは省略して無向グラフを作成します。

A = ones(20);
G = graph(A,'omitselfloops');

グラフのすべてのノードが他のすべてのノードと連結されるため、どの 2 つのノードの間にもグラフに多数の経路が存在します (1.7e16 を超えます)。そのため、結果がメモリに収まらず、2 つのノード間のすべての経路を計算することは不可能です。代わりに、ノード 2 からノード 5 までの最初の 10 個の経路を計算します。

paths1 = allpaths(G,2,5,'MaxNumPaths',10)

paths1=10×1 cell array
    {[                       2 1 3 4 5]}
    {[                     2 1 3 4 6 5]}
    {[                   2 1 3 4 6 7 5]}
    {[                 2 1 3 4 6 7 8 5]}
    {[               2 1 3 4 6 7 8 9 5]}
    {[            2 1 3 4 6 7 8 9 10 5]}
    {[         2 1 3 4 6 7 8 9 10 11 5]}
    {[      2 1 3 4 6 7 8 9 10 11 12 5]}
    {[   2 1 3 4 6 7 8 9 10 11 12 13 5]}
    {[2 1 3 4 6 7 8 9 10 11 12 13 14 5]}

次に、ノード 2 とノード 5 の間の経路のうち、経路の長さが 2 以下である最初の 10 個の経路を計算します。

paths2 = allpaths(G,2,5,'MaxNumPaths',10,'MaxPathLength',2)

paths2=10×1 cell array
    {[ 2 1 5]}
    {[ 2 3 5]}
    {[ 2 4 5]}
    {[   2 5]}
    {[ 2 6 5]}
    {[ 2 7 5]}
    {[ 2 8 5]}
    {[ 2 9 5]}
    {[2 10 5]}
    {[2 11 5]}

最後に、ノード 2 とノード 5 の間の経路のうち、経路の長さが 3 以上である最初の 10 個の経路を計算します。

paths3 = allpaths(G,2,5,'MaxNumPaths',10,'MinPathLength',3)

paths3=10×1 cell array
    {[                       2 1 3 4 5]}
    {[                     2 1 3 4 6 5]}
    {[                   2 1 3 4 6 7 5]}
    {[                 2 1 3 4 6 7 8 5]}
    {[               2 1 3 4 6 7 8 9 5]}
    {[            2 1 3 4 6 7 8 9 10 5]}
    {[         2 1 3 4 6 7 8 9 10 11 5]}
    {[      2 1 3 4 6 7 8 9 10 11 12 5]}
    {[   2 1 3 4 6 7 8 9 10 11 12 13 5]}
    {[2 1 3 4 6 7 8 9 10 11 12 13 14 5]}

入力引数

G — 入力グラフ

graph オブジェクト | digraph オブジェクト

入力グラフ。graph オブジェクトまたは digraph オブジェクトとして指定します。無向グラフの作成には graph を、有向グラフの作成には digraph を使用します。

例: G = graph(1,2)

例: G = digraph([1 2],[2 3])

s, t — ソース ノードとターゲット ノードの ID (個別の引数として指定)

ノード インデックス | ノード名

ソース ノードとターゲット ノードの ID。ノード インデックスまたはノード名の個別の引数として指定します。

値	例
スカラー ノード インデックス	1
文字ベクトルのノード名	'A'
string スカラーのノード名	"A"

例: allpaths(G,2,5) は、ノード 2 とノード 5 の間のすべての経路を計算します。

例: allpaths(G,'node1','node2') は、名前付きノード node1 と node2 の間のすべての経路を計算します。

名前と値の引数

引数のオプションのペアを Name1=Value1,...,NameN=ValueN として指定します。ここで Name は引数名で、Value は対応する値です。名前と値の引数は他の引数の後になければなりませんが、ペアの順序は重要ではありません。

R2021a より前では、コンマを使用してそれぞれの名前と値を区切り、Name を引用符で囲みます。

例: allpaths(G,s,t,'MaxNumPaths',100) は、経路の辞書的順序に基づいて最初の 100 個の結果のみを返します。

MaxNumPaths — 経路の最大数

非負の整数スカラー

経路の最大数。'MaxNumPaths' と非負の整数スカラーで構成されるコンマ区切りのペアとして指定します。このオプションは、2 つのノード間の経路の数がメモリ制限に達するほど多くなる場合に便利です。MaxNumPaths を指定して、使用可能なメモリ内に結果が収まるように allpaths で返される経路の数を制限できます。

例: allpaths(G,s,t,'MaxNumPaths',100)

MaxPathLength — 最大の経路の長さ

非負の整数スカラー

最大の経路の長さ。'MaxPathLength' と非負の整数スカラーで構成されるコンマ区切りのペアとして指定します。このオプションは、長さが指定した制限を超える経路が返されないように allpaths で返される結果をフィルター処理します。経路の長さはエッジの数で測定され、エッジの重みは無視されます。

特定の範囲の長さの経路を検出するには、'MaxPathLength' と 'MinPathLength' の両方を指定します。指定した正確な長さの経路を検出するには、'MaxPathLength' と 'MinPathLength' の両方に同じ値を指定します。

例: allpaths(G,s,t,'MaxPathLength',4) は、長さが 4 以下の経路を返します。

例: allpaths(G,s,t,'MinPathLength',3,'MaxPathLength',5) は、長さが 3、4、5 の経路を返します。

MinPathLength — 最小の経路の長さ

非負の整数スカラー

最小の経路の長さ。'MinPathLength' と非負の整数スカラーで構成されるコンマ区切りのペアとして指定します。このオプションは、長さが指定した制限に満たない経路が返されないように allpaths で返される結果をフィルター処理します。経路の長さはエッジの数で測定され、エッジの重みは無視されます。

特定の範囲の長さの経路を検出するには、'MaxPathLength' と 'MinPathLength' の両方を指定します。指定した正確な長さの経路を検出するには、'MaxPathLength' と 'MinPathLength' の両方に同じ値を指定します。

例: allpaths(G,s,t,'MinPathLength',2) は、長さが 2 以上の経路を返します。

例: allpaths(G,s,t,'MinPathLength',3,'MaxPathLength',5) は、長さが 3、4、5 の経路を返します。

出力引数

paths — 指定したノード間の経路

cell 配列

指定したノード間の経路。cell 配列として返されます。各要素 paths{k} に、指定したソース ノードとターゲット ノードの間の 1 つの経路上にあるノードが格納されます。経路は辞書的順序で返されます。ソース ノード s とターゲット ノード t に同じノードを指定した場合、慣例により、allpaths はそのノードを含む単一の経路を返します。ノード t にノード s から到達できない場合、paths は空になります。

paths の項目のデータ型は、s および t の指定方法に応じて次のように異なります。

• s と t がノード インデックスの数値として指定されている場合、各要素 paths{k} はノード インデックスの数値ベクトルになります。

• s と t がノード名の string として指定されている場合、各要素 paths{k} はノード名の string 配列になります。

• s と t がノード名の文字ベクトルとして指定されている場合、各要素 paths{k} はノード名の文字ベクトルの cell 配列になります。

edgepaths — 各経路上のエッジ

cell 配列

各経路上のエッジ。cell 配列として返されます。各要素 edgepaths{k} に、対応する経路 paths{k} にあるエッジのエッジ インデックスが格納されます。ノード t にノード s から到達できない場合、edgepaths は空になります。

詳細

グラフの経路

グラフ内の "経路" とは、定義された開始ノードから定義された終了ノードに達するまでを辿ることができる、一連のグラフ エッジです。慣例として、経路に沿ったノードは固有でなければならないため、経路には繰り返されるノードまたはエッジは含まれません。

ヒント

• グラフ内の経路の数は、グラフの構造によって大きく異なります。一部のグラフ構造では、経路の数がノードの数に応じて指数関数的に多くなることがあります。たとえば、G = graph(ones(12)) で与えられる 12 個のノードをもつ完全グラフには、どの 2 つのノードの間にも 1,000 万個近い経路があります。このような場合は、MaxNumPaths、MaxPathLength、および MinPathLength の名前と値のペアを使用して allpaths の出力を制御します。

バージョン履歴

R2021a で導入

参考

allcycles | shortestpath | shortestpathtree | distances