用于使用 igraph C 库
igraph_error_t igraph_maxflow(const igraph_t *graph, igraph_real_t *value,
igraph_vector_t *flow, igraph_vector_int_t *cut,
igraph_vector_int_t *partition, igraph_vector_int_t *partition2,
igraph_integer_t source, igraph_integer_t target,
const igraph_vector_t *capacity,
igraph_maxflow_stats_t *stats);
此函数实现 Goldberg-Tarjan 算法来计算有向图或无向图中最大流的值。该算法在 Andrew V. Goldberg, Robert E. Tarjan: A New Approach to the Maximum-Flow Problem, Journal of the ACM, 35(4), 921-940, 1988 https://doi.org/10.1145/48014.61051 中给出。
该函数的输入是一个图，一个实数向量表示边的容量，以及图中的两个顶点，源和目标。流是一个将正实数分配给边的函数，并满足两个要求：（1）流值小于边的容量，并且（2）在除源和目标之外的每个顶点，流入流（即，流入边上的流的总和）与流出流（即，流出边上的流的总和）相同。流的值是目标顶点的流入流。最大流是具有最大值的流。
参数：
|
输入图，可以是有向图或无向图。 |
|
指向实数的指针，最大流的值将放置在此处，除非它是空指针。 |
|
如果不是空指针，则它必须是指向已初始化向量的指针。向量将被调整大小，并且每条边上的流将按照边 ID 的顺序放置在其中。对于无向图，此参数有点棘手，因为对于这些图，流方向不是由边方向预先确定的。对于这些图， |
|
空指针或指向已初始化向量的指针。如果不是空指针，则与最大流对应的最小割将存储在此处，即，属于最小割的所有边 ID 都存储在向量中。 |
|
空指针或指向已初始化向量的指针。如果不是空指针，则与最大流对应的最小割的第一个分区将放置在此处。第一个分区始终是包含源顶点的分区。 |
|
空指针或指向已初始化向量的指针。如果不是空指针，则与最大流对应的最小割的第二个分区将放置在此处。第二个分区始终是包含目标顶点的分区。 |
|
源顶点的 ID。 |
|
目标顶点的 ID。 |
|
包含边容量的向量。如果为 NULL，则认为每条边的容量为 1.0。 |
|
算法执行的不同操作的次数存储在此处。 |
返回值：
错误代码。 |
时间复杂度：O(|V|^3)。在实践中它快得多，但我无法证明我使用的数据结构有更好的下限。事实上，这个实现比 B. V. Cherkassky 和 A. V. Goldberg: On implementing the push-relabel method for the maximum flow problem, (Algorithmica, 19:390--410, 1997) 中讨论的 hi_pr 实现在我尝试过的所有图类上运行得更快。
另请参阅：
示例 22.1. 文件 examples/simple/flow.c
#include <igraph.h> int main(void) { igraph_t g; igraph_real_t flow; igraph_vector_t capacity; igraph_integer_t source, target; FILE *infile; igraph_maxflow_stats_t stats; igraph_vector_init(&capacity, 0); /***************/ infile = fopen("ak-4102.max", "r"); igraph_read_graph_dimacs_flow( &g, infile, 0, 0, &source, &target, &capacity, IGRAPH_DIRECTED); fclose(infile); igraph_maxflow_value(&g, &flow, source, target, &capacity, &stats); if (flow != 8207) { return 1; } igraph_destroy(&g); /***************/ /* /\***************\/ */ /* infile=fopen("ak-8198.max", "r"); */ /* igraph_read_graph_dimacs_flow(&g, infile, 0, 0, &source, &target, &capacity, */ /* IGRAPH_DIRECTED); */ /* fclose(infile); */ /* t=timer(); */ /* igraph_maxflow_value(&g, &flow, source, target, &capacity, &stats); */ /* t=timer()-t; */ /* printf("8198: %g (time %.10f)\n", flow, t); */ /* igraph_destroy(&g); */ /* /\***************\/ */ /* /\***************\/ */ /* infile=fopen("ak-16390.max", "r"); */ /* igraph_read_graph_dimacs_flow(&g, infile, 0, 0, &source, &target, &capacity, */ /* IGRAPH_DIRECTED); */ /* fclose(infile); */ /* t=timer(); */ /* igraph_maxflow_value(&g, &flow, source, target, &capacity, &stats); */ /* t=timer()-t; */ /* printf("16390: %g (time %.10f)\n", flow, t); */ /* igraph_destroy(&g); */ /* /\***************\/ */ /* /\***************\/ */ /* infile=fopen("ak-32774.max", "r"); */ /* igraph_read_graph_dimacs_flow(&g, infile, 0, 0, &source, &target, &capacity, */ /* IGRAPH_DIRECTED); */ /* fclose(infile); */ /* t=timer(); */ /* igraph_maxflow_value(&g, &flow, source, target, &capacity, &stats); */ /* t=timer()-t; */ /* printf("32774: %g (time %.10f)\n", flow, t); */ /* igraph_destroy(&g); */ /* /\***************\/ */ /* /\***************\/ */ /* infile=fopen("ak-65542.max", "r"); */ /* igraph_read_graph_dimacs_flow(&g, infile, 0, 0, &source, &target, &capacity, */ /* IGRAPH_DIRECTED); */ /* fclose(infile); */ /* t=timer(); */ /* igraph_maxflow_value(&g, &flow, source, target, &capacity, &stats); */ /* t=timer()-t; */ /* printf("65542: %g (time %.10f)\n", flow, t); */ /* igraph_destroy(&g); */ /* /\***************\/ */ igraph_vector_destroy(&capacity); return 0; }
示例 22.2. 文件 examples/simple/flow2.c
#include <igraph.h> int main(void) { igraph_t g; igraph_real_t flow_value; igraph_vector_int_t cut; igraph_vector_t capacity; igraph_vector_int_t partition, partition2; igraph_vector_t flow; igraph_integer_t i; igraph_maxflow_stats_t stats; igraph_small(&g, 6, IGRAPH_DIRECTED, 0, 1, 1, 2, 2, 3, 0, 5, 5, 4, 4, 3, 3, 0, -1); igraph_vector_init_int_end(&capacity, -1, 3, 1, 2, 10, 1, 3, 2, -1); igraph_vector_int_init(&cut, 0); igraph_vector_int_init(&partition, 0); igraph_vector_int_init(&partition2, 0); igraph_vector_init(&flow, 0); igraph_maxflow(&g, &flow_value, &flow, &cut, &partition, &partition2, /*source=*/ 0, /*target=*/ 2, &capacity, &stats); igraph_integer_t nc = igraph_vector_int_size(&cut); printf("flow value: %g\n", (double) flow_value); printf("flow: "); igraph_vector_print(&flow); printf("first partition: "); igraph_vector_int_print(&partition); printf("second partition: "); igraph_vector_int_print(&partition2); printf("edges in the cut: "); for (i = 0; i < nc; i++) { igraph_integer_t edge = VECTOR(cut)[i]; igraph_integer_t from = IGRAPH_FROM(&g, edge); igraph_integer_t to = IGRAPH_TO(&g, edge); printf("%" IGRAPH_PRId "-%" IGRAPH_PRId " (%g), ", from, to, VECTOR(capacity)[edge]); } printf("\n"); igraph_vector_int_destroy(&cut); igraph_vector_int_destroy(&partition2); igraph_vector_int_destroy(&partition); igraph_vector_destroy(&capacity); igraph_vector_destroy(&flow); igraph_destroy(&g); return 0; }
igraph_error_t igraph_maxflow_value(const igraph_t *graph, igraph_real_t *value,
igraph_integer_t source, igraph_integer_t target,
const igraph_vector_t *capacity,
igraph_maxflow_stats_t *stats);
此函数实现 Goldberg-Tarjan 算法来计算有向图或无向图中最大流的值。该算法在 Andrew V. Goldberg, Robert E. Tarjan: A New Approach to the Maximum-Flow Problem, Journal of the ACM, 35(4), 921-940, 1988 https://doi.org/10.1145/48014.61051 中给出。
该函数的输入是一个图，一个实数向量表示边的容量，以及图中的两个顶点，源和目标。流是一个将正实数分配给边的函数，并满足两个要求：（1）流值小于边的容量，并且（2）在除源和目标之外的每个顶点，流入流（即，流入边上的流的总和）与流出流（即，流出边上的流的总和）相同。流的值是目标顶点的流入流。最大流是具有最大值的流。
根据 Ford 和 Fulkerson 的一个定理（L. R. Ford Jr. 和 D. R. Fulkerson. Maximal flow through a network. Canadian J. Math., 8:399-404, 1956.），两个顶点之间的最大流与它们之间的最小割相同（也称为最小 s-t 割）。所以 igraph_st_mincut_value() 在所有情况下都给出与 igraph_maxflow_value() 相同的结果。
请注意，最大流的值与图中的最小割相同。
参数：
|
输入图，可以是有向图或无向图。 |
|
指向实数的指针，结果将放置在此处。 |
|
源顶点的 ID。 |
|
目标顶点的 ID。 |
|
包含边容量的向量。如果为 NULL，则认为每条边的容量为 1.0。 |
|
算法执行的不同操作的次数存储在此处。 |
返回值：
错误代码。 |
时间复杂度：O(|V|^3)。
另请参阅：
|
igraph_error_t igraph_dominator_tree(const igraph_t *graph,
igraph_integer_t root,
igraph_vector_int_t *dom,
igraph_t *domtree,
igraph_vector_int_t *leftout,
igraph_neimode_t mode);
流图是一个有向图，具有一个特定的起始（或根）顶点 r，这样对于任何顶点 v，都存在从 r 到 v 的路径。如果从 r 到 w 的每条路径都包含 v，则顶点 v 支配另一个顶点 w（不等于 v）。如果 v 支配 w 并且 w 的每个其他支配者都支配 v，则顶点 v 是 w 的直接支配者，v=idom(w)。边 {(idom(w), w)| w 不是 r} 形成一个有向树，以 r 为根，称为图的支配树。当且仅当 v 是支配树中 w 的祖先时，顶点 v 支配顶点 w。
此函数实现 Lengauer-Tarjan 算法来构造有向图的支配树。有关详细信息，请参阅 Thomas Lengauer, Robert Endre Tarjan: A fast algorithm for finding dominators in a flowgraph, ACM Transactions on Programming Languages and Systems (TOPLAS) I/1, 121--141, 1979. https://doi.org/10.1145/357062.357071
参数：
|
一个有向图。如果它不是流图，并且包含一些无法从根顶点到达的顶点，则这些顶点将被收集在 |
|
根（或源）顶点的 ID，这将是树的根。 |
|
指向已初始化向量或空指针的指针。如果不是空指针，则每个顶点的直接支配者将存储在此处。对于无法从根到达的顶点，此处存储 |
|
指向未初始化 igraph_t 或 |
|
指向已初始化向量对象的指针，或 |
|
恒定值，必须是 |
返回值：
错误代码。 |
时间复杂度：非常接近 O(|E|+|V|)，在边和顶点的数量上是线性的。更准确地说，它是 O(|V|+|E|alpha(|E|,|V|))，其中 alpha(|E|,|V|) 是 Ackermann 函数的函数逆。
示例 22.3. 文件 examples/simple/dominator_tree.c
#include <igraph.h> #include <stdio.h> int main(void) { igraph_t g, domtree; igraph_vector_int_t dom; igraph_vector_int_t leftout; igraph_vector_int_init(&dom, 0); igraph_vector_int_init(&leftout, 0); igraph_small(&g, 10, IGRAPH_DIRECTED, 0, 9, 1, 0, 1, 2, 2, 3, 2, 7, 3, 1, 4, 1, 4, 3, 5, 2, 5, 3, 5, 4, 5, 8, 6, 5, 6, 9, 8, 7, -1); igraph_dominator_tree(&g, /*root=*/ 9, &dom, &domtree, &leftout, /*mode=*/ IGRAPH_IN); igraph_vector_int_print(&dom); igraph_vector_int_print(&leftout); igraph_write_graph_edgelist(&domtree, stdout); igraph_vector_int_destroy(&dom); igraph_vector_int_destroy(&leftout); igraph_destroy(&domtree); igraph_destroy(&g); return 0; }
igraph_error_t igraph_st_mincut(const igraph_t *graph, igraph_real_t *value,
igraph_vector_int_t *cut, igraph_vector_int_t *partition,
igraph_vector_int_t *partition2,
igraph_integer_t source, igraph_integer_t target,
const igraph_vector_t *capacity);
查找在所有断开源顶点和目标顶点的边集中总容量最小的边集。
通过调用 igraph_maxflow() 使用最大流技术执行计算。
参数：
|
输入图。 |
|
指向实变量的指针，割的值存储在此处。 |
|
指向已初始化向量的指针，包含在割中的边 ID 存储在此处。如果此参数是空指针，则忽略它。 |
|
指向已初始化向量的指针，割的第一个分区中顶点的顶点 ID 存储在此处。第一个分区始终是包含源顶点的分区。如果此参数是空指针，则忽略它。 |
|
指向已初始化向量的指针，割的第二个分区中顶点的顶点 ID 存储在此处。第二个分区始终是包含目标顶点的分区。如果此参数是空指针，则忽略它。 |
|
整数，源顶点的 ID。 |
|
整数，目标顶点的 ID。 |
|
包含边容量的向量。如果为空指针，则认为每条边的容量为 1.0。 |
返回值：
错误代码。 |
另请参阅：
时间复杂度：请参阅 igraph_maxflow()。
igraph_error_t igraph_st_mincut_value(const igraph_t *graph, igraph_real_t *value,
igraph_integer_t source, igraph_integer_t target,
const igraph_vector_t *capacity);
加权（=值）图中的最小 s-t 割是从图中删除以消除从给定顶点（source）到另一个顶点（target）的所有路径所需的最小总边权重。在有向图中考虑有向路径，在无向图中考虑无向路径。
已知两个顶点之间的最小 s-t 割与这两个顶点之间的最大流相同。因此，此函数调用 igraph_maxflow_value() 进行计算。
参数：
|
输入图。 |
|
指向实变量的指针，结果将存储在此处。 |
|
源顶点的 ID。 |
|
目标顶点的 ID。 |
|
指向容量向量的指针，它应该包含非负数，并且其长度应与图中边的数量相同。它可以是空指针，然后每条边都有单位容量。 |
返回值：
错误代码。 |
时间复杂度：O(|V|^3)，另请参见 igraph_maxflow_value() 的讨论，|V| 是顶点的数量。
igraph_error_t igraph_all_st_cuts(const igraph_t *graph,
igraph_vector_int_list_t *cuts,
igraph_vector_int_list_t *partition1s,
igraph_integer_t source,
igraph_integer_t target);
此函数列出源顶点和目标顶点之间的所有边割。每个割恰好列出一次。实现的算法在 JS Provan 和 DR Shier: A Paradigm for listing (s,t)-cuts in graphs, Algorithmica 15, 351--372, 1996 中进行了描述。
参数：
|
输入图，必须是有向图。 |
|
整数向量的已初始化列表，割存储在此处。每个向量将包含割中边的 ID。如果此参数是空指针，则忽略它。 |
|
整数向量的已初始化列表，生成实际边割的顶点集列表存储在此处。每个向量都包含一组顶点 ID。如果 X 是这样一个集合，则从 X 到 X 的补集的所有边都在图中形成（s，t）边割。如果此参数是空指针，则忽略它。 |
|
源顶点的 ID。 |
|
目标顶点的 ID。 |
返回值：
错误代码。 |
时间复杂度：O(n(|V|+|E|))，其中 |V| 是顶点的数量，|E| 是边的数量，n 是割的数量。
igraph_error_t igraph_all_st_mincuts(const igraph_t *graph, igraph_real_t *value,
igraph_vector_int_list_t *cuts,
igraph_vector_int_list_t *partition1s,
igraph_integer_t source,
igraph_integer_t target,
const igraph_vector_t *capacity);
此函数列出有向图中两个顶点之间的所有边割，并具有最小的总容量。可能多个割可能具有相同的总容量，尽管在加权图中通常只有一个最小割。建议提供整数值的容量。否则，由于数值舍入误差，可能无法检测到所有最小割。实现的算法在 JS Provan 和 DR Shier: A Paradigm for listing (s,t)-cuts in graphs, Algorithmica 15, 351--372, 1996 中进行了描述。
参数：
|
输入图，必须是有向图。 |
|
指向实数的指针或 |
|
指向整数向量的已初始化列表的指针或 |
|
指向整数向量的已初始化列表的指针或 |
|
源顶点的 ID。 |
|
目标顶点的 ID。 |
|
边容量向量。所有容量必须严格为正。如果这是空指针，则假定所有边的容量均为 1。 |
返回值：
错误代码。 |
时间复杂度：O(n(|V|+|E|))+O(F)，其中 |V| 是顶点的数量，|E| 是边的数量，n 是割的数量；O(F) 是最大流算法的时间复杂度，请参见 igraph_maxflow()。
示例 22.4. 文件 examples/simple/igraph_all_st_mincuts.c
#include <igraph.h> int main(void) { igraph_t g; igraph_vector_int_list_t partitions; igraph_vector_int_list_t cuts; igraph_real_t value; igraph_small(&g, 5, IGRAPH_DIRECTED, 0, 1, 1, 2, 2, 3, 3, 4, -1); igraph_vector_int_list_init(&partitions, 0); igraph_vector_int_list_init(&cuts, 0); igraph_all_st_mincuts(&g, &value, &cuts, &partitions, /*source=*/ 0, /*target=*/ 4, /*capacity=*/ 0); igraph_integer_t i, e, m, n = igraph_vector_int_list_size(&partitions); printf("Found %" IGRAPH_PRId " cuts, value: %g\n", n, value); for (i = 0; i < n; i++) { igraph_vector_int_t *vec = igraph_vector_int_list_get_ptr(&partitions, i); igraph_vector_int_t *vec2 = igraph_vector_int_list_get_ptr(&cuts, i); printf("Partition %" IGRAPH_PRId ": ", i); igraph_vector_int_print(vec); if (vec2) { printf("Cut %" IGRAPH_PRId ":\n", i); m = igraph_vector_int_size(vec2); for (e = 0; e < m; e++) { igraph_integer_t from = IGRAPH_FROM(&g, VECTOR(*vec2)[e]), to = IGRAPH_TO(&g, VECTOR(*vec2)[e]); printf(" %" IGRAPH_PRId " -> %" IGRAPH_PRId "\n", from, to); } } } igraph_vector_int_list_destroy(&partitions); igraph_vector_int_list_destroy(&cuts); printf("\n"); igraph_destroy(&g); return 0; }
igraph_error_t igraph_mincut(const igraph_t *graph,
igraph_real_t *value,
igraph_vector_int_t *partition,
igraph_vector_int_t *partition2,
igraph_vector_int_t *cut,
const igraph_vector_t *capacity);
此函数计算图中的最小割。最小割是需要删除以断开图的最小边集。使用边的权重（capacity）计算最小值，因此计算具有最小总容量的割。
对于有向图，使用基于计算 2|V|-2 个最大流的实现。对于无向图，我们使用 Stoer-Wagner 算法，如 M. Stoer 和 F. Wagner: A simple min-cut algorithm, Journal of the ACM, 44 585-591, 1997 中所述。
Gregory Benison 首次实现了无向图的实际割计算，谢谢 Greg。
参数：
|
输入图。 |
|
指向浮点数的指针，割的值将存储在此处。 |
|
指向已初始化向量的指针，分离图后，第一个分区中顶点的 ID 将存储在此处。向量将根据需要调整大小。如果此参数为 NULL 指针，则忽略它。 |
|
指向已初始化向量的指针，第二个分区中顶点的 ID 将存储在此处。向量将根据需要调整大小。如果此参数为 NULL 指针，则忽略它。 |
|
指向已初始化向量的指针，割中边的 ID 将存储在此处。如果此参数为 NULL 指针，则忽略它。 |
|
一个数字向量，给出边的容量。如果为空指针，则所有边的容量均为 1。 |
返回值：
错误代码。 |
另请参阅：
|
时间复杂度：对于有向图，它是 O(|V|^4)，但请参见 igraph_maxflow() 的备注。对于无向图，它是 O(|V||E|+|V|^2 log|V|)。 |V| 和 |E| 分别是顶点和边的数量。
示例 22.5. 文件 examples/simple/igraph_mincut.c
#include <igraph.h> int print_mincut(const igraph_t *graph, igraph_real_t value, const igraph_vector_int_t *partition, const igraph_vector_int_t *partition2, const igraph_vector_int_t *cut, const igraph_vector_t *capacity) { igraph_integer_t i, nc = igraph_vector_int_size(cut); igraph_bool_t directed = igraph_is_directed(graph); printf("mincut value: %g\n", (double) value); printf("first partition: "); igraph_vector_int_print(partition); printf("second partition: "); igraph_vector_int_print(partition2); printf("edges in the cut: "); for (i = 0; i < nc; i++) { igraph_integer_t edge = VECTOR(*cut)[i]; igraph_integer_t from = IGRAPH_FROM(graph, edge); igraph_integer_t to = IGRAPH_TO (graph, edge); if (!directed && from > to) { igraph_integer_t tmp = from; from = to; to = tmp; } printf("%" IGRAPH_PRId "-%" IGRAPH_PRId " (%g), ", from, to, VECTOR(*capacity)[edge]); } printf("\n"); return 0; } int main(void) { igraph_t g; igraph_vector_int_t partition, partition2, cut; igraph_vector_t weights; igraph_real_t value; igraph_vector_int_init(&partition, 0); igraph_vector_int_init(&partition2, 0); igraph_vector_int_init(&cut, 0); /* -------------------------------------------- */ igraph_small(&g, 0, IGRAPH_UNDIRECTED, 0, 1, 0, 4, 1, 2, 1, 4, 1, 5, 2, 3, 2, 6, 3, 6, 3, 7, 4, 5, 5, 6, 6, 7, -1); igraph_vector_init_int_end(&weights, -1, 2, 3, 3, 2, 2, 4, 2, 2, 2, 3, 1, 3, -1); igraph_mincut(&g, &value, &partition, &partition2, &cut, &weights); print_mincut(&g, value, &partition, &partition2, &cut, &weights); igraph_vector_destroy(&weights); igraph_destroy(&g); /* -------------------------------------------- */ igraph_small(&g, 6, IGRAPH_DIRECTED, 0, 1, 1, 2, 2, 3, 0, 5, 5, 4, 4, 3, 3, 0, -1); igraph_vector_init_int_end(&weights, -1, 3, 1, 2, 10, 1, 3, 2, -1); igraph_mincut(&g, &value, &partition, &partition2, &cut, &weights); print_mincut(&g, value, &partition, &partition2, &cut, &weights); igraph_vector_destroy(&weights); igraph_destroy(&g); /* -------------------------------------------- */ igraph_small(&g, 5, IGRAPH_DIRECTED, 4, 3, 3, 2, 2, 1, 1, 0, -1); igraph_vector_init_int_end(&weights, -1, 1, 1, 1, 1, -1); igraph_mincut(&g, &value, &partition, &partition2, &cut, &weights); print_mincut(&g, value, &partition, &partition2, &cut, &weights); igraph_vector_destroy(&weights); igraph_destroy(&g); /* -------------------------------------------- */ igraph_vector_int_destroy(&cut); igraph_vector_int_destroy(&partition2); igraph_vector_int_destroy(&partition); return 0; }
igraph_error_t igraph_mincut_value(const igraph_t *graph, igraph_real_t *res,
const igraph_vector_t *capacity);
图中的最小边割是需要从图中删除以使图不强连通的边的最小总权重。（如果原始图不是强连通的，则此值为零。）请注意，在无向图中，强连通性与弱连通性相同。
可以使用最大流技术计算最小割，尽管当前实现仅对有向图执行此操作，并且对无向图使用单独的非基于流的实现。请参见 Mechthild Stoer 和 Frank Wagner: A simple min-cut algorithm, Journal of the ACM 44 585--591, 1997。对于有向图，在固定顶点和图中的所有其他顶点之间计算最大流，并且在两个方向上都执行此操作。然后取最小值以获得最小割。
参数：
|
输入图。 |
|
指向实变量的指针，结果将存储在此处。 |
|
指向容量向量的指针，它应包含与图中边数相同的非负数。如果为空指针，则所有边的容量均为 1。 |
返回值：
错误代码。 |
另请参阅：
时间复杂度：无向图为 O(log(|V|)*|V|^2)，有向图为 O(|V|^4)，但请参见 igraph_maxflow_value() 文档中的讨论。
igraph_error_t igraph_gomory_hu_tree(const igraph_t *graph,
igraph_t *tree,
igraph_vector_t *flows,
const igraph_vector_t *capacity);
Gomory-Hu 树是图中所有最大流（或最小割）值的简洁表示。树的顶点与原始图中的顶点完全对应，顺序相同。Gomory-Hu 树的边用流值注释。原始图中任意 (u,v) 顶点对之间的最大流（或最小割）的值然后由 Gomory-Hu 树中 u 和 v 之间的最短路径上的最小流值（即边注释）给出。
此实现使用 Gusfield 的算法来构造 Gomory-Hu 树。有关更多详细信息，请参见以下论文
参考
Gusfield D: Very simple methods for all pairs network flow analysis. SIAM J Comput 19(1):143-155, 1990 https://doi.org/10.1137/0219009.
参数：
|
输入图。 |
|
指向未初始化的图的指针；结果将存储在此处。 |
|
指向未初始化向量的指针；与 Gomory-Hu 树中每条边对应的流值将在此处返回。如果您对流值不感兴趣，可以在此处传递 NULL 指针。 |
|
包含边容量的向量。如果为 NULL，则认为每条边的容量为 1.0。 |
返回值：
错误代码。 |
时间复杂度：O(|V|^4)，因为它在顶点零和每个其他顶点之间执行最大流计算，而最大流为 O(|V|^3)。
另请参阅：
igraph_error_t igraph_st_edge_connectivity(const igraph_t *graph,
igraph_integer_t *res,
igraph_integer_t source,
igraph_integer_t target);
两个顶点（source 和 target）的边连通度是必须从图中删除以消除从 source 到 target 的所有路径的最小边数。
此函数使用最大流算法来计算边连通度。
参数：
|
输入图，必须是有向图。 |
|
指向整数的指针，结果将存储在此处。 |
|
源顶点的 ID。 |
|
目标顶点的 ID。 |
返回值：
错误代码。 |
时间复杂度：O(|V|^3)。
另请参阅：
|
igraph_error_t igraph_edge_connectivity(const igraph_t *graph,
igraph_integer_t *res,
igraph_bool_t checks);
这是图表中所有顶点对的边连通度的最小值。
图的边连通度与 Douglas R. White 和 Frank Harary: The cohesiveness of blocks in social networks: node connectivity and conditional density, Sociological Methodology 31:305--359, 2001 https://doi.org/10.1111/0081-1750.00098 中定义的组粘附力相同。
参数：
|
输入图。 |
|
指向整数的指针，结果将存储在此处。 |
|
布尔常量。是否检查图是否已连接以及顶点的度数。如果图未（强）连接，则连通性显然为零。否则，如果最小度数为 1，则边连通性也为 1。执行这些检查是个好主意，因为与连通性计算本身相比，它们可以快速完成。彼得·麦克马洪 (Peter McMahan) 提出了这些建议，谢谢彼得。 |
返回值：
错误代码。 |
时间复杂度：无向图为 O(log(|V|)*|V|^2)，有向图为 O(|V|^4)，但请参见 igraph_maxflow_value() 文档中的讨论。
另请参阅：
igraph_error_t igraph_st_vertex_connectivity(
const igraph_t *graph,
igraph_integer_t *res,
igraph_integer_t source,
igraph_integer_t target,
igraph_vconn_nei_t neighbors);
两个顶点（source 和 target）的顶点连通度是必须删除的最小顶点数，以消除从 source 到 target 的所有路径。在有向图中考虑有向路径。
一对顶点的顶点连通度与从源到目标的不同（即节点独立）路径的数量相同，前提是它们之间没有直接边。
当前实现使用最大流计算来获得结果。
参数：
|
输入图。 |
|
指向整数的指针，结果将存储在此处。 |
|
源顶点的 ID。 |
|
目标顶点的 ID。 |
|
一个常量，用于给出如果两个顶点连接时该怎么做。可能的值： |
返回值：
错误代码。 |
时间复杂度：O(|V|^3)，但请参见 igraph_maxflow_value() 的讨论。
另请参阅：
igraph_error_t igraph_vertex_connectivity(
const igraph_t *graph, igraph_integer_t *res,
igraph_bool_t checks);
图的顶点连通度是图中每对顶点的最小顶点连通度。
图的顶点连通度与 Douglas R. White 和 Frank Harary: The cohesiveness of blocks in social networks: node connectivity and conditional density, Sociological Methodology 31:305--359, 2001 https://doi.org/10.1111/0081-1750.00098 中定义的组内聚力相同。
参数：
|
输入图。 |
|
指向整数的指针，结果将存储在此处。 |
|
布尔常量。是否检查图是否已连接或完整以及顶点的度数。如果图未（强）连接，则连通性显然为零。否则，如果最小度数为 1，则顶点连通性也为 1。如果图是完整的，则连通性是顶点数减 1。执行这些检查是个好主意，因为与连通性计算本身相比，它们可以快速完成。彼得·麦克马洪 (Peter McMahan) 提出了这些建议，谢谢彼得。 |
返回值：
错误代码。 |
时间复杂度：O(|V|^5)。
另请参阅：
igraph_error_t igraph_edge_disjoint_paths(const igraph_t *graph,
igraph_integer_t *res,
igraph_integer_t source,
igraph_integer_t target);
如果两个顶点之间的一组路径不共享任何边，则称为边不相交。此函数使用最大流技术计算最大边不相交路径数。在有向图中考虑有向路径。
请注意，不相交路径的数量与使用统一边权重的两个顶点的边连通度相同。
参数：
|
输入图，可以是定向图或无向图。 |
|
指向整数变量的指针，结果将存储在此处。 |
|
源顶点的 ID。 |
|
目标顶点的 ID。 |
返回值：
错误代码。 |
时间复杂度：O(|V|^3)，但请参见 igraph_maxflow_value() 的讨论。
另请参阅：
igraph_error_t igraph_vertex_disjoint_paths(const igraph_t *graph,
igraph_integer_t *res,
igraph_integer_t source,
igraph_integer_t target);
如果两个顶点之间的路径除了端点外没有共享顶点，则称这些路径是不相交的。此函数计算可以在源顶点和目标顶点之间构建的最大此类路径数。计算是通过使用最大流技术进行的。
当从源顶点到目标顶点没有边时，顶点不相交路径的数量与两个顶点的顶点连通性相同。当存在一些边时，每个边都会贡献一条额外的路径。
参数：
|
输入图。 |
|
指向整数变量的指针，结果将存储在此处。 |
|
源顶点的 ID。 |
|
目标顶点的 ID。 |
返回值：
错误代码。 |
时间复杂度：O(|V|^3)。
另请参阅：
igraph_error_t igraph_adhesion(const igraph_t *graph,
igraph_integer_t *res,
igraph_bool_t checks);
此数量由 White 和 Harary 在 The cohesiveness of blocks in social networks: node connectivity and conditional density, (Sociological Methodology 31:305--359, 2001) 中定义，基本上它是具有均匀边权重的图的边连通性。
参数：
|
输入图，可以是有向图或无向图。 |
|
指向整数的指针，结果将存储在此处。 |
|
布尔常量。是否检查图是否已连接以及顶点的度。如果图未（强）连接，则粘附性显然为零。否则，如果最小度为 1，则粘附性也为 1。执行这些检查是一个好主意，因为与边连通性计算本身相比，它们可以快速完成。它们由 Peter McMahan 提出，感谢 Peter。 * |
返回值：
错误代码。 |
时间复杂度：无向图为 O(log(|V|)*|V|^2)，有向图为 O(|V|^4)，但请参见 igraph_maxflow_value() 文档中的讨论。
另请参阅：
igraph_error_t igraph_cohesion(const igraph_t *graph,
igraph_integer_t *res,
igraph_bool_t checks);
此数量由 White 和 Harary 在 “社会网络中块的凝聚力：节点连通性和条件密度”, (Sociological Methodology 31:305--359, 2001) 中定义，它与图的顶点连通性相同。
参数：
|
输入图。 |
|
指向整数变量的指针，结果将存储在此处。 |
|
布尔常量。是否检查图是否已连接以及顶点的度。如果图未（强）连接，则凝聚力显然为零。否则，如果最小度为 1，则凝聚力也为 1。执行这些检查是一个好主意，因为与顶点连通性计算本身相比，它们可以快速完成。它们由 Peter McMahan 提出，感谢 Peter。 |
返回值：
错误代码。 |
时间复杂度：O(|V|^4)，|V| 是顶点数。实际上它更像是 O(|V|^2)，请参阅 igraph_maxflow_value()。
另请参阅：
igraph_error_t igraph_cohesive_blocks(const igraph_t *graph,
igraph_vector_int_list_t *blocks,
igraph_vector_int_t *cohesion,
igraph_vector_int_t *parent,
igraph_t *block_tree);
凝聚块是一种基于其结构凝聚力（或顶点连通性）确定图顶点分层子集的方法。对于给定的图 G，如果 S 没有顶点连通性大于或等于 k 的超集，则称其顶点子集 S 是最大 k 凝聚的。凝聚块是一种过程，通过该过程，给定一个 k 凝聚顶点集，以递归方式识别最大 l 凝聚子集，其中 l>k。因此，可以找到一个顶点子集层次结构，整个图 G 位于其根。
此函数实现凝聚块并计算图的完整凝聚块层次结构。
有关详细信息，请参阅以下参考
J. Moody 和 D. R. White。Structural cohesion and embeddedness: A hierarchical concept of social groups。American Sociological Review, 68(1):103--127, Feb 2003。 https://doi.org/10.2307/3088904
参数：
|
输入图。它必须是无向的和简单的。请参阅 |
|
如果不是空指针，则它必须是一个初始化的整数向量列表；凝聚块将存储在此处。每个块都用一个类型为 |
|
如果不是空指针，则它必须是一个初始化的向量，并且块的凝聚力存储在此处，顺序与 |
|
如果不是空指针，则它必须是一个初始化的向量，并且块层次结构存储在此处。对于每个块，存储其父块的 ID（即 |
|
如果不是空指针，则它必须是指向未初始化的图的指针，并且块层次结构将作为 igraph 图存储在此处。顶点 ID 对应于 |
返回值：
错误代码。 |
时间复杂度：待定。
示例 22.6. 文件 examples/simple/cohesive_blocks.c
#include <igraph.h> int main(void) { igraph_t g; igraph_vector_int_list_t blocks; igraph_vector_int_t cohesion; igraph_vector_int_t parent; igraph_t block_tree; igraph_integer_t i; igraph_famous(&g, "zachary"); igraph_vector_int_list_init(&blocks, 0); igraph_vector_int_init(&cohesion, 0); igraph_vector_int_init(&parent, 0); igraph_cohesive_blocks(&g, &blocks, &cohesion, &parent, &block_tree); printf("Blocks:\n"); for (i = 0; i < igraph_vector_int_list_size(&blocks); i++) { igraph_vector_int_t *sg = igraph_vector_int_list_get_ptr(&blocks, i); printf(" "); igraph_vector_int_print(sg); } printf("Cohesion:\n "); igraph_vector_int_print(&cohesion); printf("Parents:\n "); igraph_vector_int_print(&parent); printf("Block graph:\n"); igraph_write_graph_edgelist(&block_tree, stdout); igraph_vector_int_list_destroy(&blocks); igraph_vector_int_destroy(&cohesion); igraph_vector_int_destroy(&parent); igraph_destroy(&block_tree); igraph_destroy(&g); return 0; }
| ← 章节 21. 从文件读取图并写入文件 | 章节 23. 顶点分隔符 → |