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 = 1×7 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
来限制 allcycles
返回的循环数,以便可用内存能够容纳结果。
示例: allcycles(G,'MaxNumCycles',100)
最大循环长度,指定为包含 'MaxCycleLength'
和正整数标量的逗号分隔对组。此选项过滤由 allcycles
返回的结果,以便不返回长度大于指定限制的循环。循环的长度按其中的边数来度量,忽略边权重。
要查找某长度范围内的循环,请同时指定 'MaxCycleLength'
和 'MinCycleLength'
。要查找具有精确指定长度的循环,请为 'MaxCycleLength'
和 'MinCycleLength'
指定相同的值。
示例: allcycles(G,'MaxCycleLength',4)
返回长度小于或等于 4 的循环。
示例: allcycles(G,'MinCycleLength',3,'MaxCycleLength',5)
返回长度为 3、4 或 5 的循环。
最小循环长度,指定为包含 'MinCycleLength'
和正整数标量的逗号分隔对组。此选项过滤由 allcycles
返回的结果,以便不返回长度小于指定限制的循环。循环的长度按其中的边数来度量,忽略边权重。
要查找某长度范围内的循环,请同时指定 'MaxCycleLength'
和 'MinCycleLength'
。要查找具有精确指定长度的循环,请为 'MaxCycleLength'
和 'MinCycleLength'
指定相同的值。
示例: allcycles(G,'MinCycleLength',2)
返回长度大于或等于 2 的循环。
示例: allcycles(G,'MinCycleLength',3,'MaxCycleLength',5)
返回长度为 3、4 或 5 的循环。
输出参量
图循环,以元胞数组形式返回。每个元素 cycles{k}
都包含属于 G
中某个循环的节点。每个循环从具有最小节点索引的节点开始,并且循环按字典编纂顺序返回。无向图中的循环只返回一次,使用同一个方向。如果 G
不包含任何循环,则 cycles
为空。
cycles
中元胞的数据类型取决于输入图是否包含节点名称:
如果图
G
没有节点名称,则每个元素cycles{k}
均为节点索引的数值向量。如果图
G
有节点名称,则每个元素cycles{k}
均为字符向量节点名称的元胞数组。
每个循环中的边,以元胞数组形式返回。每个元素 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 Command
You clicked a link that corresponds to this MATLAB command:
Run the command by entering it in the MATLAB Command Window. Web browsers do not support MATLAB commands.
选择网站
选择网站以获取翻译的可用内容,以及查看当地活动和优惠。根据您的位置,我们建议您选择:。
您也可以从以下列表中选择网站:
如何获得最佳网站性能
选择中国网站(中文或英文)以获得最佳网站性能。其他 MathWorks 国家/地区网站并未针对您所在位置的访问进行优化。
美洲
- América Latina (Español)
- Canada (English)
- United States (English)
欧洲
- 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)