condensation

グラフの縮合

構文

C = condensation(G)

説明

C = condensation(G) は、ノードが G 内の強連結要素を表す有向グラフ C を返します。この削減により、要素間の連結の表示が簡略化されます。

例

強連結要素を単一ノードに縮合

いくつかの強連結要素を含むグラフを作成してプロットします。強連結要素を強調表示します。

s = [1 1 2 3 3 4 4 4 4 5 5 6 6 6 7 8 8 9 9 10 10 10 11 11 12 13 13 14 15];
t = [1 3 1 2 5 1 2 12 13 6 8 7 8 10 10 9 10 5 11 9 11 14 12 14 13 11 15 13 14];
G = digraph(s,t);
p = plot(G);

bins = conncomp(G);
p.MarkerSize = 7;
p.NodeCData = bins;
colormap(hsv(4))

condensation を使用して、各要素を単一ノードとして表します。それらが表す要素に基づいて、ノードに色を付けます。

C = condensation(G);
p2 = plot(C);
p2.MarkerSize = 7;
p2.NodeCData = 1:4;
colormap(hsv(4))

入力引数

G — 入力グラフ

digraph オブジェクト

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

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

出力引数

C — 縮合グラフ

digraph オブジェクト

縮合グラフ。digraph オブジェクトとして返されます。C は有向非循環グラフ (DAG) で、トポロジ的に並べ替えられます。C 内のノード番号は、conncomp によって返されるビン番号に対応します。

condensation は、G 内の要素と連結によって、C 内のノードとエッジを決定します。

• C には、G 内の各強連結要素のノードが含まれます。

• G の要素 I 内の任意のノードと要素 J 内の任意のノードとの間にエッジが存在する場合、C にはノード I とノード J との間のエッジが含まれます。

バージョン履歴

R2016b で導入

参考

conncomp | bctree

トピック

• 有向および無向グラフ
• 幅優先探索と深さ優先探索の可視化