igraph 参考手册

用于使用 igraph C 库

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

第 16 章. 团和独立顶点集

1. 团
2. 加权团
3. 独立顶点集

这些函数计算与团和独立顶点集相关的各种图属性。

1. 团

1.1. igraph_is_complete — 确定图是否是完全图。
1.2. igraph_is_clique — 顶点集是否构成团？
1.3. igraph_cliques — 在图中查找所有或某些团。
1.4. igraph_clique_size_hist — 统计图中每个大小的团的数量。
1.5. igraph_cliques_callback — 为图中的每个团调用一个函数。
1.6. igraph_clique_handler_t — 团处理函数类型。
1.7. igraph_largest_cliques — 在图中查找最大团。
1.8. igraph_maximal_cliques — 在图中查找所有极大团。
1.9. igraph_maximal_cliques_count — 计算图中极大团的数量。
1.10. igraph_maximal_cliques_file — 查找极大团并将它们写入文件。
1.11. igraph_maximal_cliques_subset — 初始顶点子集的极大团。
1.12. igraph_maximal_cliques_hist — 统计图中每个大小的极大团的数量。
1.13. igraph_maximal_cliques_callback — 在图中查找极大团并为每个团调用一个函数。
1.14. igraph_clique_number — 查找图的团数。

1.1. igraph_is_complete — 确定图是否是完全图。

igraph_error_t igraph_is_complete(const igraph_t *graph, igraph_bool_t *res);

警告

此函数是实验性的，其签名尚未被视为最终签名。我们保留更改函数签名的权利，而无需更改 igraph 的主要版本。使用它需要您自担风险。

如果所有不同的顶点对都是相邻的，则认为图是完全图。

空图和单例图被认为是完全图。

参数： 

图:

要分析的图对象。

res:

指向布尔变量的指针，结果将存储在此处。

返回值： 

错误代码。

时间复杂度：最坏情况下为 O(|V| + |E|)。

1.2. igraph_is_clique — 顶点集是否构成团？

igraph_error_t igraph_is_clique(const igraph_t *graph, igraph_vs_t candidate,
                                igraph_bool_t directed, igraph_bool_t *res);

警告

此函数是实验性的，其签名尚未被视为最终签名。我们保留更改函数签名的权利，而无需更改 igraph 的主要版本。使用它需要您自担风险。

测试顶点集中的所有对是否相邻，即它们是否构成团。空集和单例集被认为是团。

参数： 

图:

输入图。

candidate:

要测试是否为团的顶点集。

有向:

是否在有向图中考虑边的方向。

res:

结果将存储在此处。

返回值： 

错误代码。

另请参阅： 

igraph_is_complete() 用于测试图是否是完全图； igraph_is_independent_vertex_set() 用于测试独立顶点集； igraph_cliques()、 igraph_maximal_cliques() 和 igraph_largest_cliques() 用于查找团。

时间复杂度：O(n^2 log(d))，其中 n 是候选集中的顶点数，d 是典型的顶点度。

1.3. igraph_cliques — 在图中查找所有或某些团。

igraph_error_t igraph_cliques(const igraph_t *graph, igraph_vector_int_list_t *res,
                   igraph_integer_t min_size, igraph_integer_t max_size);

团是图的完全连接子图。

如果您只对图中最大团的大小感兴趣，请使用 igraph_clique_number()。

此函数的当前实现使用 Sampo Niskanen 和 Patric R. J. Östergård 的 Cliquer 库的 1.21 版本，http://users.aalto.fi/~pat/cliquer.html

参数： 

图:

输入图。

res:

指向已初始化的整数向量列表的指针。团将作为顶点 ID 的向量存储在此处。

min_size:

整数，指定要返回的团的最小大小。如果为负数或零，则不使用下限。

max_size:

整数，指定要返回的团的最大大小。如果为负数或零，则不使用上限。

返回值： 

错误代码。

另请参阅： 

igraph_largest_cliques() 和 igraph_clique_number()。

时间复杂度：指数级

示例 16.1.  文件 examples/simple/igraph_cliques.c

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

int compare_vectors(const igraph_vector_int_t *v1, const igraph_vector_int_t *v2) {
    igraph_integer_t s1, s2, i;

    s1 = igraph_vector_int_size(v1);
    s2 = igraph_vector_int_size(v2);
    if (s1 < s2) {
        return -1;
    }
    if (s1 > s2) {
        return 1;
    }
    for (i = 0; i < s1; ++i) {
        if (VECTOR(*v1)[i] < VECTOR(*v2)[i]) {
            return -1;
        }
        if (VECTOR(*v1)[i] > VECTOR(*v2)[i]) {
            return 1;
        }
    }
    return 0;
}

/* Takes a pointer vector of vectors. Sorts each vector, then sorts the pointer vector */
void canonicalize_list(igraph_vector_int_list_t *list) {
    igraph_integer_t len = igraph_vector_int_list_size(list);
    for (igraph_integer_t i = 0; i < len; ++i) {
        igraph_vector_int_sort(igraph_vector_int_list_get_ptr(list, i));
    }
    igraph_vector_int_list_sort(list, &compare_vectors);
}

struct userdata {
    igraph_integer_t i;
    igraph_vector_int_list_t *list;
};

igraph_error_t handler(const igraph_vector_int_t *clique, void *arg) {
    struct userdata *ud;
    igraph_bool_t cont;

    ud = (struct userdata *) arg;
    cont = 1; /* true */

    if (compare_vectors(clique, igraph_vector_int_list_get_ptr(ud->list, ud->i)) != 0) {
        printf("igraph_cliques() and igraph_cliques_callback() give different results.\n");
        cont = 0; /* false */
    }

    ud->i += 1;

    return cont ? IGRAPH_SUCCESS : IGRAPH_STOP;
}

void test_callback(const igraph_t *graph) {
    igraph_vector_int_list_t list;
    struct userdata ud;

    igraph_vector_int_list_init(&list, 0);
    igraph_cliques(graph, &list, 0, 0);

    ud.i = 0;
    ud.list = &list;

    igraph_cliques_callback(graph, 0, 0, &handler, (void *) &ud);

    igraph_vector_int_list_destroy(&list);
}


int main(void) {

    igraph_t g;
    igraph_vector_int_list_t result;
    igraph_es_t es;
    igraph_integer_t omega;
    igraph_integer_t i, j, n;
    const int params[] = {4, -1, 2, 2, 0, 0, -1, -1};

    igraph_set_warning_handler(igraph_warning_handler_ignore);

    igraph_vector_int_list_init(&result, 0);
    igraph_full(&g, 6, 0, 0);
    igraph_es_pairs_small(&es, 0, 0, 1, 0, 2, 3, 5, -1);
    igraph_delete_edges(&g, es);
    igraph_es_destroy(&es);

    for (j = 0; j < sizeof(params) / (2 * sizeof(params[0])); j++) {
        if (params[2 * j + 1] != 0) {
            igraph_cliques(&g, &result, params[2 * j], params[2 * j + 1]);
        } else {
            igraph_largest_cliques(&g, &result);
        }
        n = igraph_vector_int_list_size(&result);
        printf("%" IGRAPH_PRId " cliques found\n", n);
        canonicalize_list(&result);
        for (i = 0; i < n; i++) {
            igraph_vector_int_t* v = igraph_vector_int_list_get_ptr(&result, i);
            igraph_vector_int_print(v);
        }
    }

    igraph_clique_number(&g, &omega);
    printf("omega=%" IGRAPH_PRId "\n", omega);

    test_callback(&g);

    igraph_destroy(&g);

    igraph_kary_tree(&g, 5, 2, IGRAPH_TREE_OUT);
    igraph_cliques(&g, &result, 5, 5);
    if (igraph_vector_int_list_size(&result) != 0) {
        return 1;
    }

    igraph_destroy(&g);
    igraph_vector_int_list_destroy(&result);

    return 0;
}


1.4. igraph_clique_size_hist — 统计图中每个大小的团的数量。

igraph_error_t igraph_clique_size_hist(const igraph_t *graph, igraph_vector_t *hist,
                            igraph_integer_t min_size, igraph_integer_t max_size);

团是图的完全连接子图。

此函数的当前实现使用 Sampo Niskanen 和 Patric R. J. Östergård 的 Cliquer 库的 1.21 版本，http://users.aalto.fi/~pat/cliquer.html

参数： 

图:

输入图。

hist:

指向已初始化的向量的指针。结果将存储在此处。第一个元素将存储大小为 1 的团的数量，第二个元素将存储大小为 2 的团的数量，依此类推。对于小于 min_size 的团，将返回零计数。

min_size:

整数，指定要返回的团的最小大小。如果为负数或零，则不使用下限。

max_size:

整数，指定要返回的团的最大大小。如果为负数或零，则不使用上限。

返回值： 

错误代码。

另请参阅： 

igraph_cliques() 和 igraph_cliques_callback()

时间复杂度：指数级

1.5. igraph_cliques_callback — 为图中的每个团调用一个函数。

igraph_error_t igraph_cliques_callback(const igraph_t *graph,
                            igraph_integer_t min_size, igraph_integer_t max_size,
                            igraph_clique_handler_t *cliquehandler_fn, void *arg);

团是图的完全连接子图。此函数枚举给定大小范围内的所有团，并为每个团调用 cliquehandler_fn。团作为指向 igraph_vector_int_t 的指针传递给回调函数。销毁和释放此向量由用户负责。使用 igraph_vector_int_destroy() 首先销毁它，然后使用 igraph_free() 释放它。

此函数的当前实现使用 Sampo Niskanen 和 Patric R. J. Östergård 的 Cliquer 库的 1.21 版本，http://users.aalto.fi/~pat/cliquer.html

参数： 

图:

输入图。

min_size:

整数，指定要返回的团的最小大小。如果为负数或零，则不使用下限。

max_size:

整数，指定要返回的团的最大大小。如果为负数或零，则不使用上限。

cliquehandler_fn:

为每个团调用的回调函数。另请参阅 igraph_clique_handler_t。

arg:

提供给 cliquehandler_fn 的额外参数。

返回值： 

错误代码。

另请参阅： 

igraph_cliques()

时间复杂度：指数级

1.6. igraph_clique_handler_t — 团处理函数类型。

typedef igraph_error_t igraph_clique_handler_t(const igraph_vector_int_t *clique, void *arg);

回调类型，当找到团时调用。有关详细信息，请参阅 igraph_cliques_callback() 的文档。

参数： 

clique:

当前团。团归团搜索例程所有。如果您不想存储它，则无需销毁或释放它；但是，如果您想长时间保留它，则需要自行复制它并存储副本本身。

arg:

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

返回值： 

错误代码； IGRAPH_SUCCESS 继续搜索或 IGRAPH_STOP 停止搜索而不发出错误信号。

1.7. igraph_largest_cliques — 在图中查找最大团。

igraph_error_t igraph_largest_cliques(const igraph_t *graph, igraph_vector_int_list_t *res);

如果图中没有包含更多顶点的其他团，则团是最大的（非常直观）。

请注意，这不一定与极大团相同，即最大团始终是极大的，但极大团不一定是最大的。

此函数的当前实现使用 igraph_maximal_cliques_callback() 搜索极大团，并删除那些不是最大团的。

此函数的实现已在 igraph 0.5 和 0.6 之间更改，因此团的顺序和团中顶点的顺序在这两个版本之间几乎肯定会有所不同。

参数： 

图:

输入图。

res:

指向已初始化的整数向量列表的指针。团将作为顶点 ID 的向量存储在此处。

返回值： 

错误代码。

另请参阅： 

igraph_cliques()、 igraph_maximal_cliques()

时间复杂度：最坏情况下为 O(3^(|V|/3))。

1.8. igraph_maximal_cliques — 在图中查找所有极大团。

igraph_error_t igraph_maximal_cliques(
    const igraph_t *graph, igraph_vector_int_list_t *res,
    igraph_integer_t min_size, igraph_integer_t max_size
);

此函数列出大小范围内的极大团，忽略边的方向。团是顶点的一个子集，其中所有顶点对都已连接。 极大团是一个团，它不是任何更大团的严格子集。

不对返回团的顺序做任何保证。

当前实现使用 Eppstein、Löffler 和 Strash 修改的 Bron-Kerbosch 算法。

参考

David Eppstein, Maarten Löffler, Darren Strash: Listing All Maximal Cliques in Sparse Graphs in Near-Optimal Time. Algorithms and Computation, Lecture Notes in Computer Science, volume 6506, pp 403-414 (2010). https://doi.org/10.1007/978-3-642-17517-6_36 https://arxiv.org/abs/1006.5440

参数： 

图:

输入图。边的方向被忽略。

res:

指向整数向量列表的指针。极大团将作为顶点 ID 的向量返回到此处。请注意，团的顶点可能会以任意顺序返回。

min_size:

整数，给出要返回的团的最小大小。如果为负数或零，则不使用下限。

max_size:

整数，给出要返回的团的最大大小。如果为负数或零，则不使用上限。

返回值： 

错误代码。

另请参阅： 

igraph_maximal_independent_vertex_sets() 用于查找极大独立集，这些集是补图的团； igraph_clique_number() 用于查找最大团的大小； igraph_cliques() 用于查找所有团。

时间复杂度：最坏情况下为 O(d(n-d)3^(d/3))，d 是图的简并度，对于稀疏图，这通常很小。

示例 16.2.  文件 examples/simple/igraph_maximal_cliques.c

#include <igraph.h>

int main(void) {

    igraph_t g;
    igraph_vector_int_list_t cliques;
    igraph_integer_t no;

    igraph_small(&g, 9, IGRAPH_UNDIRECTED,
                 0,1, 0,2, 1,2, 2,3, 3,4, 3, 5, 4,5, 5,6, 6,7, -1);
    igraph_vector_int_list_init(&cliques, 0);
    igraph_maximal_cliques(&g, &cliques, /*min_size=*/ 0,
                           /*max_size=*/ 0 /*no limit*/);
    igraph_maximal_cliques_count(&g, &no, /*min_size=*/ 0,
                                 /*max_size=*/ 0 /*no limit*/);

    if (no != igraph_vector_int_list_size(&cliques)) {
        return 1;
    }

    for (igraph_integer_t i = 0; i < igraph_vector_int_list_size(&cliques); i++) {
        igraph_vector_int_t *v = igraph_vector_int_list_get_ptr(&cliques, i);
        igraph_vector_int_print(v);
    }

    igraph_vector_int_list_destroy(&cliques);
    igraph_destroy(&g);

    return 0;
}


1.9. igraph_maximal_cliques_count — 计算图中极大团的数量。

igraph_error_t igraph_maximal_cliques_count(const igraph_t *graph,
                                 igraph_integer_t *res,
                                 igraph_integer_t min_size,
                                 igraph_integer_t max_size);

有关详细信息，请参阅 igraph_maximal_cliques()。

参数： 

图:

输入图。边的方向被忽略。

res:

指向 igraph_integer_t 的指针；极大团的数量将存储在此处。

min_size:

整数，给出要返回的团的最小大小。如果为负数或零，则不使用下限。

max_size:

整数，给出要返回的团的最大大小。如果为负数或零，则不使用上限。

返回值： 

错误代码。

另请参阅： 

igraph_maximal_cliques().

时间复杂度：最坏情况下为 O(d(n-d)3^(d/3))，d 是图的简并度，对于稀疏图，这通常很小。

示例 16.3.  文件 examples/simple/igraph_maximal_cliques.c

#include <igraph.h>

int main(void) {

    igraph_t g;
    igraph_vector_int_list_t cliques;
    igraph_integer_t no;

    igraph_small(&g, 9, IGRAPH_UNDIRECTED,
                 0,1, 0,2, 1,2, 2,3, 3,4, 3, 5, 4,5, 5,6, 6,7, -1);
    igraph_vector_int_list_init(&cliques, 0);
    igraph_maximal_cliques(&g, &cliques, /*min_size=*/ 0,
                           /*max_size=*/ 0 /*no limit*/);
    igraph_maximal_cliques_count(&g, &no, /*min_size=*/ 0,
                                 /*max_size=*/ 0 /*no limit*/);

    if (no != igraph_vector_int_list_size(&cliques)) {
        return 1;
    }

    for (igraph_integer_t i = 0; i < igraph_vector_int_list_size(&cliques); i++) {
        igraph_vector_int_t *v = igraph_vector_int_list_get_ptr(&cliques, i);
        igraph_vector_int_print(v);
    }

    igraph_vector_int_list_destroy(&cliques);
    igraph_destroy(&g);

    return 0;
}


1.10. igraph_maximal_cliques_file — 查找极大团并将它们写入文件。

igraph_error_t igraph_maximal_cliques_file(const igraph_t *graph,
                                FILE *outfile,
                                igraph_integer_t min_size,
                                igraph_integer_t max_size);

此函数枚举大小范围内的所有极大团，并将它们写入文件。有关详细信息，请参阅 igraph_maximal_cliques()

参数： 

图:

输入图。边的方向被忽略。

outfile:

指向输出文件的指针，它应该是可写的。

min_size:

整数，给出要返回的团的最小大小。如果为负数或零，则不使用下限。

max_size:

整数，给出要返回的团的最大大小。如果为负数或零，则不使用上限。

返回值： 

错误代码。

另请参阅： 

igraph_maximal_cliques().

时间复杂度：最坏情况下为 O(d(n-d)3^(d/3))，d 是图的简并度，对于稀疏图，这通常很小。

1.11. igraph_maximal_cliques_subset — 初始顶点子集的极大团。

igraph_error_t igraph_maximal_cliques_subset(
    const igraph_t *graph, const igraph_vector_int_t *subset,
    igraph_vector_int_list_t *res, igraph_integer_t *no,
    FILE *outfile, igraph_integer_t min_size, igraph_integer_t max_size
);

此函数枚举初始顶点子集的所有极大团，并将它们写入文件。有关详细信息，请参阅 igraph_maximal_cliques()。

参数： 

图:

输入图。边的方向被忽略。

subset:

指向包含初始顶点子集的 igraph_vector_int_t 的指针。

res:

指向整数向量列表的指针；团将存储在此处。

no:

指向 igraph_integer_t 的指针；极大团的数量将存储在此处。

outfile:

指向输出文件或 NULL 的指针。当不是 NULL 时，该文件应该是可写的。

min_size:

整数，给出要返回的团的最小大小。如果为负数或零，则不使用下限。

max_size:

整数，给出要返回的团的最大大小。如果为负数或零，则不使用上限。

返回值： 

错误代码。

另请参阅： 

igraph_maximal_cliques().

时间复杂度：最坏情况下为 O(d(n-d)3^(d/3))，d 是图的简并度，对于稀疏图，这通常很小。

1.12. igraph_maximal_cliques_hist — 统计图中每个大小的极大团的数量。

igraph_error_t igraph_maximal_cliques_hist(const igraph_t *graph,
                                igraph_vector_t *hist,
                                igraph_integer_t min_size,
                                igraph_integer_t max_size);

此函数统计图中存在的每个大小的极大团的数量。大小为 1 的极大团只是孤立顶点。

参数： 

图:

输入图。边的方向被忽略。

hist:

指向已初始化的向量的指针。结果将存储在此处。第一个元素将存储大小为 1 的极大团的数量，第二个元素将存储大小为 2 的极大团的数量，依此类推。对于小于 min_size 的团，将返回零计数。

min_size:

整数，给出要返回的团的最小大小。如果为负数或零，则不使用下限。

max_size:

整数，给出要返回的团的最大大小。如果为负数或零，则不使用上限。

返回值： 

错误代码。

另请参阅： 

igraph_maximal_cliques()、 igraph_clique_size_hist()。

时间复杂度：最坏情况下为 O(d(n-d)3^(d/3))，d 是图的简并度，对于稀疏图，这通常很小。

1.13. igraph_maximal_cliques_callback — 在图中查找极大团并为每个团调用一个函数。

igraph_error_t igraph_maximal_cliques_callback(const igraph_t *graph,
                                    igraph_clique_handler_t *cliquehandler_fn, void *arg,
                                    igraph_integer_t min_size, igraph_integer_t max_size);

此函数枚举给定大小范围内的所有极大团，并为每个团调用 cliquehandler_fn。团作为指向 igraph_vector_int_t 的指针传递给回调函数。向量归极大团搜索例程所有，因此用户应使用 igraph_vector_int_init_copy() 复制向量，如果他们想保留它。

参数： 

图:

输入图。边的方向被忽略。

cliquehandler_fn:

为每个团调用的回调函数。另请参阅 igraph_clique_handler_t。

arg:

提供给 cliquehandler_fn 的额外参数。

min_size:

整数，给出要返回的团的最小大小。如果为负数或零，则不使用下限。

max_size:

整数，给出要返回的团的最大大小。如果为负数或零，则不使用上限。

返回值： 

错误代码。

另请参阅： 

igraph_maximal_cliques()、 igraph_cliques_callback()。

时间复杂度：最坏情况下为 O(d(n-d)3^(d/3))，d 是图的简并度，对于稀疏图，这通常很小。

1.14. igraph_clique_number — 查找图的团数。

igraph_error_t igraph_clique_number(const igraph_t *graph, igraph_integer_t *no);

图的团数是最大团的大小。

此函数的当前实现使用 igraph_maximal_cliques_callback() 搜索极大团，并跟踪找到的最大团的大小。

参数： 

图:

输入图。

no:

团数将返回到此变量指向的 igraph_integer_t。

返回值： 

错误代码。

另请参阅： 

igraph_cliques()、 igraph_largest_cliques()。

时间复杂度：最坏情况下为 O(3^(|V|/3))。

2. 加权团

2.1. igraph_weighted_cliques — 在顶点加权图中查找给定权重范围内的所有团。
2.2. igraph_largest_weighted_cliques — 在图中查找最大权重团。
2.3. igraph_weighted_clique_number — 查找图中最大权重团的权重。

2.1. igraph_weighted_cliques — 在顶点加权图中查找给定权重范围内的所有团。

igraph_error_t igraph_weighted_cliques(const igraph_t *graph,
                            const igraph_vector_t *vertex_weights, igraph_vector_int_list_t *res,
                            igraph_real_t min_weight, igraph_real_t max_weight, igraph_bool_t maximal);

团是图的完全连接子图。团的权重是团中各个顶点的权重之和。

仅支持正整数顶点权重。

此函数的当前实现使用 Sampo Niskanen 和 Patric R. J. Östergård 的 Cliquer 库的 1.21 版本，http://users.aalto.fi/~pat/cliquer.html

参数： 

图:

输入图。

vertex_weights:

顶点权重的向量。当前实现会将所有权重截断为其整数部分。您可以在此处传递 NULL 以使每个顶点的权重为 1。

res:

指向已初始化的整数向量列表的指针。团将作为顶点 ID 的向量存储在此处。

min_weight:

整数，指定要返回的团的最小权重。如果为负数或零，则不使用下限。

max_weight:

整数，指定要返回的团的最大权重。如果为负数或零，则不使用上限。

maximal:

如果为 true，则仅返回极大团

返回值： 

错误代码。

另请参阅： 

igraph_cliques()、 igraph_maximal_cliques()

时间复杂度：指数级

2.2. igraph_largest_weighted_cliques — 在图中查找最大权重团。

igraph_error_t igraph_largest_weighted_cliques(const igraph_t *graph,
                                    const igraph_vector_t *vertex_weights, igraph_vector_int_list_t *res);

团的权重是其顶点权重之和。此函数查找图中具有最大权重的团。

仅支持正整数顶点权重。

此函数的当前实现使用 Sampo Niskanen 和 Patric R. J. Östergård 的 Cliquer 库的 1.21 版本，http://users.aalto.fi/~pat/cliquer.html

参数： 

图:

输入图。

vertex_weights:

顶点权重的向量。当前实现会将所有权重截断为其整数部分。您可以在此处传递 NULL 以使每个顶点的权重为 1。

res:

指向已初始化的整数向量列表的指针。团将作为顶点 ID 的向量存储在此处。

返回值： 

错误代码。

另请参阅： 

igraph_weighted_cliques()、 igraph_weighted_clique_number()、 igraph_largest_cliques()

时间复杂度：TODO

2.3. igraph_weighted_clique_number — 查找图中最大权重团的权重。

igraph_error_t igraph_weighted_clique_number(const igraph_t *graph,
                                  const igraph_vector_t *vertex_weights, igraph_real_t *res);

团的权重是其顶点权重之和。此函数查找最大权重团的权重。

仅支持正整数顶点权重。

此函数的当前实现使用 Sampo Niskanen 和 Patric R. J. Östergård 的 Cliquer 库的 1.21 版本，http://users.aalto.fi/~pat/cliquer.html

参数： 

图:

输入图。

vertex_weights:

顶点权重的向量。当前实现会将所有权重截断为其整数部分。您可以在此处传递 NULL 以使每个顶点的权重为 1。

res:

最大权重将返回到此变量指向的 igraph_real_t。

返回值： 

错误代码。

另请参阅： 

igraph_weighted_cliques()、 igraph_largest_weighted_cliques()、 igraph_clique_number()

时间复杂度：TODO

3. 独立顶点集

3.1. igraph_is_independent_vertex_set — 顶点集是否构成独立集？
3.2. igraph_independent_vertex_sets — 查找图中的所有独立顶点集。
3.3. igraph_largest_independent_vertex_sets — 查找图中的最大独立顶点集。
3.4. igraph_maximal_independent_vertex_sets — 查找图的所有极大独立顶点集。
3.5. igraph_independence_number — 查找图的独立数。

3.1. igraph_is_independent_vertex_set — 顶点集是否构成独立集？

igraph_error_t igraph_is_independent_vertex_set(const igraph_t *graph, igraph_vs_t candidate,
                                         igraph_bool_t *res);

警告

此函数是实验性的，其签名尚未被视为最终签名。我们保留更改函数签名的权利，而无需更改 igraph 的主要版本。使用它需要您自担风险。

测试顶点集中是否没有顶点对相邻，即它们是否构成独立集。空集和单例集都被认为是独立集。

参数： 

图:

输入图。

candidate:

要测试是否为独立集的顶点集。

res:

结果将存储在此处。

返回值： 

错误代码。

另请参阅： 

igraph_is_clique() 用于测试团； igraph_independent_vertex_sets()、 igraph_maximal_independent_vertex_sets() 和 igraph_largest_independent_vertex_sets() 用于查找独立顶点集。

时间复杂度：O(n^2 log(d))，其中 n 是候选集中的顶点数，d 是典型的顶点度。

3.2. igraph_independent_vertex_sets — 查找图中的所有独立顶点集。

igraph_error_t igraph_independent_vertex_sets(const igraph_t *graph,
                                   igraph_vector_int_list_t *res,
                                   igraph_integer_t min_size,
                                   igraph_integer_t max_size);

如果顶点集之间没有边，则认为该顶点集是独立的。

如果您对最大独立顶点集的大小感兴趣，请使用 igraph_independence_number()。

当前实现已从 Keith Briggs 的 Very Nauty Graph Library 移植到 igraph，并使用 S. Tsukiyama、M. Ide、H. Ariyoshi 和 I. Shirawaka 的论文中的算法。生成所有最大独立集的新算法。SIAM J Computing, 6:505--517, 1977.

参数： 

图:

输入图。

res:

指向已初始化的整数向量列表的指针。团将作为顶点 ID 的向量存储在此处。

min_size:

整数，指定要返回的集合的最小大小。如果为负数或零，则不使用下限。

max_size:

整数，指定要返回的集合的最大大小。如果为负数或零，则不使用上限。

返回值： 

错误代码。

另请参阅： 

igraph_largest_independent_vertex_sets()、 igraph_independence_number()。

时间复杂度：TODO

示例 16.4.  文件 examples/simple/igraph_independent_sets.c

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

int main(void) {

    igraph_t g;
    igraph_vector_int_list_t result;
    igraph_integer_t i, j, n;
    igraph_integer_t alpha;
    const int params[] = {4, -1, 2, 2, 0, 0, -1, -1};

    igraph_set_warning_handler(igraph_warning_handler_ignore);
    igraph_vector_int_list_init(&result, 0);

    igraph_kary_tree(&g, 5, 2, IGRAPH_TREE_OUT);
    for (j = 0; j < sizeof(params) / (2 * sizeof(params[0])); j++) {
        if (params[2 * j + 1] != 0) {
            igraph_independent_vertex_sets(&g, &result, params[2 * j], params[2 * j + 1]);
        } else {
            igraph_largest_independent_vertex_sets(&g, &result);
        }
        n = igraph_vector_int_list_size(&result);
        printf("%" IGRAPH_PRId " independent sets found\n", n);
        for (i = 0; i < n; i++) {
            igraph_vector_int_print(igraph_vector_int_list_get_ptr(&result, i));
        }
    }
    igraph_destroy(&g);

    igraph_kary_tree(&g, 10, 2, IGRAPH_TREE_OUT);
    igraph_maximal_independent_vertex_sets(&g, &result);
    n = igraph_vector_int_list_size(&result);
    printf("%" IGRAPH_PRId " maximal independent sets found\n", n);
    for (i = 0; i < n; i++) {
        igraph_vector_int_print(igraph_vector_int_list_get_ptr(&result, i));
    }

    igraph_independence_number(&g, &alpha);
    printf("alpha=%" IGRAPH_PRId "\n", alpha);

    igraph_destroy(&g);

    igraph_vector_int_list_destroy(&result);

    return 0;
}


3.3. igraph_largest_independent_vertex_sets — 查找图中的最大独立顶点集。

igraph_error_t igraph_largest_independent_vertex_sets(const igraph_t *graph,
        igraph_vector_int_list_t *res);

如果图中没有其他具有更多顶点的独立顶点集，则独立顶点集是最大的。

当前实现已从 Keith Briggs 的 Very Nauty Graph Library 移植到 igraph，并使用 S. Tsukiyama、M. Ide、H. Ariyoshi 和 I. Shirawaka 的论文中的算法。生成所有最大独立集的新算法。SIAM J Computing, 6:505--517, 1977.

参数： 

图:

输入图。

res:

指向已初始化的整数向量列表的指针。团将作为顶点 ID 的向量存储在此处。

返回值： 

错误代码。

另请参阅： 

igraph_independent_vertex_sets()、 igraph_maximal_independent_vertex_sets()。

时间复杂度：TODO

3.4. igraph_maximal_independent_vertex_sets — 查找图的所有极大独立顶点集。

igraph_error_t igraph_maximal_independent_vertex_sets(const igraph_t *graph,
        igraph_vector_int_list_t *res);

极大独立顶点集是无法通过向其中添加新顶点来进一步扩展的独立顶点集。

此处使用的算法基于以下论文：S. Tsukiyama、M. Ide、H. Ariyoshi 和 I. Shirawaka。生成所有最大独立集的新算法。SIAM J Computing, 6:505--517, 1977.

该实现最初由 Kevin O'Neill 编写，并由 K M Briggs 在 Very Nauty Graph Library 中修改。我只是重新编写了它以使用 igraph 的数据结构。

如果您对最大独立顶点集的大小感兴趣，请使用 igraph_independence_number()。

参数： 

图:

输入图。

res:

指向已初始化的整数向量列表的指针。团将作为顶点 ID 的向量存储在此处。

返回值： 

错误代码。

另请参阅： 

igraph_maximal_cliques()、 igraph_independence_number()

时间复杂度：待定。

3.5. igraph_independence_number — 查找图的独立数。

igraph_error_t igraph_independence_number(const igraph_t *graph, igraph_integer_t *no);

图的独立数是最大独立顶点集的基数。

当前实现已从 Keith Briggs 的 Very Nauty Graph Library 移植到 igraph，并使用 S. Tsukiyama、M. Ide、H. Ariyoshi 和 I. Shirawaka 的论文中的算法。生成所有最大独立集的新算法。SIAM J Computing, 6:505--517, 1977.

参数： 

图:

输入图。

no:

独立数将返回到此变量指向的 igraph_integer_t。

返回值： 

错误代码。

另请参阅： 

igraph_independent_vertex_sets().

时间复杂度：待定。

← 第 15 章. 图访问器 第 17 章. 图同构 →