conncomp

グラフの連結要素

構文

bins = conncomp(G)

bins = conncomp(G,Name,Value)

[bins,binsizes] = conncomp(___)

説明

bins = conncomp(G) は、グラフ G の連結要素をビンとして返します。ビン番号はグラフの各ノードが属する要素を示します。

• G が無向グラフの場合、2 つのノードを連結する経路があれば、それらのノードは同じ要素に属します。

• G が有向グラフの場合、2 つのノードを双方向で連結する経路があるときに限り、それらのノードは同じ強要素に属します。

bins = conncomp(G,Name,Value) は、1 つ以上の名前と値のペアの引数で指定された追加のオプションを使用します。たとえば、conncomp(G,'OutputForm','cell') は連結要素を表す cell 配列を返します。

[bins,binsizes] = conncomp(___) は連結要素のサイズも返します。binsizes(i) は、要素 i のノード数を返します。

例

グラフの要素の検出

連結要素を 3 つもつ無向グラフを作成してプロットします。conncomp を使用して、各ノードが属する要素を求めます。

G = graph([1 1 4],[2 3 5],[1 1 1],6);
plot(G)

bins = conncomp(G)

bins = 1×6

     1     1     1     2     2     3

グラフの強要素と弱要素

有向グラフを作成してプロットし、強連結要素および弱連結要素を計算します。弱連結要素は、連結エッジの方向を無視します。

s = [1 2 2 3 3 3 4 5 5 5 8 8];
t = [2 3 4 1 4 5 5 3 6 7 9 10];
G = digraph(s,t);
plot(G,'Layout','layered')

str_bins = conncomp(G)

str_bins = 1×10

     4     4     4     4     4     6     5     1     3     2

weak_bins = conncomp(G,'Type','weak')

weak_bins = 1×10

     1     1     1     1     1     1     1     2     2     2

サイズに基づくグラフ要素の破棄

conncomp の 2 つ目の出力を使用して、グラフの最大要素を抽出するか、特定のサイズを下回る要素を削除します。

有向グラフを作成してプロットします。グラフには 1 つの大きな要素、1 つの小さい要素、および 1 つのノードのみを含む複数の要素があります。

s = [1 2 2 3 3 3 4 5 5 5 8 8 9];
t = [2 3 4 1 4 5 5 3 6 7 9 10 10];
G = digraph(s,t,[],20);
plot(G,'Layout','layered')

弱連結要素を計算し、conncomp に 2 つの出力を指定して各要素のサイズを取得します。

[bin,binsize] = conncomp(G,'Type','weak')

bin = 1×20

     1     1     1     1     1     1     1     2     2     2     3     4     5     6     7     8     9    10    11    12

binsize = 1×12

     7     3     1     1     1     1     1     1     1     1     1     1

binsize を使用してグラフから最大要素を抽出します。idx は、各ノードが最大要素に属しているかどうかを示す論理インデックスです。関数 subgraph は、idx で選択されたノードを G から抽出します。

idx = binsize(bin) == max(binsize);
SG = subgraph(G, idx);
plot(SG)

binsizes の同様の使用方法として、サイズに基づいて要素をフィルターで除外することがあります。この手順は最大要素の抽出と似ていますが、この場合は、各ノードが、サイズ要件を満たすどの要素にも属することができます。

ノードの数が 3 未満の G 内の要素をすべてフィルターで除外します。idx は、各ノードが 3 つ以上のノードをもつ要素に属するかどうかを示す論理インデックスです。

idx = binsize(bin) >= 3;
SG = subgraph(G, idx);
plot(SG)

入力引数

G — 入力グラフ

graph オブジェクト | digraph オブジェクト

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

例: G = graph(1,2)

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

名前と値の引数

オプションの引数のペアを Name1=Value1,...,NameN=ValueN として指定します。ここで、Name は引数名で、Value は対応する値です。名前と値の引数は他の引数の後に指定しなければなりませんが、ペアの順序は重要ではありません。

R2021a より前では、コンマを使用して名前と値をそれぞれ区切り、Name を引用符で囲みます。

例: bins = conncomp(G,'OutputForm','cell')

OutputForm — 出力のタイプ

'vector' (既定値) | 'cell'

出力のタイプ。'OutputForm' と 'vector' または 'cell' のいずれかで構成されるコンマ区切りのペアとして指定します。

オプション	出力
'vector' (既定)	bins は各ノードが属する連結要素を示す数値ベクトルです。
'cell'	bins は cell 配列であり、bins{j} は要素 j に属するすべてのノードのノード ID を含みます。

Type — 連結要素のタイプ。

'strong' (既定値) | 'weak'

メモ

'Type' オプションは、digraph を使用して作成された有向グラフでのみサポートされます。

連結要素のタイプ。'Type' と 'strong' (既定) または 'weak' のいずれかで構成されるコンマ区切りのペアとして指定されます。

オプション	結果
'strong' (既定)	2 つのノードを "双" 方向で連結する経路がある場合にのみ、それらのノードは同じ連結要素に属します。
'weak'	2 つのノードを連結する経路がある場合、それらのノードは同じ連結要素に属します。エッジの方向は無視されます。

例: bins = conncomp(G,'Type','weak') は、有向グラフ G の弱連結要素を計算します。

出力引数

bins — 連結要素

ベクトル | cell 配列

連結要素。ベクトルまたは cell 配列として返されます。ビン番号は、グラフの各ノードを連結要素に割り当てます。

• OutputForm が 'vector' (既定) の場合、bins は各ノードが属する連結要素 (ビン) を示す数値ベクトルです。

• OutputForm が 'cell' の場合、bins は cell 配列であり、bins{j} は要素 j に属するすべてのノードのノード ID を含みます。

binsizes — 各連結要素のサイズ

ベクトル

各連結要素のサイズ。ベクトルとして返されます。binsizes(i) は要素 i の要素数を返します。binsizes の長さは、連結要素 max(bins) の数と等しくなります。

詳細

弱連結要素

2 つのノードを連結する経路がある場合 (エッジの方向は無視)、それらのノードは同じ弱連結要素に属します。2 つの弱連結要素の間にはエッジがありません。

強要素と弱要素の概念は有向グラフにのみ適用されます。これは、無向グラフで強要素と弱要素は同等だからです。

強連結要素

2 つのノードを連結する双方向の経路がある場合、これらのノードは同じ強連結要素に属します。2 つの強連結要素の間にエッジが存在できますが、この連結エッジは絶対に循環の一部にはなりません。

強連結要素のビン番号は、2 つの要素を連結する任意のエッジが小さい方のビン番号をもつ要素から大きい方のビン番号をもつ要素を向くように付けられます。

強要素と弱要素の概念は有向グラフにのみ適用されます。これは、無向グラフで強要素と弱要素は同等だからです。

拡張機能

C/C++ コード生成

MATLAB® Coder™ を使用して C および C++ コードを生成します。

使用上の注意および制限:

• cell 配列出力を指定する名前と値の引数 'OutputForm','cell' はサポートされていません。

スレッドベースの環境
MATLAB® の backgroundPool を使用してバックグラウンドでコードを実行するか、Parallel Computing Toolbox™ の ThreadPool を使用してコードを高速化します。

バージョン履歴

R2015b で導入

参考

graph | digraph | subgraph