用于使用 igraph C 库
igraph_error_t igraph_is_separator(const igraph_t *graph,
const igraph_vs_t candidate,
igraph_bool_t *res);
顶点集 S 是一个分隔符，如果在图中存在顶点 u 和 v，使得 u 和 v 之间的所有路径都经过 S 中的某些顶点。
参数：
|
输入图。 它可以是有向图，但边缘方向将被忽略。 |
|
候选分隔符。 |
|
指向布尔变量的指针，结果存储在这里。 |
返回值：
错误代码。 |
时间复杂度：O(|V|+|E|)，与顶点和边的数量呈线性关系。
示例 23.1. 文件 examples/simple/igraph_is_separator.c
#include <igraph.h> #include <stdio.h> #define FAIL(msg, error) do { printf(msg "\n") ; return error; } while (0) int main(void) { igraph_t graph; igraph_vector_int_t sep; igraph_bool_t result; /* Simple star graph, remove the center */ igraph_star(&graph, 10, IGRAPH_STAR_UNDIRECTED, 0); igraph_is_separator(&graph, igraph_vss_1(0), &result); if (!result) { FAIL("Center of star graph failed.", 1); } /* Same graph, but another vertex */ igraph_is_separator(&graph, igraph_vss_1(6), &result); if (result) { FAIL("Non-center of star graph failed.", 2); } /* Same graph, all vertices but the center */ igraph_is_separator(&graph, igraph_vss_range(1, 10), &result); if (result) { FAIL("All non-central vertices of star graph failed.", 5); } /* Same graph, all vertices */ igraph_is_separator(&graph, igraph_vss_range(0, 10), &result); if (result) { FAIL("All vertices of star graph failed.", 6); } igraph_destroy(&graph); /* Karate club */ igraph_famous(&graph, "zachary"); igraph_vector_int_init(&sep, 0); igraph_vector_int_push_back(&sep, 32); igraph_vector_int_push_back(&sep, 33); igraph_is_separator(&graph, igraph_vss_vector(&sep), &result); if (!result) { FAIL("Karate network (32,33) failed", 3); } igraph_vector_int_resize(&sep, 5); VECTOR(sep)[0] = 8; VECTOR(sep)[1] = 9; VECTOR(sep)[2] = 19; VECTOR(sep)[3] = 30; VECTOR(sep)[4] = 31; igraph_is_separator(&graph, igraph_vss_vector(&sep), &result); if (result) { FAIL("Karate network (8,9,19,30,31) failed", 4); } igraph_destroy(&graph); igraph_vector_int_destroy(&sep); return 0; }
igraph_error_t igraph_is_minimal_separator(const igraph_t *graph,
const igraph_vs_t candidate,
igraph_bool_t *res);
顶点分隔符 S 是最小的，当且仅当 S 的任何真子集都不是分隔符。
参数：
|
输入图。 它可以是有向图，但边缘方向将被忽略。 |
|
候选的最小分隔符。 |
|
指向布尔变量的指针，结果存储在这里。 |
返回值：
错误代码。 |
时间复杂度：O(|V|+|E|)，与顶点和边的数量呈线性关系。
示例 23.2. 文件 examples/simple/igraph_is_minimal_separator.c
#include <igraph.h> #include <stdio.h> #define FAIL(msg, error) do { printf(msg "\n") ; return error; } while (0) int main(void) { igraph_t graph; igraph_vector_int_t sep; igraph_bool_t result; /* Simple star graph, remove the center */ igraph_star(&graph, 10, IGRAPH_STAR_UNDIRECTED, 0); igraph_is_minimal_separator(&graph, igraph_vss_1(0), &result); if (!result) { FAIL("Center of star graph failed.", 1); } /* Same graph, but another vertex */ igraph_is_minimal_separator(&graph, igraph_vss_1(6), &result); if (result) { FAIL("Non-center of star graph failed.", 2); } igraph_destroy(&graph); /* Karate club */ igraph_famous(&graph, "zachary"); igraph_vector_int_init(&sep, 0); igraph_vector_int_push_back(&sep, 32); igraph_vector_int_push_back(&sep, 33); igraph_is_minimal_separator(&graph, igraph_vss_vector(&sep), &result); if (!result) { FAIL("Karate network (32,33) failed", 3); } igraph_vector_int_resize(&sep, 5); VECTOR(sep)[0] = 8; VECTOR(sep)[1] = 9; VECTOR(sep)[2] = 19; VECTOR(sep)[3] = 30; VECTOR(sep)[4] = 31; igraph_is_minimal_separator(&graph, igraph_vss_vector(&sep), &result); if (result) { FAIL("Karate network (8,9,19,30,31) failed", 4); } igraph_destroy(&graph); igraph_vector_int_destroy(&sep); return 0; }
igraph_error_t igraph_all_minimal_st_separators(
const igraph_t *graph, igraph_vector_int_list_t *separators
);
此函数列出所有对于某些 (s,t) 顶点对来说是最小 (s,t) 分隔符的顶点集。
请注意，此函数返回的某些顶点集可能不是断开图（或增加连通分量的数量）的最小顶点集。例如，考虑具有边 0-1-2-3-4-1 的 5 顶点图。此函数返回顶点集 {1}、{2,4} 和 {1,3}。请注意，{1,3} 对于断开图来说不是最小的，因为 {1} 就足够了。但是，它对于分隔顶点 2 和 4 来说是最小的。
有关已实现算法的更多信息，请参见 Anne Berry, Jean-Paul Bordat and Olivier Cogis: Generating All the Minimal Separators of a Graph, In: Peter Widmayer, Gabriele Neyer and Stephan Eidenbenz (editors): Graph-theoretic concepts in computer science, 1665, 167--172, 1999. Springer. https://doi.org/10.1007/3-540-46784-X_17
参数：
|
输入图。 它可以是有向图，但边缘方向将被忽略。 |
|
指向整数向量列表的指针，分隔符将存储在此处。 |
返回值：
错误代码。 |
另请参阅：
时间复杂度：O(n|V|^3), |V| 是顶点的数量，n 是分隔符的数量。
示例 23.3. 文件 examples/simple/igraph_minimal_separators.c
#include <igraph.h> #include <stdio.h> int main(void) { igraph_t graph; igraph_vector_int_list_t separators; igraph_integer_t i, n; igraph_famous(&graph, "zachary"); igraph_vector_int_list_init(&separators, 0); igraph_all_minimal_st_separators(&graph, &separators); n = igraph_vector_int_list_size(&separators); for (i = 0; i < n; i++) { igraph_bool_t res; igraph_vector_int_t *sep = igraph_vector_int_list_get_ptr(&separators, i); igraph_is_separator(&graph, igraph_vss_vector(sep), &res); if (!res) { printf("Vertex set %" IGRAPH_PRId " is not a separator!\n", i); igraph_vector_int_print(sep); return 1; } } igraph_destroy(&graph); igraph_vector_int_list_destroy(&separators); return 0; }
igraph_error_t igraph_minimum_size_separators(
const igraph_t *graph, igraph_vector_int_list_t *separators
);
此函数列出所有最小大小的分隔顶点集。如果移除顶点集会断开图，则该顶点集是分隔符。
该实现基于以下论文：Arkady Kanevsky: Finding all minimum-size separating vertex sets in a graph, Networks 23, 533--541, 1993. https://doi.org/10.1002/net.3230230604
参数：
|
输入图，必须是无向图。 |
|
已初始化的整数向量列表，分隔符存储在此处。它是指向 igraph_vector_int_t 对象的指针列表。每个向量将包含分隔符中顶点的 ID。分隔符以任意顺序返回。 |
返回值：
错误代码。 |
时间复杂度：待定。
示例 23.4. 文件 examples/simple/igraph_minimum_size_separators.c
#include <igraph.h> int main(void) { igraph_t g; igraph_vector_int_list_t sep; igraph_small(&g, 7, IGRAPH_UNDIRECTED, 1, 0, 2, 0, 3, 0, 4, 0, 5, 0, 6, 0, -1); igraph_vector_int_list_init(&sep, 0); igraph_minimum_size_separators(&g, &sep); for (igraph_integer_t i = 0; i < igraph_vector_int_list_size(&sep); i++) { igraph_vector_int_t* v = igraph_vector_int_list_get_ptr(&sep, i); igraph_vector_int_print(v); } igraph_vector_int_list_destroy(&sep); igraph_destroy(&g); return 0; }
igraph_error_t igraph_even_tarjan_reduction(const igraph_t *graph, igraph_t *graphbar,
igraph_vector_t *capacity);
创建一个有向图，其顶点和边的数量是原来的两倍。对于每个原始顶点 i，创建两个顶点 i' = i 和 i'' = i' + n，并从 i' 到 i'' 存在一条有向边。对于从 i 到 j 的每个原始有向边，创建两个新边，从 i' 到 j'' 和从 i'' 到 j'。
此归约用于论文（观察 2）：Arkady Kanevsky: Finding all minimum-size separating vertex sets in a graph, Networks 23, 533--541, 1993.
构思此归约的原始论文是 Shimon Even 和 R. Endre Tarjan: Network Flow and Testing Graph Connectivity, SIAM J. Comput., 4(4), 507–518. https://doi.org/10.1137/0204043
参数：
|
一个图。虽然不检查方向性，但此函数通常仅用于有向图。 |
|
指向新有向图的指针，该图将包含归约，其顶点和边的数量是原来的两倍。 |
|
指向已初始化的向量或空指针的指针。如果不是空指针，则将填充归约的容量：前 |E| 个元素为 1，其余 |E| 个元素等于 |V|（用于表示无穷大）。 |
返回值：
错误代码。 |
时间复杂度：O(|E|+|V|)。
示例 23.5. 文件 examples/simple/even_tarjan.c
#include <igraph.h> #include <limits.h> int main(void) { igraph_t g, gbar; igraph_integer_t k1, k2 = INT_MAX; igraph_real_t tmpk; igraph_integer_t i, j, n; igraph_maxflow_stats_t stats; /* --------------------------------------------------- */ igraph_famous(&g, "meredith"); igraph_even_tarjan_reduction(&g, &gbar, /*capacity=*/ NULL); igraph_vertex_connectivity(&g, &k1, /* checks= */ false); n = igraph_vcount(&g); for (i = 0; i < n; i++) { for (j = i + 1; j < n; j++) { igraph_bool_t conn; igraph_are_adjacent(&g, i, j, &conn); if (conn) { continue; } igraph_maxflow_value(&gbar, &tmpk, /* source= */ i + n, /* target= */ j, /* capacity= */ 0, &stats); if (tmpk < k2) { k2 = tmpk; } } } igraph_destroy(&gbar); igraph_destroy(&g); if (k1 != k2) { printf("k1 = %" IGRAPH_PRId " while k2 = %" IGRAPH_PRId "\n", k1, k2); return 1; } return 0; }
| ← 第 22. 章 最大流、最小割和相关度量 | 第 24. 章 检测社区结构 → |