allpaths
説明
[___] = allpaths(
は、1 つ以上の名前と値の引数を使用して追加のオプションを指定します。前述の構文にある任意の出力引数の組み合わせが使用できます。たとえば、G
,s
,t
,Name,Value
)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]}
入力引数
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 で導入
MATLAB コマンド
次の MATLAB コマンドに対応するリンクがクリックされました。
コマンドを MATLAB コマンド ウィンドウに入力して実行してください。Web ブラウザーは MATLAB コマンドをサポートしていません。
Select a Web Site
Choose a web site to get translated content where available and see local events and offers. Based on your location, we recommend that you select: .
You can also select a web site from the following list:
How to Get Best Site Performance
Select the China site (in Chinese or English) for best site performance. Other MathWorks country sites are not optimized for visits from your location.
Americas
- América Latina (Español)
- Canada (English)
- United States (English)
Europe
- Belgium (English)
- Denmark (English)
- Deutschland (Deutsch)
- España (Español)
- Finland (English)
- France (Français)
- Ireland (English)
- Italia (Italiano)
- Luxembourg (English)
- Netherlands (English)
- Norway (English)
- Österreich (Deutsch)
- Portugal (English)
- Sweden (English)
- Switzerland
- United Kingdom (English)