igraph 参考手册

用于使用 igraph C 库

搜索手册
上一个 首页 下一个

第 17 章 图同构

1. 简单接口
2. BLISS 算法
3. VF2 算法
4. LAD 算法
5. 小型图函数
6. 实用函数
7. 弃用函数

1. 简单接口

1.1. igraph_isomorphic — 两个图是否同构？
1.2. igraph_subisomorphic — 确定子图同构。

igraph 提供了四组函数来处理图同构问题。

igraph_isomorphic() 和 igraph_subisomorphic() 函数构成了第一组（此外还有 igraph_permute_vertices() 函数）。这些函数选择最适合所提供输入图的算法。（该选择不是很复杂，有关详细信息，请参阅其文档。）

VF2 图（和子图）同构算法在 igraph 中实现，这些函数是第二组。有关入门信息，请参阅 igraph_isomorphic_vf2() 和 igraph_subisomorphic_vf2()。

Bliss 算法的函数构成了第三组，请参阅 igraph_isomorphic_bliss()。

最后，所有具有三个和四个顶点的有向图以及所有具有 3-6 个顶点的无向图的同构类都已预先计算并存储在 igraph 中，因此对于这些小型图，代码中存在单独的快速路径，该路径不使用更复杂的通用同构算法。

1.1. igraph_isomorphic — 两个图是否同构？

igraph_error_t igraph_isomorphic(const igraph_t *graph1, const igraph_t *graph2,
                      igraph_bool_t *iso);

简单来说，如果两个图的顶点标签被移除（使每个图中的顶点无法区分）后，它们变得彼此无法区分，则它们是同构的。更准确地说，如果存在从第一个图的顶点到第二个图的顶点的一对一映射，从而将第一个图的边集转换为第二个图的边集，则两个图是同构的。此映射称为同构。

此函数根据输入图决定要使用的图同构算法。目前，它执行以下操作：

  1. 如果一个图是有向图，而另一个图是无向图，则会触发错误。

  2. 如果其中一个图具有多重边，则两个图都会使用 igraph_simplify_and_colorize() 进行简化和着色，然后发送到 VF2。

  3. 如果两个图的顶点和边数不相同，则返回 false。

  4. 否则，如果 igraph_isoclass() 函数支持这两个图（对于具有 3 和 4 个顶点的有向图以及具有 3-6 个顶点的无向图来说是正确的），则使用具有预先计算数据的 O(1) 算法。

  5. 否则，将使用 Bliss，请参阅 igraph_isomorphic_bliss()。

如果您需要更复杂的内容，例如，您需要同构映射，请直接调用 VF2 和 Bliss 函数。

参数： 

graph1:

第一个图。

graph2:

第二个图。

iso:

指向布尔变量的指针，如果两个图同构，则设置为 true，否则设置为 false。

返回值： 

错误代码。

另请参阅： 

igraph_isoclass(), igraph_isoclass_subgraph(), igraph_isoclass_create().

时间复杂度：指数级。

1.2. igraph_subisomorphic — 确定子图同构。

igraph_error_t igraph_subisomorphic(const igraph_t *graph1, const igraph_t *graph2,
                         igraph_bool_t *iso);

检查 graph2 是否与 graph1 的子图同构。目前，此函数仅为所有图调用 igraph_subisomorphic_vf2()。

目前，此函数不支持非简单图。

参数： 

graph1:

第一个输入图，可以是有向图或无向图。这应该是更大的图。

graph2:

第二个输入图，它必须与 graph2 具有相同的方向性，否则会触发错误。这应该是较小的图。

iso:

指向布尔值的指针，结果存储在此处。

返回值： 

错误代码。

时间复杂度：指数级。

2. BLISS 算法

2.1. igraph_bliss_sh_t — Bliss 的拆分启发式方法。
2.2. igraph_bliss_info_t — 关于 Bliss 运行的信息。
2.3. igraph_canonical_permutation — 使用 Bliss 的规范排列。
2.4. igraph_isomorphic_bliss — 通过 Bliss 实现图同构。
2.5. igraph_count_automorphisms — 使用 Bliss 的自同构数。
2.6. igraph_automorphism_group — 使用 Bliss 的自同构群生成器。
2.7. 弃用的别名

Bliss 是著名的 NAUTY 算法和实现的后继者。虽然通常使用相同的想法，但凭借更好的启发式方法和数据结构，Bliss 在大多数图上都优于 NAUTY。

Bliss 由芬兰赫尔辛基理工大学的 Tommi Junttila 和 Petteri Kaski 开发和实施。有关更多信息，请参见 Bliss 主页 https://users.aalto.fi/~tjunttil/bliss/ 和以下出版物

Tommi Junttila 和 Petteri Kaski：“Engineering an Efficient Canonical Labeling Tool for Large and Sparse Graphs” In ALENEX 2007，第 135–149 页，2007 年 https://doi.org/10.1137/1.9781611972870.13

Tommi Junttila 和 Petteri Kaski：“Conflict Propagation and Component Recursion for Canonical Labeling” in TAPAS 2011，第 151–162 页，2011 年。 https://doi.org/10.1007/978-3-642-19754-3_16

Bliss 可用于有向图和无向图。它支持具有自环的图，但不支持具有多重边的图。

Bliss 0.75 版本包含在 igraph 中。

2.1. igraph_bliss_sh_t — Bliss 的拆分启发式方法。

typedef enum { IGRAPH_BLISS_F = 0, IGRAPH_BLISS_FL,
               IGRAPH_BLISS_FS, IGRAPH_BLISS_FM,
               IGRAPH_BLISS_FLM, IGRAPH_BLISS_FSM
             } igraph_bliss_sh_t;

IGRAPH_BLISS_FL 为许多图提供了良好的性能，是一个合理的默认选择。IGRAPH_BLISS_FSM 建议用于具有一些组合结构的图，并且是 Bliss 库命令行工具的默认设置。

值： 

IGRAPH_BLISS_F:

第一个非单例单元格。

IGRAPH_BLISS_FL:

第一个最大的非单例单元格。

IGRAPH_BLISS_FS:

第一个最小的非单例单元格。

IGRAPH_BLISS_FM:

第一个最大程度地非平凡连接的非单例单元格。

IGRAPH_BLISS_FLM:

最大程度地非平凡连接的非单例单元格中最大的一个。

IGRAPH_BLISS_FSM:

最小程度地非平凡连接的非单例单元格中最小的一个。

2.2. igraph_bliss_info_t — 关于 Bliss 运行的信息。

typedef struct igraph_bliss_info_t {
    unsigned long nof_nodes;
    unsigned long nof_leaf_nodes;
    unsigned long nof_bad_nodes;
    unsigned long nof_canupdates;
    unsigned long nof_generators;
    unsigned long max_level;
    char *group_size;
} igraph_bliss_info_t;

Bliss 算法发现的一些辅助信息存储在此处。如果您想研究算法的内部工作，这将非常有用。

值： 

nof_nodes:

搜索树中的节点数。

nof_leaf_nodes:

搜索树中的叶节点数。

nof_bad_nodes:

坏节点的数量。

nof_canupdates:

Canrep 更新的数量。

nof_generators:

自同构群的生成器数量。

max_level:

最大级别。

group_size:

图的自同构群的大小，以字符串形式给出。如果不再需要，应通过 igraph_free() 取消分配。

有关算法和这些参数的详细信息，请参见 https://users.aalto.fi/~tjunttil/bliss/。

2.3. igraph_canonical_permutation — 使用 Bliss 的规范排列。

igraph_error_t igraph_canonical_permutation(const igraph_t *graph, const igraph_vector_int_t *colors,
                                 igraph_vector_int_t *labeling, igraph_bliss_sh_t sh, igraph_bliss_info_t *info);

此函数使用 Bliss 算法计算将图转换为规范形式的顶点排列。当且仅当两个图具有相同的规范形式时，它们才是同构的。使用 igraph_is_same_graph() 比较两个规范形式。

参数： 

图:

输入图。不支持同一节点之间的多重边，并且会导致返回不正确的结果。

colors:

图的可选顶点颜色向量。如果图未着色，则提供空指针。

labeling:

指向向量的指针，结果存储在此处。排列将顶点 0 转换为向量的第一个元素，将顶点 1 转换为第二个元素，依此类推。该向量将根据需要调整大小。

sh:

Bliss 中使用的拆分启发式方法。请参阅 igraph_bliss_sh_t。

info:

如果不为 NULL，则此处存储有关 Bliss 内部的信息。不再需要时必须释放此结构使用的内存，请参阅 igraph_bliss_info_t。

返回值： 

错误代码。

另请参阅： 

igraph_is_same_graph()

时间复杂度：指数级，在实践中，它对于许多图都很快。

2.4. igraph_isomorphic_bliss — 通过 Bliss 实现图同构。

igraph_error_t igraph_isomorphic_bliss(const igraph_t *graph1, const igraph_t *graph2,
                            const igraph_vector_int_t *colors1, const igraph_vector_int_t *colors2,
                            igraph_bool_t *iso, igraph_vector_int_t *map12,
                            igraph_vector_int_t *map21, igraph_bliss_sh_t sh,
                            igraph_bliss_info_t *info1, igraph_bliss_info_t *info2);

此函数使用 Bliss 图同构算法，该算法是著名的 NAUTY 算法和实现的后继者。Bliss 是开源的，并根据 GNU LGPL 许可。有关详细信息，请参见 https://users.aalto.fi/~tjunttil/bliss/。目前，igraph 中包含 Bliss 的 0.75 版本。

同构测试是通过使用 igraph_canonical_permutation() 生成两个图的规范形式并进行比较来实现的。

参数： 

graph1:

第一个输入图。不支持同一节点之间的多重边，并且会导致返回不正确的结果。

graph2:

第二个输入图。不支持同一节点之间的多重边，并且会导致返回不正确的结果。

colors1:

第一个图的可选顶点颜色向量。如果您的图未着色，则提供空指针。

colors2:

第二个图的可选顶点颜色向量。有关说明，请参阅上一个参数。

iso:

指向布尔值的指针，结果存储在此处。

map12:

向量或 NULL 指针。如果不为 NULL，则此处存储从 graph1 到 graph2 的同构映射。如果输入图不同构，则将清除此向量，即，其长度将为零。

map21:

与 map12 类似，但是是从 graph2 到 graph1 的映射。

sh:

用于图的拆分启发式方法。请参阅 igraph_bliss_sh_t。

info1:

如果不为 NULL，则此处存储有关第一个输入图的规范化的信息。请注意，如果两个图的顶点或边数不同，则仅部分填充此信息。不再需要时应释放此结构使用的内存，有关详细信息，请参阅 igraph_bliss_info_t。

info2:

与 info1 相同，但用于第二个图。

返回值： 

错误代码。

时间复杂度：指数级，但在实践中，它非常快。

2.5. igraph_count_automorphisms — 使用 Bliss 的自同构数。

igraph_error_t igraph_count_automorphisms(const igraph_t *graph, const igraph_vector_int_t *colors,
                         igraph_bliss_sh_t sh, igraph_bliss_info_t *info);

图的自同构数是使用 Bliss 计算的。结果作为 info 结构的一部分返回，位于标记 group_size 中。结果以字符串形式返回，因为即使对于相对较小的图，它也可能很高。另请参阅 igraph_bliss_info_t。

参数： 

图:

输入图。不支持同一节点之间的多重边，并且会导致返回不正确的结果。

colors:

图的可选顶点颜色向量。如果图未着色，则提供空指针。

sh:

Bliss 中使用的拆分启发式方法。请参阅 igraph_bliss_sh_t。

info:

结果存储在此处，尤其是在 info 的 group_size 标记中。不再需要时必须释放此结构使用的内存，请参阅 igraph_bliss_info_t。

返回值： 

错误代码。

时间复杂度：指数级，在实践中，它对于许多图都很快。

2.6. igraph_automorphism_group — 使用 Bliss 的自同构群生成器。

igraph_error_t igraph_automorphism_group(
    const igraph_t *graph, const igraph_vector_int_t *colors, igraph_vector_int_list_t *generators,
    igraph_bliss_sh_t sh, igraph_bliss_info_t *info);

图的自同构群的生成器是使用 Bliss 计算的。生成器集可能不是最小的，并且可能取决于拆分启发式方法。生成器是使用从零开始的索引表示的排列。

参数： 

图:

输入图。不支持同一节点之间的多重边，并且会导致返回不正确的结果。

colors:

图的可选顶点颜色向量。如果图未着色，则提供空指针。

generators:

必须是已初始化的整数向量列表。自同构群的生成器将存储在此处。

sh:

Bliss 中使用的拆分启发式方法。请参阅 igraph_bliss_sh_t。

info:

如果不为 NULL，则此处存储有关 Bliss 内部的信息。不再需要时必须释放此结构使用的内存，请参阅 igraph_bliss_info_t。

返回值： 

错误代码。

时间复杂度：指数级，在实践中，它对于许多图都很快。

2.7. 弃用的别名

2.7.1. igraph_automorphisms — 使用 Bliss 的自同构数（弃用的别名）。

2.7.1. igraph_automorphisms — 使用 Bliss 的自同构数（弃用的别名）。

igraph_error_t igraph_automorphisms(const igraph_t *graph, const igraph_vector_int_t *colors,
                                    igraph_bliss_sh_t sh, igraph_bliss_info_t *info);

警告

自 0.10.5 版本起已弃用。请勿在新代码中使用此函数；请改用 igraph_count_automorphisms()。

3. VF2 算法

3.1. igraph_isomorphic_vf2 — 通过 VF2 实现同构。
3.2. igraph_count_isomorphisms_vf2 — 通过 VF2 实现的同构数。
3.3. igraph_get_isomorphisms_vf2 — 收集两个图的所有同构映射。
3.4. igraph_get_isomorphisms_vf2_callback — 通用 VF2 接口
3.5. igraph_isohandler_t — 回调类型，在找到同构时调用
3.6. igraph_isocompat_t — 回调类型，用于检查两个顶点或边是否兼容
3.7. igraph_subisomorphic_vf2 — 使用 VF2 确定子图同构
3.8. igraph_count_subisomorphisms_vf2 — 使用 VF2 的子图同构数
3.9. igraph_get_subisomorphisms_vf2 — 返回所有子图同构映射。
3.10. igraph_get_subisomorphisms_vf2_callback — 用于子图同构问题的通用 VF2 函数。
3.11. 弃用的别名

VF2 算法可以在较大的图中搜索子图，或检查两个图是否同构。请参阅 P. Foggia、C. Sansone、M. Vento，《An Improved algorithm for matching large graphs》，Proc. of the 3rd IAPR-TC-15 International Workshop on Graph-based Representations, Italy, 2001。

VF2 支持顶点着色图和边着色图，以及自定义顶点或边兼容性函数。

VF2 适用于有向图和无向图。仅支持简单图。图中不得存在自环或多重边。目前，VF2 函数不检查输入图是否简单：用户有责任传入有效的输入。

3.1. igraph_isomorphic_vf2 — 通过 VF2 实现同构。

igraph_error_t igraph_isomorphic_vf2(const igraph_t *graph1, const igraph_t *graph2,
                          const igraph_vector_int_t *vertex_color1,
                          const igraph_vector_int_t *vertex_color2,
                          const igraph_vector_int_t *edge_color1,
                          const igraph_vector_int_t *edge_color2,
                          igraph_bool_t *iso, igraph_vector_int_t *map12,
                          igraph_vector_int_t *map21,
                          igraph_isocompat_t *node_compat_fn,
                          igraph_isocompat_t *edge_compat_fn,
                          void *arg);

此函数通过调用 igraph_get_isomorphisms_vf2_callback() 来执行 VF2 算法。

请注意，此函数不能用于确定子图同构，请使用 igraph_subisomorphic_vf2()。

参数： 

graph1:

第一个图，可以是有向图或无向图。

graph2:

第二个图。它必须与 graph1 具有相同的方向性，否则会报告错误。

vertex_color1:

第一个图的可选颜色向量。如果为两个图都提供了颜色向量，则在着色图上计算同构；即，两个顶点只有在颜色也匹配时才能匹配。如果您的图未着色，请在此处提供空指针。

vertex_color2:

第二个图的可选颜色向量。有关说明，请参阅上一个参数。

edge_color1:

第一个图的可选边颜色向量。两个图中的匹配边也必须具有匹配的颜色。如果您的图未进行边着色，请在此处提供空指针。

edge_color2:

第二个图的边颜色向量。

iso:

指向布尔常量的指针，算法的结果将放置在此处。

map12:

指向已初始化的向量或 NULL 指针。如果不为 NULL 指针，则此处存储从 graph1 到 graph2 的映射。如果图不同构，则向量将被清除（即，具有零个元素）。

map21:

指向已初始化的向量或 NULL 指针。如果不为 NULL 指针，则此处存储从 graph2 到 graph1 的映射。如果图不同构，则向量将被清除（即，具有零个元素）。

node_compat_fn:

指向类型为 igraph_isocompat_t 的函数的指针。此函数将由算法调用，以确定两个节点是否兼容。

edge_compat_fn:

指向类型为 igraph_isocompat_t 的函数的指针。此函数将由算法调用，以确定两条边是否兼容。

arg:

要提供给函数 node_compat_fn 和 edge_compat_fn 的额外参数。

返回值： 

错误代码。

另请参阅： 

igraph_subisomorphic_vf2(), igraph_count_isomorphisms_vf2(), igraph_get_isomorphisms_vf2(),

时间复杂度：指数级，您期望什么？

示例 17.1. 文件 examples/simple/igraph_isomorphic_vf2.c

#include <igraph.h>
#include <stdio.h>
#include <stdlib.h>

int main(void) {

    igraph_t ring1, ring2;
    igraph_vector_int_t color1, color2;
    igraph_vector_int_t perm;
    igraph_bool_t iso;
    igraph_integer_t count;
    igraph_integer_t i;

    igraph_rng_seed(igraph_rng_default(), 12345);

    igraph_ring(&ring1, 100, /*directed=*/ 0, /*mutual=*/ 0, /*circular=*/1);
    igraph_vector_int_init_range(&perm, 0, igraph_vcount(&ring1));
    igraph_vector_int_shuffle(&perm);
    igraph_permute_vertices(&ring1, &ring2, &perm);

    /* Everything has the same colors */
    igraph_vector_int_init(&color1, igraph_vcount(&ring1));
    igraph_vector_int_init(&color2, igraph_vcount(&ring2));
    igraph_isomorphic_vf2(&ring1, &ring2, &color1, &color2, 0, 0, &iso, 0, 0, 0, 0, 0);
    if (!iso) {
        fprintf(stderr, "Single color failed.\n");
        return 1;
    }

    /* Two colors, just counting */
    for (i = 0; i < igraph_vector_int_size(&color1); i += 2) {
        VECTOR(color1)[i] = VECTOR(color2)[VECTOR(perm)[i]] = 1;
    }
    igraph_count_isomorphisms_vf2(&ring1, &ring2, &color1, &color2, 0, 0, &count, 0, 0, 0);
    if (count != 100) {
        fprintf(stderr, "Count with two colors failed, expected 100, got %" IGRAPH_PRId ".\n", count);
        return 2;
    }

    igraph_destroy(&ring1);
    igraph_destroy(&ring2);
    igraph_vector_int_destroy(&color2);
    igraph_vector_int_destroy(&perm);

    /* Two colors, count subisomorphisms */
    igraph_ring(&ring1, 100, /*directed=*/ 0, /*mutual=*/ 0, /*circular=*/0);
    igraph_ring(&ring2, 80, /*directed=*/ 0, /*mutual=*/ 0, /*circular=*/0);

    igraph_vector_int_init(&color2, igraph_vcount(&ring2));
    for (i = 0; i < igraph_vector_int_size(&color1); i += 2) {
        VECTOR(color1)[i]   = 0;
        VECTOR(color1)[i + 1] = 1;
    }
    for (i = 0; i < igraph_vector_int_size(&color2); i += 2) {
        VECTOR(color2)[i]   = 0;
        VECTOR(color2)[i + 1] = 1;
    }
    igraph_count_subisomorphisms_vf2(&ring1, &ring2, &color1, &color2, 0, 0,
                                     &count, 0, 0, 0);
    if (count != 21) {
        fprintf(stderr, "Count with two colors failed, expected 21, got %" IGRAPH_PRId ".\n", count);
        return 3;
    }

    igraph_vector_int_destroy(&color1);
    igraph_vector_int_destroy(&color2);

    igraph_destroy(&ring1);
    igraph_destroy(&ring2);

    return 0;
}


3.2. igraph_count_isomorphisms_vf2 — 通过 VF2 实现的同构数。

igraph_error_t igraph_count_isomorphisms_vf2(const igraph_t *graph1, const igraph_t *graph2,
                                  const igraph_vector_int_t *vertex_color1,
                                  const igraph_vector_int_t *vertex_color2,
                                  const igraph_vector_int_t *edge_color1,
                                  const igraph_vector_int_t *edge_color2,
                                  igraph_integer_t *count,
                                  igraph_isocompat_t *node_compat_fn,
                                  igraph_isocompat_t *edge_compat_fn,
                                  void *arg);

此函数计算两个图之间的同构映射数。它使用通用 igraph_get_isomorphisms_vf2_callback() 函数。

参数： 

graph1:

第一个输入图，可以是有向图或无向图。

graph2:

第二个输入图，它必须与 graph1 具有相同的方向性，否则将报告错误。

vertex_color1:

第一个图的可选颜色向量。如果为两个图都提供了颜色向量，则在着色图上计算同构；即，两个顶点只有在颜色也匹配时才能匹配。如果您的图未着色，请在此处提供空指针。

vertex_color2:

第二个图的可选颜色向量。有关说明，请参阅上一个参数。

edge_color1:

第一个图的可选边颜色向量。两个图中的匹配边也必须具有匹配的颜色。如果您的图未进行边着色，请在此处提供空指针。

edge_color2:

第二个图的边颜色向量。

count:

指向整数的指针，结果将存储在此处。

node_compat_fn:

指向类型为 igraph_isocompat_t 的函数的指针。此函数将由算法调用，以确定两个节点是否兼容。

edge_compat_fn:

指向类型为 igraph_isocompat_t 的函数的指针。此函数将由算法调用，以确定两条边是否兼容。

arg:

要提供给函数 node_compat_fn 和 edge_compat_fn 的额外参数。

返回值： 

错误代码。

另请参阅： 

igraph_count_automorphisms()

时间复杂度：指数级。

3.3. igraph_get_isomorphisms_vf2 — 收集两个图的所有同构映射。

igraph_error_t igraph_get_isomorphisms_vf2(const igraph_t *graph1,
                                const igraph_t *graph2,
                                const igraph_vector_int_t *vertex_color1,
                                const igraph_vector_int_t *vertex_color2,
                                const igraph_vector_int_t *edge_color1,
                                const igraph_vector_int_t *edge_color2,
                                igraph_vector_int_list_t *maps,
                                igraph_isocompat_t *node_compat_fn,
                                igraph_isocompat_t *edge_compat_fn,
                                void *arg);

此函数查找两个简单图之间的所有同构映射。它使用 igraph_get_isomorphisms_vf2_callback() 函数。使用与 graph1 和 graph2 相同的图调用该函数以获取自同构。

参数： 

graph1:

第一个输入图，可以是有向图或无向图。

graph2:

第二个输入图，它必须与 graph1 具有相同的方向性，否则将报告错误。

vertex_color1:

第一个图的可选颜色向量。如果为两个图都提供了颜色向量，则在着色图上计算同构；即，两个顶点只有在颜色也匹配时才能匹配。如果您的图未着色，请在此处提供空指针。

vertex_color2:

第二个图的可选颜色向量。有关说明，请参阅上一个参数。

edge_color1:

第一个图的可选边颜色向量。两个图中的匹配边也必须具有匹配的颜色。如果您的图未进行边着色，请在此处提供空指针。

edge_color2:

第二个图的边颜色向量。

maps:

指向整数向量列表的指针。如果输入图不同构，则在返回时为空。否则，它包含指向 igraph_vector_int_t 对象的指针，每个向量都是 graph2 到 graph1 的同构映射。

node_compat_fn:

指向类型为 igraph_isocompat_t 的函数的指针。此函数将由算法调用，以确定两个节点是否兼容。

edge_compat_fn:

指向类型为 igraph_isocompat_t 的函数的指针。此函数将由算法调用，以确定两条边是否兼容。

arg:

要提供给函数 node_compat_fn 和 edge_compat_fn 的额外参数。

返回值： 

错误代码。

时间复杂度：指数级。

3.4. igraph_get_isomorphisms_vf2_callback — 通用 VF2 接口

igraph_error_t igraph_get_isomorphisms_vf2_callback(
    const igraph_t *graph1, const igraph_t *graph2,
    const igraph_vector_int_t *vertex_color1, const igraph_vector_int_t *vertex_color2,
    const igraph_vector_int_t *edge_color1, const igraph_vector_int_t *edge_color2,
    igraph_vector_int_t *map12, igraph_vector_int_t *map21,
    igraph_isohandler_t *isohandler_fn, igraph_isocompat_t *node_compat_fn,
    igraph_isocompat_t *edge_compat_fn, void *arg
);

此函数是 VF2 同构算法的实现，请参阅 P. Foggia、C. Sansone、M. Vento，《An Improved algorithm for matching large graphs》，Proc. of the 3rd IAPR-TC-15 International Workshop on Graph-based Representations, Italy, 2001。

要使用它，您需要定义一个类型为 igraph_isohandler_t 的回调函数。每当 VF2 找到两个图之间的同构时，都会调用此函数。两个图之间的映射也将提供给此函数。如果回调返回 IGRAPH_SUCCESS，则搜索将继续，否则将停止。 IGRAPH_STOP 作为返回值可用于指示正常的过早终止；任何其他返回值都将被视为 igraph 错误代码，从而使调用方函数也返回相同的错误代码。回调函数不得销毁传递给它的映射向量。

参数： 

graph1:

第一个输入图。

graph2:

第二个输入图。

vertex_color1:

第一个图的可选颜色向量。如果为两个图都提供了颜色向量，则在着色图上计算同构；即，两个顶点只有在颜色也匹配时才能匹配。如果您的图未着色，请在此处提供空指针。

vertex_color2:

第二个图的可选颜色向量。有关说明，请参阅上一个参数。

edge_color1:

第一个图的可选边颜色向量。两个图中的匹配边也必须具有匹配的颜色。如果您的图未进行边着色，请在此处提供空指针。

edge_color2:

第二个图的边颜色向量。

map12:

指向已初始化向量的指针或 NULL。如果不为 NULL 且提供的图同构，则此处存储将 graph1 带到 graph 的排列。如果不为 NULL 且图不同构，则返回零长度向量。

map21:

这与 map12 相同，但用于将 graph2 带到 graph1 的排列。

isohandler_fn:

如果在找到同构时要调用的回调函数。另请参阅 igraph_isohandler_t。

node_compat_fn:

指向类型为 igraph_isocompat_t 的函数的指针。此函数将由算法调用，以确定两个节点是否兼容。

edge_compat_fn:

指向类型为 igraph_isocompat_t 的函数的指针。此函数将由算法调用，以确定两条边是否兼容。

arg:

要提供给函数 isohandler_fn、node_compat_fn 和 edge_compat_fn 的额外参数。

返回值： 

错误代码。

时间复杂度：指数级。

3.5. igraph_isohandler_t — 回调类型，在找到同构时调用

typedef igraph_error_t igraph_isohandler_t(const igraph_vector_int_t *map12,
        const igraph_vector_int_t *map21, void *arg);

有关详细信息，请参见 igraph_get_isomorphisms_vf2_callback() 的文档。

参数： 

map12:

从第一个图到第二个图的映射。

map21:

从第二个图到第一个图的映射，基本上是 map12 的逆。

arg:

此额外参数在调用 igraph_get_isomorphisms_vf2_callback() 时传递给它。

返回值： 

IGRAPH_SUCCESS 继续搜索，IGRAPH_STOP 终止搜索。任何其他返回值都将被解释为 igraph 错误代码，然后将中止搜索并从调用方函数返回相同的错误代码。

3.6. igraph_isocompat_t — 回调类型，用于检查两个顶点或边是否兼容

typedef igraph_bool_t igraph_isocompat_t(const igraph_t *graph1,
        const igraph_t *graph2,
        const igraph_integer_t g1_num,
        const igraph_integer_t g2_num,
        void *arg);

可以通过在图的顶点和/或边上定义关系，然后检查顶点（边）是否根据这些关系匹配来限制 VF2（子图）同构函数。

此功能通过两个回调实现，一个用于顶点，一个用于边。每当 igraph 尝试将第一个（子）图的顶点（边）与第二个图的顶点匹配时，都会调用顶点（边）兼容性回调。回调返回一个逻辑值，指示两个顶点是否匹配。

两个回调函数的类型均为 igraph_isocompat_t。

参数： 

graph1:

第一个图。

graph2:

第二个图。

g1_num:

第一个图中顶点或边的 ID。

g2_num:

第二个图中顶点或边的 ID。

arg:

要传递给回调函数的额外参数。

返回值： 

逻辑标量，指示 graph1 中的顶点（或边）g1_num 是否与 graph2 中的顶点（或边）g2_num 兼容。

3.7. igraph_subisomorphic_vf2 — 使用 VF2 确定子图同构

igraph_error_t igraph_subisomorphic_vf2(const igraph_t *graph1, const igraph_t *graph2,
                             const igraph_vector_int_t *vertex_color1,
                             const igraph_vector_int_t *vertex_color2,
                             const igraph_vector_int_t *edge_color1,
                             const igraph_vector_int_t *edge_color2,
                             igraph_bool_t *iso, igraph_vector_int_t *map12,
                             igraph_vector_int_t *map21,
                             igraph_isocompat_t *node_compat_fn,
                             igraph_isocompat_t *edge_compat_fn,
                             void *arg);

确定 graph1 的子图是否与 graph2 同构。它使用 igraph_get_subisomorphisms_vf2_callback()。

参数： 

graph1:

第一个输入图，可以是有向图或无向图。这应该是更大的图。

graph2:

第二个输入图，它必须与 graph1 具有相同的方向性。这应该是较小的图。

vertex_color1:

第一个图的可选颜色向量。如果为两个图都提供了颜色向量，则在着色图上计算子图同构；即，两个顶点只有在颜色也匹配时才能匹配。如果您的图未着色，请在此处提供空指针。

vertex_color2:

第二个图的可选颜色向量。有关说明，请参阅上一个参数。

edge_color1:

第一个图的可选边颜色向量。两个图中的匹配边也必须具有匹配的颜色。如果您的图未进行边着色，请在此处提供空指针。

edge_color2:

第二个图的边颜色向量。

iso:

指向布尔值的指针。决策问题的结果存储在此处。

map12:

指向向量的指针或 NULL。如果不为 NULL，则此处存储从 graph1 到 graph2 的同构映射。

map21:

指向向量 ot NULL 的指针。如果不为 NULL，则此处存储从 graph2 到 graph1 的同构映射。

node_compat_fn:

指向类型为 igraph_isocompat_t 的函数的指针。此函数将由算法调用，以确定两个节点是否兼容。

edge_compat_fn:

指向类型为 igraph_isocompat_t 的函数的指针。此函数将由算法调用，以确定两条边是否兼容。

arg:

要提供给函数 node_compat_fn 和 edge_compat_fn 的额外参数。

返回值： 

错误代码。

时间复杂度：指数级。

3.8. igraph_count_subisomorphisms_vf2 — 使用 VF2 的子图同构数

igraph_error_t igraph_count_subisomorphisms_vf2(const igraph_t *graph1, const igraph_t *graph2,
                                     const igraph_vector_int_t *vertex_color1,
                                     const igraph_vector_int_t *vertex_color2,
                                     const igraph_vector_int_t *edge_color1,
                                     const igraph_vector_int_t *edge_color2,
                                     igraph_integer_t *count,
                                     igraph_isocompat_t *node_compat_fn,
                                     igraph_isocompat_t *edge_compat_fn,
                                     void *arg);

计算 graph1 的子图和 graph2 之间的同构数。此函数使用 igraph_get_subisomorphisms_vf2_callback()。

参数： 

graph1:

第一个输入图，可以是有向图或无向图。这应该是更大的图。

graph2:

第二个输入图，它必须与 graph1 具有相同的方向性。这应该是较小的图。

vertex_color1:

第一个图的可选颜色向量。如果为两个图都提供了颜色向量，则在着色图上计算子图同构；即，两个顶点只有在颜色也匹配时才能匹配。如果您的图未着色，请在此处提供空指针。

vertex_color2:

第二个图的可选颜色向量。有关说明，请参阅上一个参数。

edge_color1:

第一个图的可选边颜色向量。两个图中的匹配边也必须具有匹配的颜色。如果您的图未进行边着色，请在此处提供空指针。

edge_color2:

第二个图的边颜色向量。

count:

指向整数的指针。子图同构数存储在此处。

node_compat_fn:

指向类型为 igraph_isocompat_t 的函数的指针。此函数将由算法调用，以确定两个节点是否兼容。

edge_compat_fn:

指向类型为 igraph_isocompat_t 的函数的指针。此函数将由算法调用，以确定两条边是否兼容。

arg:

要提供给函数 node_compat_fn 和 edge_compat_fn 的额外参数。

返回值： 

错误代码。

时间复杂度：指数级。

3.9. igraph_get_subisomorphisms_vf2 — 返回所有子图同构映射。

igraph_error_t igraph_get_subisomorphisms_vf2(const igraph_t *graph1,
                                   const igraph_t *graph2,
                                   const igraph_vector_int_t *vertex_color1,
                                   const igraph_vector_int_t *vertex_color2,
                                   const igraph_vector_int_t *edge_color1,
                                   const igraph_vector_int_t *edge_color2,
                                   igraph_vector_int_list_t *maps,
                                   igraph_isocompat_t *node_compat_fn,
                                   igraph_isocompat_t *edge_compat_fn,
                                   void *arg);

此函数收集 graph2 到 graph1 的子图的所有同构映射。它使用 igraph_get_subisomorphisms_vf2_callback() 函数。这些图应该是简单的。

参数： 

graph1:

第一个输入图，可以是有向图或无向图。这应该是更大的图。

graph2:

第二个输入图，它必须与 graph1 具有相同的方向性。这应该是较小的图。

vertex_color1:

第一个图的可选颜色向量。如果为两个图都提供了颜色向量，则在着色图上计算子图同构；即，两个顶点只有在颜色也匹配时才能匹配。如果您的图未着色，请在此处提供空指针。

vertex_color2:

第二个图的可选颜色向量。有关说明，请参阅上一个参数。

edge_color1:

第一个图的可选边颜色向量。两个图中的匹配边也必须具有匹配的颜色。如果您的图未进行边着色，请在此处提供空指针。

edge_color2:

第二个图的边颜色向量。

maps:

指向整数向量列表的指针。在返回时，它包含指向 igraph_vector_int_t 对象的指针，每个向量都是 graph2 到 graph1 的子图的同构映射。

node_compat_fn:

指向类型为 igraph_isocompat_t 的函数的指针。此函数将由算法调用，以确定两个节点是否兼容。

edge_compat_fn:

指向类型为 igraph_isocompat_t 的函数的指针。此函数将由算法调用，以确定两条边是否兼容。

arg:

要提供给函数 node_compat_fn 和 edge_compat_fn 的额外参数。

返回值： 

错误代码。

时间复杂度：指数级。

3.10. igraph_get_subisomorphisms_vf2_callback — 用于子图同构问题的通用 VF2 函数。

igraph_error_t igraph_get_subisomorphisms_vf2_callback(
    const igraph_t *graph1, const igraph_t *graph2,
    const igraph_vector_int_t *vertex_color1, const igraph_vector_int_t *vertex_color2,
    const igraph_vector_int_t *edge_color1, const igraph_vector_int_t *edge_color2,
    igraph_vector_int_t *map12, igraph_vector_int_t *map21,
    igraph_isohandler_t *isohandler_fn, igraph_isocompat_t *node_compat_fn,
    igraph_isocompat_t *edge_compat_fn, void *arg
);

此函数是 igraph_get_isomorphisms_vf2_callback() 的对，用于子图同构问题。它搜索 graph1 中与 graph2 同构的子图。当它找到同构映射时，它会调用提供的回调 isohandler_fn。映射（及其逆）和额外的 arg 参数将提供给回调。

参数： 

graph1:

第一个输入图，可以是有向图或无向图。这应该是更大的图。

graph2:

第二个输入图，它必须与 graph1 具有相同的方向性。这应该是较小的图。

vertex_color1:

第一个图的可选颜色向量。如果为两个图都提供了颜色向量，则在着色图上计算子图同构；即，两个顶点只有在颜色也匹配时才能匹配。如果您的图未着色，请在此处提供空指针。

vertex_color2:

第二个图的可选颜色向量。有关说明，请参阅上一个参数。

edge_color1:

第一个图的可选边颜色向量。两个图中的匹配边也必须具有匹配的颜色。如果您的图未进行边着色，请在此处提供空指针。

edge_color2:

第二个图的边颜色向量。

map12:

指向向量的指针或 NULL。如果不为 NULL，则此处存储从 graph1 到 graph2 的同构映射。

map21:

指向向量 ot NULL 的指针。如果不为 NULL，则此处存储从 graph2 到 graph1 的同构映射。

isohandler_fn:

指向类型为 igraph_isohandler_t 的函数的指针。每当找到子图同构时，都会调用此函数。如果函数返回 IGRAPH_SUCCESS，则搜索将继续。如果函数返回 IGRAPH_STOP，则搜索将正常终止。任何其他值都将被视为 igraph 错误代码。

node_compat_fn:

指向类型为 igraph_isocompat_t 的函数的指针。此函数将由算法调用，以确定两个节点是否兼容。

edge_compat_fn:

指向类型为 igraph_isocompat_t 的函数的指针。此函数将由算法调用，以确定两条边是否兼容。

arg:

要提供给函数 isohandler_fn、node_compat_fn 和 edge_compat_fn 的额外参数。

返回值： 

错误代码。

时间复杂度：指数级。

3.11. 弃用的别名

3.11.1. igraph_isomorphic_function_vf2 — 通用 VF2 接口（弃用的别名）。
3.11.2. igraph_subisomorphic_function_vf2 — 用于子图同构问题的通用 VF2 函数（弃用的别名）。

3.11.1. igraph_isomorphic_function_vf2 — 通用 VF2 接口（弃用的别名）。

igraph_error_t igraph_isomorphic_function_vf2(
    const igraph_t *graph1, const igraph_t *graph2,
    const igraph_vector_int_t *vertex_color1, const igraph_vector_int_t *vertex_color2,
    const igraph_vector_int_t *edge_color1, const igraph_vector_int_t *edge_color2,
    igraph_vector_int_t *map12, igraph_vector_int_t *map21,
    igraph_isohandler_t *isohandler_fn, igraph_isocompat_t *node_compat_fn,
    igraph_isocompat_t *edge_compat_fn, void *arg
);

警告

自 0.10.0 版本起已弃用。请勿在新代码中使用此函数；请改用 igraph_get_isomorphisms_vf2_callback()。

3.11.2. igraph_subisomorphic_function_vf2 — 用于子图同构问题的通用 VF2 函数（弃用的别名）。

igraph_error_t igraph_subisomorphic_function_vf2(
    const igraph_t *graph1, const igraph_t *graph2,
    const igraph_vector_int_t *vertex_color1, const igraph_vector_int_t *vertex_color2,
    const igraph_vector_int_t *edge_color1, const igraph_vector_int_t *edge_color2,
    igraph_vector_int_t *map12, igraph_vector_int_t *map21,
    igraph_isohandler_t *isohandler_fn, igraph_isocompat_t *node_compat_fn,
    igraph_isocompat_t *edge_compat_fn, void *arg
);

警告

自 0.10.0 版本起已弃用。请勿在新代码中使用此函数；请改用 igraph_get_subisomorphisms_vf2_callback()。

4. LAD 算法

4.1. igraph_subisomorphic_lad — 使用 LAD 算法检查子图同构

LAD 算法可以在较大的图中搜索子图，或检查两个图是否同构。请参阅 Christine Solnon: AllDifferent-based Filtering for Subgraph Isomorphism. Artificial Intelligence, 174(12-13):850-864, 2010. https://doi.org/10.1016/j.artint.2010.05.002 以及 LAD 库的主页 http://liris.cnrs.fr/csolnon/LAD.html igraph 中的实现基于 LADv1，但已修改为使用 igraph 自己的内存分配和错误处理。

LAD 使用域的概念来指示匹配模式图时的顶点兼容性。域可用于实现着色顶点的匹配。

LAD 适用于有向图和无向图。不支持具有多重边的图。

4.1. igraph_subisomorphic_lad — 使用 LAD 算法检查子图同构

igraph_error_t igraph_subisomorphic_lad(const igraph_t *pattern, const igraph_t *target,
                             const igraph_vector_int_list_t *domains,
                             igraph_bool_t *iso, igraph_vector_int_t *map,
                             igraph_vector_int_list_t *maps,
                             igraph_bool_t induced, igraph_integer_t time_limit);

检查 pattern 是否与 target 的子图同构。Christine Solnon 的原始 LAD 实现用作此代码的基础。

有关 LAD 的更多信息，请参见 http://liris.cnrs.fr/csolnon/LAD.html 和 Christine Solnon: AllDifferent-based Filtering for Subgraph Isomorphism. Artificial Intelligence, 174(12-13):850-864, 2010. https://doi.org/10.1016/j.artint.2010.05.002

参数： 

pattern:

较小的图，可以是有向图或无向图。

目标:

更大的图，可以是有向图或无向图。

domains:

一个整数向量列表，可以是 NULL。每个向量的长度必须与 pattern 图中的顶点数匹配。对于每个顶点，列出了目标图中兼容顶点的 ID。

iso:

指向布尔值的指针，或一个空指针。如果不是空指针，则如果找到子图同构，则布尔值设置为 true，否则设置为 false。

map:

指向向量的指针或一个空指针。如果不是空指针且找到子图同构，则目标图中匹配的顶点将在此处列出，对应于模式图中的每个顶点（按顶点 ID 顺序）。

maps:

指向整数向量列表的指针或一个空指针。如果不是空指针，则所有子图同构都将存储在向量列表中，以 igraph_vector_int_t 对象的形式存储。

induced:

布尔值，是否搜索诱导匹配子图。

time_limit:

处理器时间限制，以秒为单位。此处提供零表示没有限制。如果超过时间限制，则该函数会发出错误信号。

返回值： 

错误代码

另请参阅： 

关于 VF2 算法，请参见 igraph_subisomorphic_vf2()。

时间复杂度：指数级。

示例 17.2.  文件 examples/simple/igraph_subisomorphic_lad.c

#include <igraph.h>

void print_maps(igraph_vector_int_t *map, igraph_vector_int_list_t *maps) {
    igraph_integer_t n, i;
    igraph_vector_int_print(map);
    n = igraph_vector_int_list_size(maps);
    for (i = 0; i < n; i++) {
        igraph_vector_int_t *v = igraph_vector_int_list_get_ptr(maps, i);
        igraph_vector_int_print(v);
    }
    igraph_vector_int_list_clear(maps);
}

int main(void) {
    igraph_t target, pattern;
    igraph_bool_t iso;
    igraph_vector_int_t map;
    igraph_vector_int_list_t maps;
    igraph_integer_t i;
    int domainsvec[] = { 0, 2, 8, -1,
                         4, 5, 6, 7, -1,
                         1, 3, 5, 6, 7, 8, -1,
                         0, 2, 8, -1,
                         1, 3, 7, 8, -1, -2
                       };
    igraph_vector_int_list_t domains;
    igraph_vector_int_t v;

    igraph_small(&target, 9, IGRAPH_UNDIRECTED,
                 0, 1, 0, 4, 0, 6,
                 1, 4, 1, 2,
                 2, 3,
                 3, 4, 3, 5, 3, 7, 3, 8,
                 4, 5, 4, 6,
                 5, 6, 5, 8,
                 7, 8,
                 -1);

    igraph_small(&pattern, 5, IGRAPH_UNDIRECTED,
                 0, 1, 0, 4,
                 1, 4, 1, 2,
                 2, 3,
                 3, 4,
                 -1);

    igraph_vector_int_init(&map, 0);
    igraph_vector_int_list_init(&maps, 0);

    igraph_subisomorphic_lad(&pattern, &target, /*domains=*/ NULL, &iso, &map,
                             &maps, /*induced=*/ false, /*time_limit=*/ 0);

    if (!iso) {
        return 1;
    }
    print_maps(&map, &maps);

    printf("---------\n");

    igraph_subisomorphic_lad(&pattern, &target, /*domains=*/ NULL, &iso, &map,
                             &maps, /*induced=*/ true, /*time_limit=*/ 0);

    if (!iso) {
        return 2;
    }
    print_maps(&map, &maps);

    printf("---------\n");

    igraph_vector_int_list_init(&domains, 0);
    i = 0;
    igraph_vector_int_init(&v, 0);
    while (1) {
        if (domainsvec[i] == -2) {
            break;
        } else if (domainsvec[i] == -1) {
            igraph_vector_int_list_push_back_copy(&domains, &v);
            igraph_vector_int_clear(&v);
        } else {
            igraph_vector_int_push_back(&v, domainsvec[i]);
        }
        i++;
    }
    igraph_vector_int_destroy(&v);

    igraph_subisomorphic_lad(&pattern, &target, &domains, &iso, &map, &maps,
                             /*induced=*/ false, /*time_limit=*/ 0);

    if (!iso) {
        return 3;
    }
    print_maps(&map, &maps);

    igraph_vector_int_list_destroy(&domains);
    igraph_vector_int_destroy(&map);
    igraph_vector_int_list_destroy(&maps);

    igraph_destroy(&pattern);
    igraph_destroy(&target);


    return 0;
}


5. 小型图的函数

5.1. igraph_isoclass — 确定小型图的同构类。
5.2. igraph_isoclass_subgraph — 图的子图的同构类。
5.3. igraph_isoclass_create — 从给定的同构类创建图。
5.4. igraph_graph_count — 给定顶点数的未标记图的数量。

5.1. igraph_isoclass — 确定小型图的同构类。

igraph_error_t igraph_isoclass(const igraph_t *graph, igraph_integer_t *isoclass);

具有给定顶点数的所有图都属于多个同构类，给定类中的每个图都彼此同构。

此函数给出图的同构类（一个数字）。两个图具有相同的同构类当且仅当它们是同构的。

第一个同构类编号为零，它包含无边图。最后一个同构类包含完整图。具有三个顶点的有向图的同构类数量为 16 个（介于 0 和 15 之间），无向图仅为 4 个。对于具有四个顶点的图，有 218 个（有向图）和 11 个（无向图）。对于 5 个和 6 个顶点的无向图，分别为 34 和 156。这些值也可以使用 igraph_graph_count() 检索。有关更多信息，请参见 https://oeis.org/A000273 和 https://oeis.org/A000088。

目前，支持 3 个和 4 个顶点的有向图以及 3 到 6 个顶点的无向图。

此函数忽略多重边和自环。

参数： 

图:

图对象。

isoclass:

指向整数的指针，同构类将存储在此处。

返回值： 

错误代码。

另请参阅： 

请参见 igraph_isomorphic()、igraph_isoclass_subgraph()、igraph_isoclass_create()、igraph_motifs_randesu()。

由于某些限制，此函数仅适用于具有三个或四个顶点的图。

时间复杂度： O(|E|)，图中的边数。

5.2. igraph_isoclass_subgraph — 图的子图的同构类。

igraph_error_t igraph_isoclass_subgraph(const igraph_t *graph, const igraph_vector_int_t *vids,
                             igraph_integer_t *isoclass);

此函数标识由 vids 中指定的顶点诱导的子图的同构类。

目前，支持 3 个和 4 个顶点的有向图以及 3 到 6 个顶点的无向图。

此函数忽略多重边和自环。

参数： 

图:

图对象。

vids:

包含要视为子图的顶点 ID 的向量。每个顶点 ID 最多应包含一次。

isoclass:

指向整数的指针，这将设置为同构类。

返回值： 

错误代码。

另请参阅： 

请参见 igraph_isoclass()、igraph_isomorphic()、igraph_isoclass_create()。

时间复杂度：O((d+n)*n)，其中 d 是网络中的平均度，n 是 vids 中的顶点数。

5.3. igraph_isoclass_create — 从给定的同构类创建图。

igraph_error_t igraph_isoclass_create(igraph_t *graph, igraph_integer_t size,
                           igraph_integer_t number, igraph_bool_t directed);

此函数创建给定同构类的规范代表图。

同构类是一个介于 0 和给定顶点数和有向性的唯一未标记（即非同构）图的数量之间的整数。有关 size 节点上的有向图和无向图的数量，请参见 https://oeis.org/A000273 和 https://oeis.org/A000088。

目前，支持 3 个和 4 个顶点的有向图以及 3 到 6 个顶点的无向图。

参数： 

图:

指向未初始化的图对象的指针。

size:

要添加到图中的顶点数。

数字:

同构类。

有向:

布尔常量，是否创建有向图。

返回值： 

错误代码。

另请参阅： 

请参见 igraph_isoclass()、igraph_isoclass_subgraph()、igraph_isomorphic()。

时间复杂度：O(|V|+|E|)，创建的图中顶点数加上边数。

5.4. igraph_graph_count — 给定顶点数的未标记图的数量。

igraph_error_t igraph_graph_count(igraph_integer_t n, igraph_bool_t directed, igraph_integer_t *count);

给出指定顶点数的未标记简单图的数量。此大小的图的“isoclass”最多比此值小 1。

此函数旨在与 isoclass 和 motif 查找器函数结合使用。它仅适用于小的 n 值，对于这些值，结果可以用 igraph_integer_t 表示。对于较大的 n 值，会引发溢出错误。

参数： 

n:

顶点数。

有向:

布尔值，是否考虑有向图。

count:

指向整数的指针，结果将存储在此处。

返回值： 

错误代码。

另请参阅： 

请参见 igraph_isoclass()、igraph_motifs_randesu_callback()。

时间复杂度：O(1)。

6. 实用函数

6.1. igraph_permute_vertices — 排列顶点。
6.2. igraph_simplify_and_colorize — 简化图并计算自环和边多重性。

6.1. igraph_permute_vertices — 排列顶点。

igraph_error_t igraph_permute_vertices(const igraph_t *graph, igraph_t *res,
                                       const igraph_vector_int_t *permutation);

此函数通过根据指定的映射排列其顶点，从输入图创建新图。使用 igraph_canonical_permutation() 的输出来调用此函数，以创建图的规范形式。

参数： 

图:

输入图。

res:

指向未初始化的图对象的指针。新图在此处创建。

permutation:

要应用的排列。顶点 0 映射到向量的第一个元素，顶点 1 映射到第二个元素，依此类推。

返回值： 

错误代码。

时间复杂度：O(|V|+|E|)，相对于顶点数和边数是线性的。

6.2. igraph_simplify_and_colorize — 简化图并计算自环和边多重性。

igraph_error_t igraph_simplify_and_colorize(
    const igraph_t *graph, igraph_t *res,
    igraph_vector_int_t *vertex_color, igraph_vector_int_t *edge_color);

此函数从输入图创建顶点和边着色的简单图。顶点颜色计算为输入图中每个顶点的入射自环数。边颜色计算为输入图中合并以创建简单图中每条边的并行边数。

生成的彩色简单图适合被同构检查算法（例如 VF2）使用，该算法仅支持简单图，但可以考虑顶点和边颜色。

参数： 

图:

图对象，通常具有自环或多重边。

res:

一个未初始化的图对象。结果将存储在此处。

vertex_color:

计算出的对应于自环多重性的顶点颜色。

edge_color:

计算出的对应于边多重性的边颜色。

返回值： 

错误代码。

另请参阅： 

请参见 igraph_simplify()、igraph_isomorphic_vf2()、igraph_subisomorphic_vf2()

7. 已弃用的函数

7.1. igraph_isomorphic_34 — 3-4 个顶点的图同构（已弃用）。

7.1. igraph_isomorphic_34 — 3-4 个顶点的图同构（已弃用）。

igraph_error_t igraph_isomorphic_34(
    const igraph_t *graph1, const igraph_t *graph2, igraph_bool_t *iso
);

警告

自 0.10.0 版本起已弃用。请不要在新代码中使用此函数；请改用 igraph_isomorphic()。

如果您确实关心性能，并且您确定您的输入图是简单的，并且对于有向图具有 3 或 4 个顶点，或者对于无向图具有 3-6 个顶点，您可以比较从 igraph_isoclass() 获得的同构类，而不是调用 igraph_isomorphic()；这节省了检查图是否不包含多重边或自环的成本。

参数： 

graph1:

第一个输入图。

graph2:

第二个输入图。必须与 graph1 具有相同的有向性。

iso:

指向布尔值的指针，结果存储在此处。

返回值： 

错误代码。

时间复杂度：O(1)。

← 第 16 章. 团和独立顶点集 第 18 章. 图着色 →