allcycles
说明
[
还返回每个循环中的边。输出 cycles
,edgecycles
] = allcycles(G
)edgecycles
是元胞数组,其中 edgecycles{k}
给出对应循环 cycles{k}
中的边。
[___] = allcycles(
使用一个或多个名称-值参量指定其他选项。您可以使用上述语法中的任何输出参量组合。例如,您可以指定 G
,Name,Value
)MaxNumCycles
和一个标量来限制返回的循环数。
示例
有向图中的所有循环
创建一个包含九个节点的有向图。绘制图。
s = [1 2 3 6 5 5 4 6 9 8 8 7]; t = [2 3 6 5 2 4 1 9 8 5 7 4]; G = digraph(s,t); plot(G)
计算图中的所有循环。
cycles = allcycles(G)
cycles=5×1 cell array
{[ 1 2 3 6 5 4]}
{[1 2 3 6 9 8 5 4]}
{[1 2 3 6 9 8 7 4]}
{[ 2 3 6 5]}
{[ 2 3 6 9 8 5]}
循环中包含的边
allcycles
的第二个输出参量返回每个循环中包含的边。这对于多重图特别有用,在多重图中,需要边索引来唯一标识每个循环中的边。
创建一个包含 8 个节点和 18 条边的有向多重图。指定节点的名称。绘制一个包含带标签的节点和边的图。
s = [1 1 2 2 3 3 2 2 4 6 8 6 6 7 3 3 5 3]; t = [2 3 1 3 2 1 4 4 6 2 6 7 8 8 5 5 7 7]; names = {'A','B','C','D','E','F','G','H'}; G = digraph(s,t,[],names); p = plot(G,'EdgeLabel',1:numedges(G));
计算图中的所有循环。指定两个输出参量,以同时返回每个循环中各边的边索引。
[cycles,edgecycles] = allcycles(G);
查看第五个循环中的节点和边。
cycles{5}
ans = 1x7 cell
{'A'} {'C'} {'E'} {'G'} {'H'} {'F'} {'B'}
edgecycles{5}
ans = 1×7
2 9 13 17 18 14 3
突出显示第五个循环中的节点和边。
highlight(p,'Edges',edgecycles{5},'EdgeColor','r','LineWidth',1.5,'NodeColor','r','MarkerSize',6)
限制返回的循环数
使用 'MaxNumCycles'
、'MaxCycleLength'
和 'MinCycleLength'
选项来限制 allcycles
返回的循环数。
为包含 20 个节点的完整图创建一个邻接矩阵。从该邻接矩阵创建一个无向图,省略自环。
A = ones(20);
G = graph(A,'omitselfloops');
由于图中的所有节点都连接到所有其他节点,图中存在大量循环(超过 1.7e17
个)。因此,计算所有循环是不可行的,因为内存中容纳不下结果。在这种情况下,计算前 10 个循环。
cycles1 = allcycles(G,'MaxNumCycles',10)
cycles1=10×1 cell array
{[ 1 2 3]}
{[ 1 2 3 4]}
{[ 1 2 3 4 5]}
{[ 1 2 3 4 5 6]}
{[ 1 2 3 4 5 6 7]}
{[ 1 2 3 4 5 6 7 8]}
{[ 1 2 3 4 5 6 7 8 9]}
{[ 1 2 3 4 5 6 7 8 9 10]}
{[ 1 2 3 4 5 6 7 8 9 10 11]}
{[1 2 3 4 5 6 7 8 9 10 11 12]}
现在计算循环长度小于或等于 3 的前 10 个循环。
cycles2 = allcycles(G,'MaxNumCycles',10,'MaxCycleLength',3)
cycles2=10×1 cell array
{[ 1 2 3]}
{[ 1 2 4]}
{[ 1 2 5]}
{[ 1 2 6]}
{[ 1 2 7]}
{[ 1 2 8]}
{[ 1 2 9]}
{[1 2 10]}
{[1 2 11]}
{[1 2 12]}
最后,计算循环长度大于或等于 4 的前 10 个循环。
cycles3 = allcycles(G,'MaxNumCycles',10,'MinCycleLength',4)
cycles3=10×1 cell array
{[ 1 2 3 4]}
{[ 1 2 3 4 5]}
{[ 1 2 3 4 5 6]}
{[ 1 2 3 4 5 6 7]}
{[ 1 2 3 4 5 6 7 8]}
{[ 1 2 3 4 5 6 7 8 9]}
{[ 1 2 3 4 5 6 7 8 9 10]}
{[ 1 2 3 4 5 6 7 8 9 10 11]}
{[ 1 2 3 4 5 6 7 8 9 10 11 12]}
{[1 2 3 4 5 6 7 8 9 10 11 12 13]}
将基础循环基与所有循环的集合进行比较
检查 cyclebasis
和 allcycles
函数的输出如何随图中的边数而变化。
创建并绘制一个正方形网格图,在正方形的每条边上有三个节点。
n = 5; A = delsq(numgrid('S',n)); G = graph(A,'omitselfloops'); plot(G)
使用 allcycles
计算图中的所有循环。使用 tiledlayout
函数构造一个子图数组,并突出显示子图中的每个循环。结果表明,图中总共有 13 个循环。
[cycles,edgecycles] = allcycles(G); tiledlayout flow for k = 1:length(cycles) nexttile highlight(plot(G),cycles{k},'Edges',edgecycles{k},'EdgeColor','r','NodeColor','r') title("Cycle " + k) end
其中一些循环可视为较小循环的组合。cyclebasis
函数返回构成图中所有其他循环基础的循环的一个子集。使用 cyclebasis
计算基础循环基,并突出显示子图中的每个基础循环。即使图中有 13 个循环,基础循环也只有 4 个。
[cycles,edgecycles] = cyclebasis(G); tiledlayout flow for k = 1:length(cycles) nexttile highlight(plot(G),cycles{k},'Edges',edgecycles{k},'EdgeColor','r','NodeColor','r') title("Cycle " + k) end
现在,将正方形图每条边的节点数从三个增加到四个。这表示图的大小略有增大。
n = 6; A = delsq(numgrid('S',n)); G = graph(A,'omitselfloops'); figure plot(G)
使用 allcycles
计算新图中的所有循环。此图有 200 多个循环,数量太多而无法绘制。
allcycles(G)
ans=213×1 cell array
{[ 1 2 3 4 8 7 6 5]}
{[ 1 2 3 4 8 7 6 10 9 5]}
{[1 2 3 4 8 7 6 10 11 12 16 15 14 13 9 5]}
{[ 1 2 3 4 8 7 6 10 11 15 14 13 9 5]}
{[ 1 2 3 4 8 7 6 10 14 13 9 5]}
{[ 1 2 3 4 8 7 11 10 6 5]}
{[ 1 2 3 4 8 7 11 10 9 5]}
{[ 1 2 3 4 8 7 11 10 14 13 9 5]}
{[ 1 2 3 4 8 7 11 12 16 15 14 10 6 5]}
{[ 1 2 3 4 8 7 11 12 16 15 14 10 9 5]}
{[ 1 2 3 4 8 7 11 12 16 15 14 13 9 5]}
{[1 2 3 4 8 7 11 12 16 15 14 13 9 10 6 5]}
{[ 1 2 3 4 8 7 11 15 14 10 6 5]}
{[ 1 2 3 4 8 7 11 15 14 10 9 5]}
{[ 1 2 3 4 8 7 11 15 14 13 9 5]}
{[ 1 2 3 4 8 7 11 15 14 13 9 10 6 5]}
⋮
尽管图中有大量循环,但 cyclebasis
仍返回少量基础循环。图中的每个循环都可以只用九个基础循环来构造。
[cycles,edgecycles] = cyclebasis(G); figure tiledlayout flow for k = 1:length(cycles) nexttile highlight(plot(G),cycles{k},'Edges',edgecycles{k},'EdgeColor','r','NodeColor','r') title("Cycle " + k) end
对于某些图结构来说,循环数大幅增加而图大小只有很小变化是很常见的。allcycles
返回的循环数可能随着图中边数增多而呈指数增长。但是,cyclebasis
返回的循环数最多会随着图中的边数线性增长。
输入参数
名称-值参数
将可选的参量对组指定为 Name1=Value1,...,NameN=ValueN
,其中 Name
是参量名称,Value
是对应的值。名称-值参量必须出现在其他参量之后,但参量对组的顺序无关紧要。
在 R2021a 之前,使用逗号分隔每个名称和值,并用引号将 Name
引起来。
示例: allcycles(G,'MaxNumCycles',100)
仅返回图中的前 100 个循环。
MaxNumCycles
— 最大循环数
非负整数标量
最大循环数,指定为包含 'MaxNumCycles'
和非负整数标量的逗号分隔对组。当图中的循环数增长到足以达到内存限制时,此选项非常有用。您可以指定 MaxNumCycles
来限制 allcycles
返回的循环数,以便可用内存能够容纳结果。
示例: allcycles(G,'MaxNumCycles',100)
MaxCycleLength
— 最大循环长度
正整数标量
最大循环长度,指定为包含 'MaxCycleLength'
和正整数标量的逗号分隔对组。此选项过滤由 allcycles
返回的结果,以便不返回长度大于指定限制的循环。循环的长度按其中的边数来度量,忽略边权重。
要查找某长度范围内的循环,请同时指定 'MaxCycleLength'
和 'MinCycleLength'
。要查找具有精确指定长度的循环,请为 'MaxCycleLength'
和 'MinCycleLength'
指定相同的值。
示例: allcycles(G,'MaxCycleLength',4)
返回长度小于或等于 4 的循环。
示例: allcycles(G,'MinCycleLength',3,'MaxCycleLength',5)
返回长度为 3、4 或 5 的循环。
MinCycleLength
— 最小循环长度
正整数标量
最小循环长度,指定为包含 'MinCycleLength'
和正整数标量的逗号分隔对组。此选项过滤由 allcycles
返回的结果,以便不返回长度小于指定限制的循环。循环的长度按其中的边数来度量,忽略边权重。
要查找某长度范围内的循环,请同时指定 'MaxCycleLength'
和 'MinCycleLength'
。要查找具有精确指定长度的循环,请为 'MaxCycleLength'
和 'MinCycleLength'
指定相同的值。
示例: allcycles(G,'MinCycleLength',2)
返回长度大于或等于 2 的循环。
示例: allcycles(G,'MinCycleLength',3,'MaxCycleLength',5)
返回长度为 3、4 或 5 的循环。
输出参量
cycles
— 图循环
元胞数组
图循环,以元胞数组形式返回。每个元素 cycles{k}
都包含属于 G
中某个循环的节点。每个循环从具有最小节点索引的节点开始,并且循环按字典编纂顺序返回。无向图中的循环只返回一次,使用同一个方向。如果 G
不包含任何循环,则 cycles
为空。
cycles
中元胞的数据类型取决于输入图是否包含节点名称:
如果图
G
没有节点名称,则每个元素cycles{k}
均为节点索引的数值向量。如果图
G
有节点名称,则每个元素cycles{k}
均为字符向量节点名称的元胞数组。
edgecycles
— 每个循环中的边
元胞数组
每个循环中的边,以元胞数组形式返回。每个元素 edgecycles{k}
包含对应循环 cycles{k}
中边的边索引。如果 G
不包含任何循环,则 edgecycles
为空。
详细信息
图循环
如果图中有一条非空路径,其中只有第一个和最后一个节点重复,则图中就存在一个循环。也就是说,除了第一个节点会在路径的末端重复以结束循环之外,没有其他节点重复。循环的一个示例是:(节点 1 - 节点 2 - 节点 3 - 节点 1)。按照惯例,allcycles
不返回循环中的最后一个节点,因为它与第一个节点相同。
一个循环不能对同一条边遍历两次。例如,无向图中的循环(节点 1 - 节点 2 - 节点 1)仅在连接结点 1 和节点 2 的边不止一条的情况下才存在。根据此定义,自环算作循环,尽管它们不能作为更大循环的一部分。
提示
图中的循环数在很大程度上取决于图的结构。对于某些图结构,循环数可能随着节点数增加而呈指数增长。例如,一个具有由
G = graph(ones(12))
给出的 12 个节点的完整图包含近 6000 万个循环。在这些情况下,请使用MaxNumCycles
、MaxCycleLength
和MinCycleLength
选项来控制allcycles
的输出。
版本历史记录
在 R2021a 中推出
另请参阅
MATLAB 命令
您点击的链接对应于以下 MATLAB 命令:
请在 MATLAB 命令行窗口中直接输入以执行命令。Web 浏览器不支持 MATLAB 命令。
Select a Web Site
Choose a web site to get translated content where available and see local events and offers. Based on your location, we recommend that you select: .
You can also select a web site from the following list:
How to Get Best Site Performance
Select the China site (in Chinese or English) for best site performance. Other MathWorks country sites are not optimized for visits from your location.
Americas
- América Latina (Español)
- Canada (English)
- United States (English)
Europe
- Belgium (English)
- Denmark (English)
- Deutschland (Deutsch)
- España (Español)
- Finland (English)
- France (Français)
- Ireland (English)
- Italia (Italiano)
- Luxembourg (English)
- Netherlands (English)
- Norway (English)
- Österreich (Deutsch)
- Portugal (English)
- Sweden (English)
- Switzerland
- United Kingdom (English)