このページの内容は最新ではありません。最新版の英語を参照するには、ここをクリックします。

toposort

R2026a

有向非循環グラフのトポロジカル順序

ページ内をすべて折りたたむ

構文

n = toposort(G)
n = toposort(G,'Order',algorithm)
[n,H] = toposort(___)

説明

n = toposort(G) は、G の各エッジ (n(i),n(j)) について i < j となる、G のノードのトポロジカル順序を返します。有向グラフ G に循環は設けられません。

例

n = toposort(G,'Order',algorithm) は順序付けアルゴリズムを指定します。たとえば、toposort(G,'Order','stable') は、ノードの辞書的順序に基づく安定的な順序付けアルゴリズムを使用します。

例

[n,H] = toposort(___) はさらに、指定されたトポロジカル順序のノードをもつ有向グラフ H を返します。前述の構文にある任意の入力引数の組み合わせが使用できます。

例

例

すべて折りたたむ

ライブ スクリプトを開く

大学レベルの数学課程の進行を表すグラフを作成し、プロットします。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)

Figure contains an axes object. The axes object contains an object of type graphplot.

課程のトポロジカル ソートを行い、課程を修了する適切な順序を決定します。

N = toposort(G)
N = 1×7

     1     3     7     2     4     6     5


G.Nodes.Name(N,:)
ans = 7×1 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)

Figure contains an axes object. The axes object contains an object of type graphplot.

グラフ ノードのトポロジカル ソートを行います。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

入力引数

すべて折りたたむ

入力グラフ。digraph オブジェクトとして指定します。G は有向非循環グラフでなければなりません。G が循環を含まないことを確認するには、isdag を使用します。

有向グラフを作成するには、digraph を使用します。

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

順序付けアルゴリズム。'fast' または 'stable' として指定します。

'fast' (既定)

深さ優先検索に基づきます。ノードは、すべての下位ノードを考慮した後にリストの先頭に追加されます。

G が既にトポロジカル順序になっている場合でも、このメソッドによってノードが並べ替えられることがあります。

'stable'

辞書的な順序に基づきます。n(1) は最小のインデックスをもつノード、n(2) は n(1) の次の最小のインデックスをもつノード、などと続きます。

G がトポロジカル順序になっている場合、H は変化せず、n は 1:numnodes(G) です。

例: [n,H] = toposort(G,'Order','stable')

出力引数

すべて折りたたむ

ノード インデックス。行ベクトルとして返されます。

トポロジカルにソートされたグラフ。digraph オブジェクトとして返されます。H は G と同じグラフですが、n に従ってノードが並べ替えられています。

詳細

すべて折りたたむ

バージョン履歴

R2015b で導入

参考

| |