digraph

有向エッジをもつグラフ

説明

digraph オブジェクトは、方向性をもつエッジによりノードが連結されている有向グラフを表します。digraph オブジェクトの作成後、そのオブジェクトに対しオブジェクト関数を使用してクエリを実行することで、グラフについて詳細を知ることができます。たとえば、ノードまたはエッジの追加や削除、2 つのノード間の最短経路の特定、特定のノードやエッジの検出ができます。

G = digraph([1 1], [2 3])
e = G.Edges
G = addedge(G,2,3)
G = addnode(G,4)
plot(G)

作成

構文

G = digraph

G = digraph(A)

G = digraph(A,nodenames)

G = digraph(A,NodeTable)

G = digraph(A,___,'omitselfloops')

G = digraph(s,t)

G = digraph(s,t,weights)

G = digraph(s,t,weights,nodenames)

G = digraph(s,t,weights,NodeTable)

G = digraph(s,t,weights,num)

G = digraph(s,t,___,'omitselfloops')

G = digraph(s,t,EdgeTable,___)

G = digraph(EdgeTable)

G = digraph(EdgeTable,NodeTable)

G = digraph(EdgeTable,___,'omitselfloops')

説明

G = digraph は、ノードとエッジをもたない空の有向グラフ オブジェクト G を作成します。

G = digraph(A) は、正方隣接行列 A を使用して有向グラフを作成します。

• 論理隣接行列の場合は、エッジの重みがないグラフになります。

• 非論理隣接行列の場合は、エッジの重みがあるグラフになります。A の各非ゼロ要素の位置はグラフのエッジを指定し、エッジの重みは要素の値に等しくなります。たとえば、A(2,1) = 10 である場合、G には、ノード 2 からノード 1 に向かう重み 10 のエッジがあります。

G = digraph(A,nodenames) はさらにノード名を指定します。nodenames の要素数は size(A,1) と等しくなければなりません。

G = digraph(A,NodeTable) は、table NodeTable を使用してノード名を (可能な場合は他のノード属性も) 指定します。この table は、A と同じ行数でなければなりません。table 変数 Name を使用してノード名を指定します。

G = digraph(A,___,'omitselfloops') は A の対角要素を無視し、自己ループのないグラフを返します。前述の構文にある任意の入力引数の組み合わせが使用できます。

G = digraph(s,t) は、有向グラフのエッジ (s,t) をソース ノードとターゲット ノードを表すペアで指定します。s と t は、ノード インデックスまたはノード名を指定できます。digraph は、G 内のエッジをまずソース ノードで並べ替えてから、ターゲット ノードで並べ替えます。s および t と同じ順序のエッジ プロパティがある場合は、構文 G = digraph(s,t,EdgeTable) を使用してエッジ プロパティを渡し、結果のグラフで同じように並べ替えられるようにします。

G = digraph(s,t,weights) は、配列 weights によってエッジの重みも指定します。

G = digraph(s,t,weights,nodenames) はさらに、文字ベクトルの cell 配列または string 配列 nodenames を使用してノード名を指定します。s と t には nodenames に存在しないノード名を含めることはできません。

G = digraph(s,t,weights,NodeTable) は、table NodeTable を使用してノード名を (可能な場合は他のノード属性も) 指定します。table 変数 Name を使用してノード名を指定します。s と t には NodeTable に存在するノード名のみを含めることができます。

G = digraph(s,t,weights,num) は、数値スカラー num によってグラフ内のノード数を指定します。

G = digraph(s,t,___,'omitselfloops') は自己ループをグラフに追加しません。つまり、s(k) == t(k) を満たす k はすべて無視されます。前述の構文にある任意の入力引数の組み合わせが使用できます。

G = digraph(s,t,EdgeTable,___) は、weights を指定する代わりに table を使用してエッジの属性を指定します。EdgeTable の入力は table で、その行はそれぞれ s と t の要素のペアに対応しなければなりません。table 変数 Weight を使用してエッジの重みを指定します。

G = digraph(EdgeTable) は、table EdgeTable を使用してグラフを定義します。この構文の場合、EdgeTable の最初の変数は EndNodes という名前で、グラフ エッジのリストを定義する 2 列配列でなければなりません。

G = digraph(EdgeTable,NodeTable) は、さらに table NodeTable を使用してグラフ ノードの名前を (可能な場合はその他の属性も) 指定します。

G = digraph(EdgeTable,___,'omitselfloops') は自己ループをグラフに追加しません。つまり、EdgeTable.EndNodes(k,1) == EdgeTable.EndNodes(k,2) を満たす k はすべて無視されます。EdgeTable の指定は必須です。NodeTable はオプションで指定できます。

入力引数

A — 隣接行列

行列

隣接行列。非スパースまたはスパースの数値行列として指定します。A の要素は、グラフのノード間における連結 (エッジ) のネットワークを指定します。A の個々の非ゼロ要素の位置は、2 つのノード間のエッジを指定します。その要素の値はエッジの重みです。論理隣接行列は重みなしのグラフになります。

A の非ゼロの主対角要素は、"自己ループ"、つまりエッジでそれ自体に連結するノードを指定します。対角要素を無視するには、入力オプション 'omitselfloops' を使用します。

例: A = [0 1 0; 0 0 0; 5 0 0] は、ノードを 3 つ、エッジを 2 本もつグラフを表します。ノード 1 からノード 2 へのエッジの重みは 1、ノード 3 からノード 1 へのエッジの重みは 5 です。

データ型: single | double | logical

nodenames — ノード名

文字ベクトルの cell 配列 | string 配列

ノード名。文字ベクトルの cell 配列または string 配列として指定します。nodenames は、グラフの各ノードに対して空ではない一意の名前が含まれるように、numnodes(G) と長さが同じでなければなりません。

例: G = digraph(A,{'n1','n2','n3'}) は、3 行 3 列の隣接行列 A に対し 3 つのノード名を指定します。

データ型: cell | string

s,t — ソース ノードとターゲット ノードのペア (個別の引数として指定)

ノード インデックス | ノード名

ソース ノードとターゲット ノードのペア。ノード インデックスまたはノード名として指定します。digraph は s と t の対応するノード間に有向エッジを作成します。s と t はどちらも数値であるか、どちらも文字ベクトル、文字ベクトルの cell 配列、categorical 配列、または string 配列でなければなりません。すべての場合において、s と t の要素数は同じでなければなりません。

• s と t が数値の場合、その値はグラフ ノードのインデックスに対応します。数値のノード インデックスは、1 以上の正の整数でなければなりません。

• s と t が文字ベクトル、文字ベクトルの cell 配列または string 配列である場合、ノード名を指定します。グラフの Nodes プロパティは、ノード名 Name をもつ変数 G.Nodes.Name のテーブルです。

• s と t が categorical 配列の場合、s と t のカテゴリがグラフ内のノード名として使用されます。これには、s または t の要素ではないカテゴリが含まれる場合があります。

• s および t で同じ 2 つのノード間の複数のエッジを指定すると、結果は、多重グラフになります。

次の表に、1 つ以上のノードを数値ノード インデックスまたはノード名のいずれかで参照するさまざまな方法を示します。

形式	単一ノード	複数ノード
ノード インデックス	スカラー 例: 1	ベクトル 例: [1 2 3]
ノード名	文字ベクトル 例: 'A'	文字ベクトルの cell 配列 例: {'A' 'B' 'C'}
	string スカラー 例: "A"	string 配列 例: ["A" "B" "C"]
	categorical 配列 例: categorical("A")	categorical 配列 例: categorical(["A" "B" "C"])

例: G = digraph([1 2 3],[2 4 5]) はノードを 5 つ、エッジを 3 本もつグラフを作成します。

例: G = digraph({'Boston' 'New York' 'Washington D.C.'},{'New York' 'New Jersey' 'Pittsburgh'}) は名前付きノードを 5 つ、エッジを 3 本もつグラフを作成します。

weights — エッジの重み

スカラー | ベクトル | 行列 | 多次元配列 | []

エッジの重み。スカラー、ベクトル、行列または多次元配列として指定します。weights には、スカラー、または s および t と同じ要素数の配列を指定しなければなりません。

digraph は、G.Edges プロパティ テーブルの変数 Weight としてエッジの重みを格納します。グラフの作成後に重みの追加や変更を行うために、たとえば G.Edges.Weight = [25 50 75]' のように、table 変数を直接変更できます。

weights を空の配列 [] として指定した場合、これは無視されます。

例: G = digraph([1 2],[2 3],[100 200]) は、ノードを 3 つ、エッジを 2 本もつグラフを作成します。エッジの重みはそれぞれ 100 と 200 です。

データ型: single | double

num — グラフ ノードの数

正のスカラー整数

グラフ ノードの数。正のスカラー整数として指定します。num は、s と t の要素の最大数以上の値でなければなりません。

例: G = digraph([1 2],[2 3],[],5) は連結ノードを 3 つ、孤立ノードを 2 つもつグラフを作成します。

EdgeTable — エッジ情報のテーブル

table

エッジ情報のテーブル。s および t を指定しない場合は、EdgeTable の最初の変数を、グラフ エッジを定義する EndNodes という 2 列の行列、文字ベクトルの cell 配列または string 配列にする必要があります。エッジの重みには、変数 Weight を使用します。これは、このテーブル変数名が一部のグラフ関数で使用されているためです。変数 Weight がある場合、これは数値列ベクトルにしなければなりません。table の作成の詳細については、table を参照してください。

グラフの作成後、G.Edges を使用してエッジ情報のテーブルをクエリします。

例: EdgeTable = table([1 2; 2 3; 3 5; 4 5],'VariableNames',{'EndNodes'})

データ型: table

NodeTable — ノード情報のテーブル

table

ノード情報のテーブル。NodeTable には、グラフ ノードの属性を記述する変数をいくつでも含めることができます。ノード名には、変数 Name を使用します。これは、この変数名が一部のグラフ関数で使用されるためです。変数 Name がある場合、これは各行で一意の名前を指定する文字ベクトルの cell 配列または string 配列でなければなりません。table の作成の詳細については、table を参照してください。

グラフの作成後、G.Nodes を使用してノード情報のテーブルをクエリします。

例: NodeTable = table({'a'; 'b'; 'c'; 'd'},'VariableNames',{'Name'})

データ型: table

プロパティ

Edges — グラフのエッジ

table

グラフのエッジ。table として返されます。既定では、これは M 行 1 列のテーブルであり、ここで M はグラフのエッジ数です。G.Edges.EndNodes 内のエッジ リストは、まずソース ノードで並べ替えてから、ターゲット ノードで並べ替えます。

• グラフに新しいエッジ プロパティを追加するには、Edges テーブルに新しい変数を作成します。

• グラフにエッジを追加するにはオブジェクト関数 addedge を、グラフからエッジを削除するにはオブジェクト関数 rmedge を使用します。

例: G.Edges はグラフ内のエッジがリストされたテーブルを返します。

例: G.Edges.Weight はエッジの重みの数値ベクトルを返します。

例: G.Edges.Weight = [10 20 30 55]' は、グラフの新しいエッジの重みを指定します。

例: G.Edges.NormWeight = G.Edges.Weight/sum(G.Edges.Weight) は、エッジの正規化された重みを含む新しいエッジ プロパティを table に追加します。

データ型: table

Nodes — グラフのノード

table

グラフのノード。table として返されます。既定では、これは N 行 0 列の空のテーブルであり、ここで N はグラフのノード数です。

• グラフに新しいノード プロパティを追加するには、Nodes テーブルに新しい変数を作成します。

• グラフにノードを追加するにはオブジェクト関数 addnode を、グラフからノードを削除するにはオブジェクト関数 rmnode を使用します。

例: G.Nodes は、グラフのノード プロパティがリストされたテーブルを返します。このテーブルは既定では空です。

例: G.Nodes.Names = {'Montana', 'New York', 'Washington', 'California'}' は、Nodes table に変数 Names を追加することにより、グラフにノード名を追加します。

例: G.Nodes.WiFi = logical([1 0 0 1 1]') は、変数 WiFi を Nodes テーブルに追加します。このプロパティは、特定の空港にワイヤレス インターネットのサービス エリアがあることを示します。

データ型: table

オブジェクト関数

ノードとエッジの変更

addedge	新しいエッジをグラフに追加
rmedge	グラフからエッジを削除
flipedge	エッジの方向の反転
addnode	新しいノードをグラフに追加
rmnode	グラフからノードを削除
findedge	グラフ内のエッジを検出
findnode	グラフ内のノードを検出
numedges	グラフ エッジの数
numnodes	グラフのノード数
edgecount	2 つのノード間のエッジ数
reordernodes	グラフ ノードの並べ替え
subgraph	部分グラフの抽出

構造の解析

centrality	ノードの重要度を測定
toposort	有向非循環グラフのトポロジカル順序
transclosure	推移閉包
transreduction	推移還元
isdag	グラフが非循環かどうかの判定
conncomp	グラフの連結要素
condensation	グラフの縮合
maxflow	グラフの最大フロー
isisomorphic	2 つのグラフが準同型であるかどうかを判別
isomorphism	2 つのグラフ間の同型を計算
ismultigraph	グラフに複数のエッジがあるかどうかを判別
simplify	多重グラフを単純グラフに縮小

トラバーサル、最短経路および循環

bfsearch	グラフの幅優先検索
dfsearch	グラフの深さ優先検索
shortestpath	2 つの単一ノード間の最短経路
shortestpathtree	ノードからの最短経路木
distances	すべてのノード ペアの最短経路の距離
allpaths	2 つのグラフ ノード間のすべての経路の検出
hascycles	グラフに循環があるかどうかを判別
allcycles	グラフ内のすべての循環の検出

行列表現

adjacency	グラフの隣接行列
incidence	グラフの接続行列

ノード情報

indegree	ノードの入次数
outdegree	ノードの出次数
predecessors	先行ノード
successors	後続ノード
nearest	半径内の最近傍
inedges	ノードの入方向エッジ
outedges	ノードからの出方向のエッジ

可視化

plot	グラフのノードとエッジをプロット

例

digraph オブジェクトの作成および変更

ノードを 3 つ、エッジを 3 本もつ digraph オブジェクトを作成します。1 つのエッジはノード 1 からノード 2 へ、別のエッジはノード 1 からノード 3 へ、3 番目のエッジはノード 2 からノード 1 へとつながります。

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

G = 
  digraph with properties:

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

グラフのエッジ テーブルを表示します。有向グラフの場合、1 列目は各エッジのソース ノード、2 列目はターゲット ノードを示します。

G.Edges

ans=3×1 table
    EndNodes
    ________

     1    2 
     1    3 
     2    1 

ノード名をグラフに追加し、新しいノード テーブルとエッジ テーブルを表示します。各エッジのソース ノードとターゲット ノードが、ノード名を使用して表されます。

G.Nodes.Name = {'A' 'B' 'C'}';
G.Nodes

ans=3×1 table
    Name 
    _____

    {'A'}
    {'B'}
    {'C'}

G.Edges

ans=3×1 table
       EndNodes   
    ______________

    {'A'}    {'B'}
    {'A'}    {'C'}
    {'B'}    {'A'}

テーブル Nodes および Edges に変数を追加し、あるいはそれを変更して、グラフのノードやエッジの属性を記述することができます。ただし、これらのテーブルを変更してグラフ内のノード数やエッジ数を直接変更することはできません。代わりに、関数 addedge、rmedge、addnode または rmnode を使用してグラフ内のノード数またはエッジ数を変更します。

たとえば、グラフのノード 2 とノード 3 の間にエッジを追加し、新しいエッジ リストを表示します。

G = addedge(G,2,3)

G = 
  digraph with properties:

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

G.Edges

ans=4×1 table
       EndNodes   
    ______________

    {'A'}    {'B'}
    {'A'}    {'C'}
    {'B'}    {'A'}
    {'B'}    {'C'}

隣接行列によるグラフの作成

次数 4 の完全有向グラフを作成する対称隣接行列 A を作成します。論理隣接行列を使用して、重みのないグラフを作成します。

A = ones(4) - diag([1 1 1 1])

A = 4×4

     0     1     1     1
     1     0     1     1
     1     1     0     1
     1     1     1     0

G = digraph(A~=0)

G = 
  digraph with properties:

    Edges: [12x1 table]
    Nodes: [4x0 table]

グラフのエッジ リストを表示します。

G.Edges

ans=12×1 table
    EndNodes
    ________

     1    2 
     1    3 
     1    4 
     2    1 
     2    3 
     2    4 
     3    1 
     3    2 
     3    4 
     4    1 
     4    2 
     4    3 

ノード名を指定した隣接行列による作成

隣接行列を作成します。

A = magic(4);
A(A>10) = 0

A = 4×4

     0     2     3     0
     5     0    10     8
     9     7     6     0
     4     0     0     1

この隣接行列を使用して、名前付きノードをもつグラフを作成します。'omitselfloops' を指定して、A の対角要素を無視します。

names = {'alpha' 'beta' 'gamma' 'delta'};
G = digraph(A,names,'omitselfloops')

G = 
  digraph with properties:

    Edges: [8x2 table]
    Nodes: [4x1 table]

エッジとノードの情報を表示します。

G.Edges

ans=8×2 table
           EndNodes           Weight
    ______________________    ______

    {'alpha'}    {'beta' }       2  
    {'alpha'}    {'gamma'}       3  
    {'beta' }    {'alpha'}       5  
    {'beta' }    {'gamma'}      10  
    {'beta' }    {'delta'}       8  
    {'gamma'}    {'alpha'}       9  
    {'gamma'}    {'beta' }       7  
    {'delta'}    {'alpha'}       4  

G.Nodes

ans=4×1 table
      Name   
    _________

    {'alpha'}
    {'beta' }
    {'gamma'}
    {'delta'}

エッジ リストによるグラフの作成

各エッジの末端ノードのリストを使用して立方体グラフを作成し、プロットします。

s = [1 1 1 2 2 3 3 4 5 5 6 7];
t = [2 4 8 3 7 4 6 5 6 8 7 8];
G = digraph(s,t)

G = 
  digraph with properties:

    Edges: [12x1 table]
    Nodes: [8x0 table]

plot(G,'Layout','force')

ノード名とエッジの重みを指定したエッジ リストによるグラフの作成

各エッジの末端ノードのリストを使用して立方体グラフを作成し、プロットします。ノード名とエッジの重みを別々の入力として指定します。

s = [1 1 1 2 2 3 3 4 5 5 6 7];
t = [2 4 8 3 7 4 6 5 6 8 7 8];
weights = [10 10 1 10 1 10 1 1 12 12 12 12];
names = {'A' 'B' 'C' 'D' 'E' 'F' 'G' 'H'};
G = digraph(s,t,weights,names)

G = 
  digraph with properties:

    Edges: [12x2 table]
    Nodes: [8x1 table]

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

追加のノードを指定したエッジ リストによる作成

各エッジの末端ノードのリストを使用して、重み付きグラフを作成します。グラフに合計 10 個のノードが含まれるよう指定します。

s = [1 1 1 1 1];
t = [2 3 4 5 6];
weights = [5 5 5 6 9];
G = digraph(s,t,weights,10)

G = 
  digraph with properties:

    Edges: [5x2 table]
    Nodes: [10x0 table]

グラフをプロットします。追加のノードは、主要な連結要素と連結されていません。

plot(G)

空のグラフにノードとエッジを追加

空の digraph オブジェクト G を作成します。

G = digraph;

このグラフにノードを 3 つ、エッジを 3 本追加します。s と t の対応する要素は、エッジのソース ノードとターゲット ノードを定義します。それらがまだ存在していない場合、addedge は適切なノードをグラフに自動的に追加します。

s = [1 2 1];
t = [2 3 3];
G = addedge(G,s,t)

G = 
  digraph with properties:

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

エッジ リストを表示します。各行はグラフのエッジを表します。

G.Edges

ans=3×1 table
    EndNodes
    ________

     1    2 
     1    3 
     2    3 

最高のパフォーマンスを得るには、digraph の呼び出しを 1 回使用してグラフをすべて一度に作成します。大規模なグラフでは、ループを使用してノードやエッジをグラフに追加する処理が低速になることがあります。

テーブルを使用したグラフの作成

変数 EndNodes、Weight および Code を格納するエッジ テーブルを作成します。次に、変数 Name および Country を格納するノード テーブルを作成します。各テーブルの変数は、グラフのノードとエッジのプロパティを指定します。

s = [1 1 1 2 2 3];
t = [2 3 4 3 4 4];
weights = [6 6.5 7 11.5 12 17]';
code = {'1/44' '1/49' '1/33' '44/49' '44/33' '49/33'}';
EdgeTable = table([s' t'],weights,code, ...
    'VariableNames',{'EndNodes' 'Weight' 'Code'})

EdgeTable=6×3 table
    EndNodes    Weight      Code   
    ________    ______    _________

     1    2         6     {'1/44' }
     1    3       6.5     {'1/49' }
     1    4         7     {'1/33' }
     2    3      11.5     {'44/49'}
     2    4        12     {'44/33'}
     3    4        17     {'49/33'}

names = {'USA' 'GBR' 'DEU' 'FRA'}';
country_code = {'1' '44' '49' '33'}';
NodeTable = table(names,country_code,'VariableNames',{'Name' 'Country'})

NodeTable=4×2 table
     Name      Country
    _______    _______

    {'USA'}    {'1' } 
    {'GBR'}    {'44'} 
    {'DEU'}    {'49'} 
    {'FRA'}    {'33'} 

ノード テーブルとエッジ テーブルを使用して、グラフを作成します。国コードをノード ラベルとエッジ ラベルとして使用して、グラフをプロットします。

G = digraph(EdgeTable,NodeTable);
plot(G,'NodeLabel',G.Nodes.Country,'EdgeLabel',G.Edges.Code)

拡張機能

C/C++ コード生成

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

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

• ノード名はサポートされていません。代わりにノード インデックスを使用してください。

• エッジ リストの作成でスパース入力はサポートされていません。

• digraph オブジェクトのコード生成でサポートされるオブジェクト関数は、addedge、addnode、adjacency、conncomp、degree、edgecount、indegree、inedges、neighbors、numedges、numnodes、outdegree、outedges、predecessors、rmnode、rmedge、subgraph、successors のみです。

• digraph オブジェクトの保存と読み込みはサポートされていません。

• コード生成時に可変サイズのエッジの重みを指定した場合、実行時に空の重みベクトルが与えられると、table G.Edges に含まれる Weight 変数に 1 のベクトルが格納されます。

• エッジとノードのプロパティについては、digraph オブジェクトの作成時に数とタイプを指定する必要があります。エッジとノードのプロパティに addnode または addedge を使用して新しい変数を追加することはできません。つまり、table G.Edges および G.Nodes に新しい列を追加することはできません。

• MATLAB^® で作成した digraph オブジェクトを MATLAB Coder™ を使用して生成された MEX 関数に渡すときに、digraph オブジェクトのエッジやノードを追加または削除することはできません。

• エッジとノードのプロパティは、コード生成で可変サイズの配列として格納できるデータ型でなければなりません。たとえば、次のデータ型にすることはできません。

  • string 配列

  • cell ごとにサイズが異なる cell 配列

  • cellstr を使用して変換される文字ベクトルの cell 配列

  • ユーザー定義クラス

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

バージョン履歴

R2015b で導入

R2019a: categorical ノード名のサポート

categorical ノード名が入力としてサポートされるようになりました。これにより、categorical としてインポートされたデータを使用してグラフが作成できるようになり、データ型の操作は不要になりました。

R2018a: 重複したエッジの処理の変更

graph、digraph および addedge は、重複したエッジを検出してもエラーを生成しません。代わりに、重複したエッジはグラフに追加され、結果として多重グラフになります。関数 ismultigraph はこの状況を検出するのに役立ち、simplify は余分なエッジを簡単に削除する方法となります。

参考

graph | subgraph

トピック

• ワッツ・ストロガッツのスモール ワールド グラフのモデル作成
• PageRank アルゴリズムを使用した Web サイトのランク付け
• 有向および無向グラフ
• 既存グラフのノードとエッジの変更
• グラフのノード名、エッジの重みおよび他の属性の追加
• グラフのプロットおよびカスタマイズ