Main Content

allcycles

查找图中的所有循环

自 R2021a 起

说明

cycles = allcycles(G) 返回指定的图中的所有循环。输出 cycles 是元胞数组,其中每个元胞 cycles{k} 的内容列出形成一个循环的节点。

示例

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

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

计算图中的所有循环。

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

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

计算图中的所有循环。指定两个输出参量,以同时返回每个循环中各边的边索引。

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

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

使用 '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]}

检查 cyclebasisallcycles 函数的输出如何随图中的边数而变化。

创建并绘制一个正方形网格图,在正方形的每条边上有三个节点。

n = 5;
A = delsq(numgrid('S',n));
G = graph(A,'omitselfloops');
plot(G)

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

使用 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

Figure contains 13 axes objects. Axes object 1 with title Cycle 1 contains an object of type graphplot. Axes object 2 with title Cycle 2 contains an object of type graphplot. Axes object 3 with title Cycle 3 contains an object of type graphplot. Axes object 4 with title Cycle 4 contains an object of type graphplot. Axes object 5 with title Cycle 5 contains an object of type graphplot. Axes object 6 with title Cycle 6 contains an object of type graphplot. Axes object 7 with title Cycle 7 contains an object of type graphplot. Axes object 8 with title Cycle 8 contains an object of type graphplot. Axes object 9 with title Cycle 9 contains an object of type graphplot. Axes object 10 with title Cycle 10 contains an object of type graphplot. Axes object 11 with title Cycle 11 contains an object of type graphplot. Axes object 12 with title Cycle 12 contains an object of type graphplot. Axes object 13 with title Cycle 13 contains an object of type graphplot.

其中一些循环可视为较小循环的组合。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

Figure contains 4 axes objects. Axes object 1 with title Cycle 1 contains an object of type graphplot. Axes object 2 with title Cycle 2 contains an object of type graphplot. Axes object 3 with title Cycle 3 contains an object of type graphplot. Axes object 4 with title Cycle 4 contains an object of type graphplot.

现在,将正方形图每条边的节点数从三个增加到四个。这表示图的大小略有增大。

n = 6;
A = delsq(numgrid('S',n));
G = graph(A,'omitselfloops');
figure
plot(G)

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

使用 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

Figure contains 9 axes objects. Axes object 1 with title Cycle 1 contains an object of type graphplot. Axes object 2 with title Cycle 2 contains an object of type graphplot. Axes object 3 with title Cycle 3 contains an object of type graphplot. Axes object 4 with title Cycle 4 contains an object of type graphplot. Axes object 5 with title Cycle 5 contains an object of type graphplot. Axes object 6 with title Cycle 6 contains an object of type graphplot. Axes object 7 with title Cycle 7 contains an object of type graphplot. Axes object 8 with title Cycle 8 contains an object of type graphplot. Axes object 9 with title Cycle 9 contains an object of type graphplot.

对于某些图结构来说,循环数大幅增加而图大小只有很小变化是很常见的。allcycles 返回的循环数可能随着图中边数增多而呈指数增长。但是,cyclebasis 返回的循环数最多会随着图中的边数线性增长。

输入参数

全部折叠

输入图,指定为 graphdigraph 对象。可使用 graph 创建一个无向图,或使用 digraph 创建一个有向图。

示例: G = graph(1,2)

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

名称-值参数

将可选的参量对组指定为 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 万个循环。在这些情况下,请使用 MaxNumCyclesMaxCycleLengthMinCycleLength 选项来控制 allcycles 的输出。

版本历史记录

在 R2021a 中推出

另请参阅

| |