Main Content

digraph

具备有向边的图

说明

digraph 对象表示有向图,有向图具有连接相应节点的有向边。创建 digraph 对象后,您可以通过使用对象函数针对对象执行查询,了解有关图的详细信息。例如,您可以添加或删除节点或边、确定两个节点之间的最短路径,或定位特定的节点或边。

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

创建对象

描述

示例

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) 使用表 NodeTable 指定节点名称(以及其他可能的节点属性)。此表和 A 的行数必须相同。使用表变量 Name 指定节点名称。

示例

G = digraph(A,___,'omitselfloops') 忽略 A 的对角线元素,并返回没有任何自环的图。您可以使用上述语法中的任何输入参数组合。

示例

G = digraph(s,t) 以对组形式指定有向图边 (s,t) 来表示源节点和目标节点。st 可以指定节点索引或节点名称。digraph 首先按源节点、然后按目标节点对 G 中的边进行排序。如果您的边属性的顺序与 st 的顺序相同,请使用语法 G = digraph(s,t,EdgeTable) 传入边属性,以便它们在生成的图中以相同的方式排序。

示例

G = digraph(s,t,weights) 还使用数组 weights 指定边的权重。

示例

G = digraph(s,t,weights,nodenames) 还使用字符向量元胞数组或字符串数组 nodenames 指定节点名称。st 不能包含 nodenames 中没有的节点名称。

G = digraph(s,t,weights,NodeTable) 使用表 NodeTable 指定节点名称(以及其他可能的节点属性)。使用 Name 表变量指定节点名称。st 不能包含 NodeTable 中没有的节点名称。

示例

G = digraph(s,t,weights,num) 使用数值标量 num 指定图中的节点数。

G = digraph(s,t,___,'omitselfloops') 不会将任何自环添加到图。即,将忽略满足 s(k) == t(k) 的任何 k。您可以使用上述语法中的任何输入参数组合。

G = digraph(s,t,EdgeTable,___) 使用表指定边属性,而不是指定 weightsEdgeTable 输入必须是一个表,其中的每一行对应于 st 中的每一对元素。使用表变量 Weight 指定边权重。

示例

G = digraph(EdgeTable) 使用表 EdgeTable 定义图。对于此语法,EdgeTable 中的第一个变量必须命名为 EndNodes,且它必须是定义图形边列表的两列数组。

示例

G = digraph(EdgeTable,NodeTable) 还使用表 NodeTable 指定图形节点的名称(以及其他可能的属性)。

G = digraph(EdgeTable,___,'omitselfloops') 不将自环添加到图。即,将忽略满足 EdgeTable.EndNodes(k,1) == EdgeTable.EndNodes(k,2) 的任何 k。必须指定 EdgeTable,可以选择指定 NodeTable

输入参数

全部展开

邻接矩阵,指定为满数值矩阵或稀疏数值矩阵。A 中的条目指定图节点之间的连接(边)网络。A 中每个非零项的位置指定两个节点之间的边。该元素的值提供边的权重。逻辑邻接矩阵会生成未加权图。

A 的主对角线上的非零项指定自环,即通过一条边连接到自身的节点。使用 'omitselfloops' 输入选项忽略对角线元素。

示例: A = [0 1 0; 0 0 0; 5 0 0] 描述具有三个节点和两条边的图。从节点 1 到节点 2 的边具有权重 1,从节点 3 到节点 1 的边具有权重 5

数据类型: single | double | logical

节点名称,指定为字符向量元胞数组或字符串数组。nodenames 的长度必须等于 numnodes(G),从而将图形中每个节点的非空唯一名称包含在该数组中。

示例: G = digraph(A,{'n1','n2','n3'}) 指定一个 3×3 邻接矩阵 A 的三个节点名称。

数据类型: cell | string

源节点和目标节点对组,指定为节点索引或节点名称。digraphst 中的对应节点之间创建有向边,这些节点必须都是数值,或都是字符向量、字符向量元胞数组、分类数组或字符串数组。在所有情况下,st 都必须具有相同的元素数。

  • 如果 st 都是数值,则它们对应于图节点的索引。数值节点索引必须为大于或等于 1 的正整数。

  • 如果 st 是字符向量、字符向量元胞数组或字符串数组,则它们指定节点的名称。图的 Nodes 属性是一个表,其中包含一个含有节点名称 G.Nodes.NameName 变量。

  • 如果 st 是分类数组,则 st 中的类别将用作图中的节点名称。这可以包括不是 st 中元素的类别。

  • 如果 st 指定相同两个节点之间的多条边,则结果为多重图

下表显示通过数值节点索引或节点名称引用一个或多个节点的不同方法。

形式单一节点多个节点
节点索引

标量

示例:1

向量

示例:[1 2 3]

节点名称

字符向量

示例:'A'

字符向量元胞数组

示例:{'A' 'B' 'C'}

字符串标量

示例:"A"

字符串数组

示例:["A" "B" "C"]

分类数组

示例:categorical("A")

分类数组

示例:categorical(["A" "B" "C"])

示例: G = digraph([1 2 3],[2 4 5]) 创建一个具有五个节点和三条边的图。

示例: G = digraph({'Boston' 'New York' 'Washington D.C.'},{'New York' 'New Jersey' 'Pittsburgh'}) 创建一个具有五个命名节点和三条边的图。

边权重,指定为标量、向量、矩阵或多维数组。weights 必须是标量或者是元素数与 st 相同的数组。

digraph 将边权重存储为 G.Edges 属性表中的一个 Weight 变量。要在创建图后添加或更改权重,您可以直接修改表变量,例如 G.Edges.Weight = [25 50 75]'

如果将 weights 指定为空数组 [],它将被忽略。

示例: G = digraph([1 2],[2 3],[100 200]) 创建具有三个节点和两条边的图。两条边的权重分别为 100200

数据类型: single | double

图节点数,指定为正整数标量。num 必须大于或等于 st 中的最大元素。

示例: G = digraph([1 2],[2 3],[],5) 创建具有三个相连接的节点和两个孤立节点的图。

边信息表。如果不指定 st,则 EdgeTable 中的第一个变量必须是定义图边的两列矩阵、字符向量元胞数组或字符串数组,名称为 EndNodes。对于边权重,请使用变量 Weight,因为某些图函数使用此表变量名称。如果存在变量 Weight,则它必须为数值列向量。请参阅 table,了解有关构建表的详细信息。

创建图后,请使用 G.Edges 查询边信息表。

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

数据类型: table

节点信息表。NodeTable 可以包含任意数量的变量来描述图节点的属性。对于节点名称,请使用变量 Name,因为某些图函数使用此表变量名称。如果存在变量 Name,则它必须是用于在每行中指定唯一名称的字符向量元胞数组或字符串数组。请参阅 table,了解有关构建表的详细信息。

在创建图后,请使用 G.Nodes 查询节点信息表。

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

数据类型: table

属性

全部展开

图的边,以表形式返回。默认情况下,这是一个 M×1 表,其中 M 是图中的边数。G.Edges.EndNodes 中的边列表首先按源节点、然后按目标节点排序。

  • 若要将新边属性添加到图,请在 Edges 表中创建一个新变量。

  • 要在图中添加或删除边,请使用 addedgermedge 对象函数。

示例: G.Edges 返回一个表,其中列出图中的边。

示例: G.Edges.Weight 返回边权重的数值向量。

示例: G.Edges.Weight = [10 20 30 55]' 指定图的新边权重。

示例: G.Edges.NormWeight = G.Edges.Weight/sum(G.Edges.Weight) 将一个新边属性添加到包含归一化边权重的表中。

数据类型: table

图的节点,以表形式返回。默认情况下,这是一个空 N×0 表,其中 N 是图中的节点数。

  • 若要将新节点属性添加到图中,请在 Nodes 表中创建一个新变量。

  • 若要在图中添加或删除节点,请使用 addnodermnode 对象函数。

示例: G.Nodes 返回一个表,其中列出图的节点属性。默认情况下此表为空。

示例: G.Nodes.Names = {'Montana', 'New York', 'Washington', 'California'}' 通过将变量 Names 添加到 Nodes 表,将节点名称添加到图。

示例: G.Nodes.WiFi = logical([1 0 0 1 1]') 将变量 WiFi 添加到 Nodes 表。此属性指定具有无线 Internet 覆盖范围的某些机场。

数据类型: table

对象函数

全部展开

addedge向图添加新边
rmedge从图中删除边
flipedge反转边的方向
addnode将新节点添加到图
rmnode从图中删除节点
findedge定位图中的边
findnode定位图中的节点
numedges图中边的数量
numnodes图中节点的数量
edgecount两个节点之间的边数
reordernodes对图节点重新排序
subgraph提取子图
centrality衡量节点的重要性
toposort有向无环图的拓扑顺序
transclosure传递闭包
transreduction传递归约
isdag确定图是否为无环
conncomp图的连通分量
condensation图凝聚
maxflow图中的最大流
isisomorphic确定两个图是否同构
isomorphism计算两个图之间的同构
ismultigraph确定图是否具有多条边
simplify将多重图简化为简单图
bfsearch广度优先图搜索
dfsearch深度优先图搜索
shortestpath两个单一节点之间的最短路径
shortestpathtree从节点的最短路径树
distances所有节点对组的最短路径距离
allpaths查找两个图节点之间的所有路径
hascycles确定图是否包含循环
allcycles查找图中的所有循环
adjacency图邻接矩阵
incidence图关联矩阵
indegree节点的入度
outdegree节点的出度
predecessors前趋节点
successors后继节点
nearest半径范围内最近的邻点
inedges进入节点的入向边
outedges节点的出向边
plot绘制图节点和边

示例

全部折叠

创建具有三个节点和三条边的 digraph 对象。一条边是从节点 1 到节点 2,另一条是从节点 1 到节点 3,第三条是从节点 2 到节点 1。

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

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

查看图的边表。对于有向图,第一列指示每条边是源节点,第二列指示目标节点。

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'}

您可以在 NodesEdges 表中添加或修改其他变量,以描述图节点或边的属性。但是,您无法通过修改这些表直接更改图中节点或边的数量。此时,应使用 addedgermedgeaddnodermnode 函数修改图中节点或边的数量。

例如,向图中的节点 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'}

创建对称邻接矩阵 A,该矩阵用于创建 4 阶完整有向图。使用逻辑邻接矩阵创建不带权重的图。

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')

Figure contains an axes object. The axes object contains an object of type graphplot.

使用每条边的端节点列表创建并绘制一个立方体图。将节点名称和边权重指定为单独的输入。

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)

Figure contains an axes object. The axes object contains an object of type graphplot.

使用每条边的端节点的列表创建加权图。指定图应包含共 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)

Figure contains an axes object. The axes object contains an object of type graphplot.

创建空有向图对象 G

G = digraph;

将三个节点和三条边添加到该图。st 中的相应项定义各条边的源节点和目标节点。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 来一次性构造多个图。对于大图来说,以循环方式添加节点或边会比较慢。

创建一个边表,其中包含变量 EndNodesWeightCode。然后,创建一个节点表,其中包含变量 NameCountry。每个表中的变量指定图节点和边的属性。

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)

Figure contains an axes object. The axes object contains an object of type graphplot.

扩展功能

基于线程的环境
使用 MATLAB® backgroundPool 在后台运行代码或使用 Parallel Computing Toolbox™ ThreadPool 加快代码运行速度。

版本历史记录

在 R2015b 中推出

全部展开