toposort

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

構文

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)

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

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)

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

入力引数

G — 入力グラフ

digraph オブジェクト

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

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

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

algorithm — 順序付けアルゴリズム

'fast' (既定値) | 'stable'

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

'fast' (既定)	深さ優先検索に基づきます。ノードは、すべての下位ノードを考慮した後にリストの先頭に追加されます。 G が既にトポロジカル順序になっている場合でも、このメソッドによってノードが並べ替えられることがあります。
'stable'	辞書的な順序に基づきます。n(1) は最小のインデックスをもつノード、n(2) は n(1) の次の最小のインデックスをもつノード、などと続きます。 G がトポロジカル順序になっている場合、H は変化せず、n は 1:numnodes(G) です。

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

出力引数

n — ノード インデックス

行ベクトル

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

H — トポロジカルにソートされたグラフ

digraph オブジェクト

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

詳細

トポロジカル順序

有向グラフのトポロジカル順序とは、グラフ内の各ノードが後続 (下位) ノードの前に現れるノードの順序です。

タスクを表すノードと、特定のタスクを他のタスクより前に完了しなければならない依存関係を表すエッジをもつ有向グラフについて考えます。そのようなグラフでは、グラフ ノードのトポロジカル ソートにより、タスクを実行する有効な順序が得られます。

バージョン履歴

R2015b で導入

参考

digraph | isdag | reordernodes