allcycles

查找图中的所有循环

自 R2021a 起

全页折叠

语法

cycles = allcycles(G)

[cycles,edgecycles] = allcycles(G)

[___] = allcycles(G,Name,Value)

说明

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

将基础循环基与所有循环的集合进行比较

打开实时脚本

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

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

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

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

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

输入参数

全部折叠

`G` — 输入图
`graph` 对象 | `digraph` 对象

输入图，指定为 graph 或 digraph 对象。可使用 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' 和非负整数标量的逗号分隔对组。当图中的循环数增长到足以达到内存限制时，此选项非常有用。您可以指定 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 返回的结果，以便不返回长度小于指定限制的循环。循环的长度按其中的边数来度量，忽略边权重。

示例: 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 的输出。