simplify

多重グラフを単純グラフに縮小

構文

H = simplify(G)

H = simplify(G,pickmethod)

H = simplify(G,aggregatemethod)

H = simplify(___,selfloopflag)

H = simplify(___,Name,Value)

[H,eind,ecount] = simplify(___)

説明

H = simplify(G) は、複数のエッジまたは自己ループのないグラフを返します。同じ 2 つのノード間に複数のエッジがある場合、最初のエッジ (G.Edges で定義される) のみ維持されます。エッジのプロパティは保持されます。

H = simplify(G,pickmethod) は、複数のエッジの中からエッジを選択するメソッドを指定します。エッジのプロパティは保持されます。pickmethod には 'first' (既定値)、'last'、'min'、または 'max' を指定できます。

H = simplify(G,aggregatemethod) は、複数のエッジの重みを 1 つの新しいエッジの重みに結合するメソッドを指定します。G の他のエッジ プロパティはすべて破棄されます。aggregatemethod には 'sum' または 'mean' を指定できます。

H = simplify(___,selfloopflag) は、前の構文の入力引数のいずれかの組み合わせを使用して、グラフの自己ループを保持するか、削除するかを指定します。たとえば、'keepselfloops' は、簡略化されたグラフでは 1 つ以上の自己ループをもつノードが 1 つの自己ループをもつことを指定します。

H = simplify(___,Name,Value) は、1 つ以上の名前と値のペアの引数を使用して追加オプションを指定します。たとえば、G.Edges で 'PickVariable' と変数を指定し、その変数を 'min' または 'max' 選択メソッドとともに使用できます。

さらに、[H,eind,ecount] = simplify(___) はエッジ インデックス eind とエッジ カウント ecount を返します。

• H.Edges(eind(i),:) は、G のエッジ i を表す H のエッジです。

• ecount(j) は、H のエッジ j に対応する G のエッジ数です。

例

多重グラフを単純グラフに簡略化

ノード 1 とノード 2 の間に複数のエッジがある重み付けされた無向多重グラフを作成します。

G = graph([1 1 1 1 2 3],[2 2 2 3 3 4], 1:6);
G.Edges

ans=6×2 table
    EndNodes    Weight
    ________    ______

     1    2       1   
     1    2       2   
     1    2       3   
     1    3       4   
     2    3       5   
     3    4       6   

ノード 1 とノード 2 の間のエッジが 1 つのみになるように、多重グラフを単純グラフに簡略化します。simplify はこれら 2 つのノードの間にある最初のエッジ G.Edges(1,:) を保持し、他のエッジを破棄します。

G = simplify(G);
G.Edges

ans=4×2 table
    EndNodes    Weight
    ________    ______

     1    2       1   
     1    3       4   
     2    3       5   
     3    4       6   

複数のグラフ エッジの選択または結合

simplify の 2 番目の入力を使用して、複数のエッジからエッジを選択するメソッド、または複数のエッジを 1 つのエッジに結合するメソッドを選択します。

重み付き多重グラフを作成します。このグラフでは、ノード 3 とノード 4 間に 5 つのエッジがありますが、エッジの重みはランダムです。エッジ テーブルを表示し、参照用にグラフをプロットします。

G = graph([1 2 3 3 3 3 3 3 ],[2 3 1 4 4 4 4 4],randi(10,1,8));
G.Edges

ans=8×2 table
    EndNodes    Weight
    ________    ______

     1    2        9  
     1    3        2  
     2    3       10  
     3    4       10  
     3    4        7  
     3    4        1  
     3    4        3  
     3    4        6  

plot(G,'EdgeLabel',G.Edges.Weight)

コマンド simplify(G) は、繰り返されるエッジの 1 つ目を保持します。ただし、2 番目の入力で別の選択/結合メソッドを指定できます。

複数のエッジからエッジを選択するオプションは、'first' (既定値)、'last'、'min' および 'max' です。最大の重みをもつ繰り返されるエッジを維持します。

H_pick = simplify(G,'max');
plot(H_pick,'EdgeLabel',H_pick.Edges.Weight)

複数のエッジを 1 つのエッジに結合するオプションは、'sum' および 'mean' です。繰り返されるエッジを合計して、重みの大きい 1 つのエッジを生成します。

H_comb = simplify(G,'sum');
plot(H_comb,'EdgeLabel',H_comb.Edges.Weight)

グラフでの自己ループの保持

'keepselfloops' オプションを使用して自己ループを保持したまま、グラフを簡略化します。

2 つのノードと複数の自己ループを含む多重グラフを作成します。グラフを簡略化し、自己ループを保持します。

G = graph([1 1 1 1 1 1 1 2 2 2 2],[1 1 1 1 2 2 2 2 2 2 2 ]);
plot(G)
axis equal

G = simplify(G,'keepselfloops');
plot(G)
axis equal

繰り返されるエッジのエッジ インデックスとカウント

simplify の 2 番目および 3 番目の出力を使用して、結合されたエッジ数 (およびエッジ) に関する情報を取得します。

3 つのノードと 4 つのエッジを持つ無向多重グラフを作成します。

G = graph([1 1 1 2],[2 2 3 3]);
G.Edges

ans=4×1 table
    EndNodes
    ________

     1    2 
     1    2 
     1    3 
     2    3 

グラフを簡略化し、結合したエッジに関する追加情報を取得する 3 つの出力を指定します。

[G,ei,ec] = simplify(G)

G = 
  graph with properties:

    Edges: [3x1 table]
    Nodes: [3x0 table]

ei = 4×1

     1
     1
     2
     3

ec = 3×1

     2
     1
     1

ei(i) は、古いグラフ内のエッジ i を表す簡略化されたグラフ内のエッジです。最初の 2 本のエッジが繰り返されるため、ei(1) = ei(2) = 1 になります。また、古いグラフのエッジ 1 に対応する 2 本のエッジが新しいグラフにあるため、ec(1) = 2 になります。

特定のエッジ変数を使用したグラフの簡略化

'PickVariable' および 'AggregationVariables' の名前と値のペアを使用して多重グラフを簡略化する方法を説明します。

ノードが場所を表し、エッジが輸送のモードを表す多重グラフを作成します。エッジには、各輸送モードのコストと時間が反映されるプロパティがあります。エッジ テーブルをプレビューします。

G = graph([1 1 1 1 1 1 2 2 2],[2 2 2 3 3 3 3 3 3],[],{'New York', 'Boston', 'Washington D.C.'});
G.Edges.Mode = categorical([1 2 3 1 2 3 1 2 3],[1 2 3],{'Air' 'Train' 'Bus'})';
G.Edges.Cost = [400 80 40 250 100 75 325 150 100]';
G.Edges.Time = [1 7 5 1.5 10 8 1.75 11 9]';
G.Edges

ans=9×4 table
                 EndNodes                  Mode     Cost    Time
    ___________________________________    _____    ____    ____

    {'New York'}    {'Boston'         }    Air      400        1
    {'New York'}    {'Boston'         }    Train     80        7
    {'New York'}    {'Boston'         }    Bus       40        5
    {'New York'}    {'Washington D.C.'}    Air      250      1.5
    {'New York'}    {'Washington D.C.'}    Train    100       10
    {'New York'}    {'Washington D.C.'}    Bus       75        8
    {'Boston'  }    {'Washington D.C.'}    Air      325     1.75
    {'Boston'  }    {'Washington D.C.'}    Train    150       11
    {'Boston'  }    {'Washington D.C.'}    Bus      100        9

参照用にグラフをプロットします。各エッジで輸送モードにラベルを付け、エッジのライン幅が時間に比例し、各エッジの色がコストに比例するようにします。

plot(G,'EdgeLabel',cellstr(G.Edges.Mode),'LineWidth',G.Edges.Time./min(G.Edges.Time),'EdgeCData',G.Edges.Cost)
colorbar

'min' 選択メソッドを使用して 'PickVariable' の値を変数 'Time' に指定し、各ノード セット間で最も速い輸送モードを求めます。

t = simplify(G,'min','PickVariable','Time');
plot(t,'EdgeLabel',cellstr(t.Edges.Mode))

'sum' 集約メソッドを使用して 'AggregationVariables' の値を 'Cost' に指定し、各接続にかかる金額を計算します。

c = simplify(G,'sum','AggregationVariables','Cost');
plot(c,'EdgeLabel',c.Edges.Cost)

入力引数

G — 入力グラフ

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

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

例: G = graph(1,2)

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

pickmethod — エッジ選択メソッド

'first' (既定値) | 'last' | 'min' | 'max'

エッジ選択メソッド。'first'、'last'、'min'、または 'max' として指定します。エッジ選択メソッドでは、同じ 2 つのノード間に複数のエッジが存在する場合、どのエッジを保持するか選択できます。

• メソッドが 'first' または 'last' の場合、simplify はエッジ テーブル G.Edges で発生した最初のエッジまたは最後のエッジのみ保持します。

• メソッドが 'min' または 'max' の場合、simplify は重みが最小または最大のエッジのみ保持します。'PickVariable' 名前と値のペアを使用して別の変数に基づいて選択しない限り、変数 Weight は G.Edges に存在しなければなりません。

例: simplify(G,'last')

aggregatemethod — 集約メソッド

'sum' | 'mean'

集約メソッド。'sum' または 'mean' として指定します。集約メソッドでは、同じ 2 つのノード間に複数のエッジがある場合に、複数のエッジを 1 つのエッジに結合できます。

既定では、simplify はグラフ内のエッジの重みのみを合計または平均化し、他のエッジ プロパティをすべて破棄します。ただし、'AggregationVariables' 名前と値のペアを使用して、保持および集約する G.Edges 内の数値変数を指定できます。

例: simplify(G,'sum')

selfloopflag — 自己ループを維持するかどうかを指定する切り替え

'omitselfloops' (既定値) | 'keepselfloops'

自己ループを維持するかどうかを指定する切り替え。以下のいずれかとして指定します。

• 'omitselfloops' — グラフからすべての自己ループを削除します。これは既定値です。

• 'keepselfloops' — 1 つ以上の自己ループを含むノードは簡略化されたグラフで 1 つの自己ループをもちます。

例: simplify(G,'sum','keepselfloops')

名前と値の引数

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

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

例: H = simplify(G,'sum','AggregationVariables',{'Var1' 'Var2'})

PickVariable — エッジ選択の基になる変数

'Weight' (既定値) | 変数名 | 数値インデックス

エッジ選択の基になる変数。'PickVariable' および変数名または数値インデックスで構成されるコンマ区切りのペアとして指定します。この名前と値のペアを使用して、'Weight' ではなく G.Edges 内のエッジ変数を選択して 'min' または 'max' 選択メソッドとともに使用します。simplify は、同じ 2 つのノード間に複数のエッジがある場合、選択した変数の最小値または最大値をもつエッジのみ保持します。

例: simplify(G,'min','PickVariable',3)

例: simplify(G,'min','PickVariable','var3')

データ型: single | double | int8 | int16 | int32 | int64 | uint8 | uint16 | uint32 | uint64 | char | string

AggregationVariables — 集約する変数

'Weight' (既定値) | 変数名 | 変数名の cell 配列 | string 配列 | 数値ベクトル | logical ベクトル | 関数ハンドル

集約する変数。'AggregationVariables' と変数名、変数名の cell 配列、string 配列、数値ベクトル、logical ベクトル、または関数ハンドルで構成されるコンマ区切りのペアとして指定します。この名前と値のペアを使用して、'sum' 集約メソッドまたは 'mean' 集約メソッドと結合できる G.Edges 内の 1 つ以上のエッジ変数を選択します。simplify は、同じ 2 つのノード間に複数のエッジがあるときに、これらの変数の値を 1 つの新しいエッジの単一の値に結合します。'AggregationVariables' の値は、以下のいずれかになります。

• 単一の table 変数名を指定する文字ベクトル

• 各要素が table 変数名である文字ベクトルの cell 配列

• 1 つ以上の変数名を指定する string 配列

• table 変数インデックスのベクトル

• 各要素が table 変数に対応する logical ベクトル。true の場合は対応する変数を含めて、false の場合は対応する変数を除外します。

• 入力として G.Edges table をとり、@isnumeric などの logical スカラーを返す関数ハンドル

例: simplify(G,'sum','AggregationVariables',[4 5 6])

例: simplify(G,'mean','AggregationVariables',{'var5 var7'})

例: simplify(G,'mean','AggregationVariables',@isnumeric)

データ型: single | double | logical | function_handle | char | string | cell

出力引数

H — 簡略化されたグラフ

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

単純化されたグラフ。graph オブジェクトまたは digraph オブジェクトとして返されます。H は、同じ 2 つのノード間に繰り返されるエッジを含まないため、ismultigraph(H) は logical 0 (false) を返します。'keepselfloops' オプションを指定しない場合、自己ループも削除されます。

eind — エッジ インデックス

ベクトル

エッジ インデックス。ベクトルとして返されます。G 内のエッジ i を表す H 内のエッジが H.Edges(eind(i),:) で与えられます。G 内のエッジ i が、削除された自己ループである場合、eind(i) は 0 になります。

ecount — エッジ カウント

ベクトル

エッジ カウント。ベクトルとして返されます。ecount(i) は、H 内のエッジ i に対応する G 内のエッジの数です。

拡張機能

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

バージョン履歴

R2018a で導入

参考

graph | digraph | ismultigraph