toposort
有向非循環グラフのトポロジカル順序
説明
例
ノードのトポロジカル ソート
大学レベルの数学課程の進行を表すグラフを作成し、プロットします。2 つの課程を結ぶエッジは受講要件を表します。
A = [0 1 1 0 0 0 0 0 0 0 1 0 0 0 0 1 0 1 0 0 1 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0]; names = {'Calculus I','Linear Algebra','Calculus II', ... 'Multivariate Calculus','Topology', ... 'Differential Equations','Real Analysis'}; G = digraph(A,names); plot(G)
課程のトポロジカル ソートを行い、課程を修了する適切な順序を決定します。
N = toposort(G)
N = 1×7
1 3 7 2 4 6 5
G.Nodes.Name(N,:)
ans = 7x1 cell
{'Calculus I' }
{'Calculus II' }
{'Real Analysis' }
{'Linear Algebra' }
{'Multivariate Calculus' }
{'Differential Equations'}
{'Topology' }
安定的トポロジカル ソート
論理隣接行列を使用して有向グラフを作成し、それをプロットします。
rng default;
A = tril(sprand(10, 10, 0.3), -1)~=0;
G = digraph(A);
[~,G] = toposort(G);
plot(G)
グラフ ノードのトポロジカル ソートを行います。G
は既に (1 2 3 4 5 6 7 8 9 10)
のトポロジカル順序になっていますが、toposort
はノードを並べ替えます。
toposort(G)
ans = 1×10
2 1 4 10 9 8 5 7 3 6
Order
を 'stable'
として指定し、安定的順序付けアルゴリズムを使用します。この並べ替えにより、インデックスの小さい順にノードが並べられます。安定的並べ替えでは、既にトポロジカル順序になっている G
は並べ替えられません。
toposort(G,'Order','stable')
ans = 1×10
1 2 3 4 5 6 7 8 9 10
入力引数
algorithm
— 順序付けアルゴリズム
'fast'
(既定値) | 'stable'
順序付けアルゴリズム。'fast'
または 'stable'
として指定します。
'fast' (既定) | 深さ優先検索に基づきます。ノードは、すべての下位ノードを考慮した後にリストの先頭に追加されます。
|
'stable' | 辞書的な順序に基づきます。
|
例: [n,H] = toposort(G,'Order','stable')
出力引数
n
— ノード インデックス
行ベクトル
ノード インデックス。行ベクトルとして返されます。
H
— トポロジカルにソートされたグラフ
digraph
オブジェクト
トポロジカルにソートされたグラフ。digraph
オブジェクトとして返されます。H
は G
と同じグラフですが、n
に従ってノードが並べ替えられています。
詳細
トポロジカル順序
有向グラフのトポロジカル順序とは、グラフ内の各ノードが後続 (下位) ノードの前に現れるノードの順序です。
タスクを表すノードと、特定のタスクを他のタスクより前に完了しなければならない依存関係を表すエッジをもつ有向グラフについて考えます。そのようなグラフでは、グラフ ノードのトポロジカル ソートにより、タスクを実行する有効な順序が得られます。
バージョン履歴
R2015b で導入
参考
digraph
| isdag
| reordernodes
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)