igraph 参考手册

用于使用 igraph C 库

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

第 15 章. 图访问器

1. 广度优先搜索
2. 深度优先搜索
3. 随机游走
4. 已弃用的函数

1. 广度优先搜索

1.1. igraph_bfs — 广度优先搜索。
1.2. igraph_bfs_simple — 广度优先搜索，单源版本
1.3. igraph_bfshandler_t — BFS 函数的回调类型。

1.1. igraph_bfs — 广度优先搜索。

igraph_error_t igraph_bfs(const igraph_t *graph,
               igraph_integer_t root, const igraph_vector_int_t *roots,
               igraph_neimode_t mode, igraph_bool_t unreachable,
               const igraph_vector_int_t *restricted,
               igraph_vector_int_t *order, igraph_vector_int_t *rank,
               igraph_vector_int_t *parents,
               igraph_vector_int_t *pred, igraph_vector_int_t *succ,
               igraph_vector_int_t *dist, igraph_bfshandler_t *callback,
               void *extra);

一个简单的广度优先搜索，具有许多不同的结果，并且可以在访问顶点时调用回调。允许提供空指针作为用户不感兴趣的输出参数，在这种情况下它们将被忽略。

如果并非所有顶点都可以从提供的根顶点到达，则将使用其他根顶点，按其顶点 ID 的顺序。

如果您将此函数提供的大部分输出参数设置为空指针，请考虑使用 igraph_bfs_simple 代替。

参数： 

图:

输入图。

root:

根顶点的 ID。如果 roots 参数不是空指针，则忽略它。

roots:

指向已初始化的向量的指针，或空指针。如果不是空指针，则它是一个包含从其开始 BFS 的根顶点的向量。顶点按它们出现的顺序被考虑。如果从另一个顶点搜索时已经找到了一个根顶点，则不会从中进行搜索。

模式:

对于有向图，它定义了要遵循的边。IGRAPH_OUT 表示沿着边的方向，IGRAPH_IN 表示相反的方向，IGRAPH_ALL 忽略边的方向。此参数对于无向图将被忽略。

unreachable:

布尔值，搜索是否应访问从给定根节点无法到达的顶点。如果为 true，则会执行其他搜索，直到访问所有顶点。

restricted:

如果不是空指针，则它必须是指向包含顶点 ID 的向量的指针。 BFS 仅在这些顶点上执行。

order:

如果不是空指针，则图的顶点 ID 将存储在此处，顺序与它们被访问的顺序相同。

rank:

如果不是空指针，则每个顶点的等级将存储在此处。

parents:

如果不是空指针，则每个顶点的父级的 ID 将存储在此处。如果顶点在遍历期间未被访问，则 -2 将存储为其父级的 ID。如果顶点在遍历期间被访问，并且它是搜索树的根之一，则 -1 将存储为其父级的 ID。

pred:

如果不是空指针，则当前顶点之前访问的顶点的 ID 将存储在此处。如果没有这样的顶点（当前顶点是搜索树的根），则 -1 将存储为该顶点的前任。如果该顶点根本未被访问，则 -2 将存储为该顶点的前任。

succ:

如果不是空指针，则当前顶点之后访问的顶点的 ID 将存储在此处。如果没有这样的顶点（当前顶点是搜索树中的最后一个），则 -1 将存储为该顶点的后继。如果该顶点根本未被访问，则 -2 将存储为该顶点的后继。

dist:

如果不是空指针，则当前搜索树的根到每个顶点的距离将存储在此处。如果在遍历期间未到达顶点，则此向量中其距离将为 -1。

callback:

如果不是空值，则它应该是指向 igraph_bfshandler_t 类型的函数的指针。每当访问新顶点时，将调用此函数。

extra:

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

返回值： 

错误代码。

时间复杂度：O(|V|+|E|)，顶点数和边数的线性关系。

示例 15.1.  文件 examples/simple/igraph_bfs.c

#include <igraph.h>

int main(void) {

    igraph_t graph, ring;
    igraph_vector_int_t order, rank, father, pred, succ, dist;

    /* Create a disjoint union of two rings */
    igraph_ring(&ring, 10, /*directed=*/ 0, /*mutual=*/ 0, /*circular=*/ 1);
    igraph_disjoint_union(&graph, &ring, &ring);
    igraph_destroy(&ring);

    /* Initialize the vectors where the result will be stored. Any of these
     * can be omitted and replaced with a null pointer when calling
     * igraph_bfs() */
    igraph_vector_int_init(&order, 0);
    igraph_vector_int_init(&rank, 0);
    igraph_vector_int_init(&father, 0);
    igraph_vector_int_init(&pred, 0);
    igraph_vector_int_init(&succ, 0);
    igraph_vector_int_init(&dist, 0);

    /* Now call the BFS function */
    igraph_bfs(&graph, /*root=*/0, /*roots=*/ NULL, /*neimode=*/ IGRAPH_OUT,
               /*unreachable=*/ 1, /*restricted=*/ NULL,
               &order, &rank, &father, &pred, &succ, &dist,
               /*callback=*/ NULL, /*extra=*/ NULL);

    /* Print the results */
    igraph_vector_int_print(&order);
    igraph_vector_int_print(&rank);
    igraph_vector_int_print(&father);
    igraph_vector_int_print(&pred);
    igraph_vector_int_print(&succ);
    igraph_vector_int_print(&dist);

    /* Cleam up after ourselves */
    igraph_vector_int_destroy(&order);
    igraph_vector_int_destroy(&rank);
    igraph_vector_int_destroy(&father);
    igraph_vector_int_destroy(&pred);
    igraph_vector_int_destroy(&succ);
    igraph_vector_int_destroy(&dist);

    igraph_destroy(&graph);

    return 0;
}


示例 15.2.  文件 examples/simple/igraph_bfs_callback.c

#include <igraph.h>

igraph_error_t bfs_callback(const igraph_t *graph,
                           igraph_integer_t vid,
                           igraph_integer_t pred,
                           igraph_integer_t succ,
                           igraph_integer_t rank,
                           igraph_integer_t dist,
                           void *extra) {
    IGRAPH_UNUSED(graph);
    IGRAPH_UNUSED(pred);
    IGRAPH_UNUSED(succ);
    IGRAPH_UNUSED(rank);
    IGRAPH_UNUSED(dist);
    printf(" %" IGRAPH_PRId "", vid);
    return IGRAPH_SUCCESS;
}

int main(void) {
    igraph_t graph, ring;

    /* Create a disjoint union of two rings */
    igraph_ring(&ring, 10, /*directed=*/ 0, /*mutual=*/ 0, /*circular=*/ 1);
    igraph_disjoint_union(&graph, &ring, &ring);
    igraph_destroy(&ring);

    /* Now call the BFS function */
    printf("(");
    igraph_bfs(&graph, /*root=*/0, /*roots=*/ 0, /*neimode=*/ IGRAPH_OUT,
               /*unreachable=*/ 1, /*restricted=*/ 0,
               /*order=*/ 0, /*rank=*/ 0, /*father=*/ 0, /*pred=*/ 0,
               /*succ=*/ 0, /*dist=*/ 0,
               /*callback=*/ bfs_callback, /*extra=*/ 0);
    printf(" )\n");

    /* Cleam up after ourselves */
    igraph_destroy(&graph);

    return 0;
}


1.2. igraph_bfs_simple — 广度优先搜索，单源版本

igraph_error_t igraph_bfs_simple(
    const igraph_t *graph, igraph_integer_t root, igraph_neimode_t mode,
    igraph_vector_int_t *order, igraph_vector_int_t *layers,
    igraph_vector_int_t *parents
);

一种替代的广度优先搜索实现，用于满足更简单的用例，即仅必须从源节点执行单个广度优先搜索，并且不需要来自 igraph_bfs 的大多数输出参数。允许提供空指针作为用户不感兴趣的输出参数，在这种情况下它们将被忽略。

参数： 

图:

输入图。

root:

根顶点的 ID。

模式:

对于有向图，它定义了要遵循的边。IGRAPH_OUT 表示沿着边的方向，IGRAPH_IN 表示相反的方向，IGRAPH_ALL 忽略边的方向。此参数对于无向图将被忽略。

order:

如果不是空指针，则必须在此处传递一个已初始化的向量。在此期间访问的顶点的 ID 将存储在此处，顺序与它们被访问的顺序相同。

layers:

如果不是空指针，则必须在此处传递一个已初始化的向量。该向量的第 i 个元素将包含进入 order 的索引，其中存储了距离根为 i 的顶点。换句话说，如果您对距离根为 i 的顶点感兴趣，则需要从 layers[i] 到 layers[i+1] 在 order 向量中查找。

parents:

如果不是空指针，则必须在此处传递一个已初始化的向量。该向量将被调整大小，使其长度等于节点数，并且它将包含每个 已访问 节点的父节点的索引。向量中的值对于 未 访问的顶点设置为 -2，对于根顶点设置为 -1。

返回值： 

错误代码。

时间复杂度：O(|V|+|E|)，顶点数和边数的线性关系。

示例 15.3.  文件 examples/simple/igraph_bfs_simple.c

#include <igraph.h>

int main(void) {

    igraph_t g;
    igraph_vector_int_t vids, layers, parents;

    igraph_ring(&g, 10, IGRAPH_UNDIRECTED, 0, 0);

    igraph_vector_int_init(&vids, 0);
    igraph_vector_int_init(&layers, 0);
    igraph_vector_int_init(&parents, 0);

    igraph_bfs_simple(&g, 0, IGRAPH_ALL, &vids, &layers, &parents);

    igraph_vector_int_print(&vids);
    igraph_vector_int_print(&layers);
    igraph_vector_int_print(&parents);

    igraph_destroy(&g);

    igraph_vector_int_destroy(&vids);
    igraph_vector_int_destroy(&layers);
    igraph_vector_int_destroy(&parents);

    return 0;
}


1.3. igraph_bfshandler_t — BFS 函数的回调类型。

typedef igraph_error_t igraph_bfshandler_t(const igraph_t *graph,
        igraph_integer_t vid,
        igraph_integer_t pred,
        igraph_integer_t succ,
        igraph_integer_t rank,
        igraph_integer_t dist,
        void *extra);

igraph_bfs() 能够在执行广度优先搜索时，在找到新顶点时调用回调函数。此回调函数必须是 igraph_bfshandler_t 类型。它具有以下参数

参数： 

图:

算法正在处理的图。当然，这不能被修改。

vid:

广度优先搜索刚刚找到的顶点的 ID。

pred:

之前访问的顶点的 ID。如果不存在之前的顶点，则它是 -1，因为当前顶点是搜索树的根。

succ:

下一个将被访问的顶点的 ID。如果不存在下一个顶点，则它是 -1，因为当前顶点是搜索树中的最后一个。

rank:

当前顶点的等级，它从零开始。

dist:

当前顶点到当前搜索树的根的距离（跳数）。

extra:

传递给 igraph_bfs() 的额外参数。

返回值： 

如果 BFS 应该继续，则为 IGRAPH_SUCCESS，如果 BFS 应该停止并正常返回给调用者，则为 IGRAPH_STOP。任何其他值都被视为 igraph 错误代码，终止搜索并以相同的错误代码返回给调用者。如果 BFS 被过早终止，则在终止点尚未计算的所有结果向量元素都包含负值。

另请参阅： 

igraph_bfs()

2. 深度优先搜索

2.1. igraph_dfs — 深度优先搜索。
2.2. igraph_dfshandler_t — DFS 函数的回调类型。

2.1. igraph_dfs — 深度优先搜索。

igraph_error_t igraph_dfs(const igraph_t *graph, igraph_integer_t root,
               igraph_neimode_t mode, igraph_bool_t unreachable,
               igraph_vector_int_t *order,
               igraph_vector_int_t *order_out, igraph_vector_int_t *parents,
               igraph_vector_int_t *dist, igraph_dfshandler_t *in_callback,
               igraph_dfshandler_t *out_callback,
               void *extra);

一种简单的深度优先搜索，可以在发现顶点时和/或完成子树时调用回调。允许提供空指针作为用户不感兴趣的输出参数，在这种情况下它们将被忽略。

如果并非所有顶点都可以从提供的根顶点到达，则将使用其他根顶点，按其顶点 ID 的顺序。

参数： 

图:

输入图。

root:

根顶点的 ID。

模式:

对于有向图，它定义了要遵循的边。IGRAPH_OUT 表示沿着边的方向，IGRAPH_IN 表示相反的方向，IGRAPH_ALL 忽略边的方向。此参数对于无向图将被忽略。

unreachable:

布尔值，搜索是否应访问从给定根节点无法到达的顶点。如果为 true，则会执行其他搜索，直到访问所有顶点。

order:

如果不是空指针，则图的顶点 ID 将存储在此处，顺序与它们被发现的顺序相同。向量的尾部将填充 -1，以确保向量的长度与顶点数相同，即使在遍历期间未访问某些顶点。

order_out:

如果不是空指针，则图的顶点 ID 将存储在此处，顺序与它们的子树完成的顺序相同。向量的尾部将填充 -1，以确保向量的长度与顶点数相同，即使在遍历期间未访问某些顶点。

parents:

如果不是空指针，则每个顶点的父级的 ID 将存储在此处。 -1 将存储为搜索树的根；-2 将存储为未访问的顶点。

dist:

如果不是空指针，则当前搜索树的根到每个顶点的距离将存储在此处。 -1 将存储为未访问的顶点。

in_callback:

如果不是空值，则它应该是指向 igraph_dfshandler_t 类型的函数的指针。每当发现新顶点时，将调用此函数。

out_callback:

如果不是空值，则它应该是指向 igraph_dfshandler_t 类型的函数的指针。每当完成顶点的子树时，将调用此函数。

extra:

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

返回值： 

错误代码。

时间复杂度：O(|V|+|E|)，顶点数和边数的线性关系。

2.2. igraph_dfshandler_t — DFS 函数的回调类型。

typedef igraph_error_t igraph_dfshandler_t(const igraph_t *graph,
        igraph_integer_t vid,
        igraph_integer_t dist,
        void *extra);

igraph_dfs() 能够在发现新顶点时和/或完成子树时调用回调函数。这些回调必须是 igraph_dfshandler_t 类型。它们具有以下参数

参数： 

图:

算法正在处理的图。当然，这不能被修改。

vid:

深度优先搜索刚刚找到的顶点的 ID。

dist:

当前顶点到当前搜索树的根的距离（跳数）。

extra:

传递给 igraph_dfs() 的额外参数。

返回值： 

如果 DFS 应该继续，则为 IGRAPH_SUCCESS，如果 DFS 应该停止并正常返回给调用者，则为 IGRAPH_STOP。任何其他值都被视为 igraph 错误代码，终止搜索并以相同的错误代码返回给调用者。如果 DFS 被过早终止，则在终止点尚未计算的所有结果向量元素都包含负值。

另请参阅： 

igraph_dfs()

3. 随机游走

3.1. igraph_random_walk — 在图上执行随机游走。

3.1. igraph_random_walk — 在图上执行随机游走。

igraph_error_t igraph_random_walk(const igraph_t *graph,
                       const igraph_vector_t *weights,
                       igraph_vector_int_t *vertices,
                       igraph_vector_int_t *edges,
                       igraph_integer_t start,
                       igraph_neimode_t mode,
                       igraph_integer_t steps,
                       igraph_random_walk_stuck_t stuck);

从给定的起始顶点，在图上执行给定长度的随机游走。边方向（可能）被考虑，具体取决于 mode 参数。

参数： 

图:

输入图，它可以是有向图或无向图。尊重多重边，也尊重自环边。

weights:

一个非负边权重的向量。假设在每个顶点的外向边中至少找到一个严格正权重。此外，任何边权重都不能是 NaN。如果任何一种情况不成立，则返回错误。如果它是 NULL，则所有边都被认为具有相等的权重。

vertices:

一个已分配的向量，结果作为顶点 ID 列表存储在此处。它将根据需要调整大小。它包括起始顶点和结束顶点的顶点 ID。顶点向量的长度：steps + 1

边:

一个已初始化的向量，遍历的边的索引存储在此处。它将根据需要调整大小。边向量的长度：steps

开始:

游走的起始顶点。

steps:

要采取的步数。如果随机游走被卡住，则 stuck 参数指定会发生什么。steps 是游走期间要遍历的边数。

模式:

如何在有向图中沿着边游走。IGRAPH_OUT 表示沿着边的方向，IGRAPH_IN 表示沿着边的相反方向，IGRAPH_ALL 表示忽略边的方向。此参数对于无向图将被忽略。

stuck:

如果随机游走被卡住，该怎么办。IGRAPH_RANDOM_WALK_STUCK_RETURN 表示该函数返回较短的游走；IGRAPH_RANDOM_WALK_STUCK_ERROR 表示报告一个 IGRAPH_ERWSTUCK 错误。在这两种情况下，vertices 和 edges 都会被截断以包含实际中断的游走。

返回值： 

错误代码：IGRAPH_ERWSTUCK 如果游走被卡住。

时间复杂度：对于未加权图为 O(l + d)，对于加权图为 O(l * log(k) + d)，其中 l 是游走的长度，d 是访问节点的总度数，k 是给定图的顶点的平均度数。

4. 已弃用的函数

4.1. igraph_random_edge_walk — 在图上执行随机游走并返回遍历的边。

4.1. igraph_random_edge_walk — 在图上执行随机游走并返回遍历的边。

igraph_error_t igraph_random_edge_walk(
        const igraph_t *graph,
        const igraph_vector_t *weights,
        igraph_vector_int_t *edgewalk,
        igraph_integer_t start, igraph_neimode_t mode,
        igraph_integer_t steps,
        igraph_random_walk_stuck_t stuck);

从给定的起始顶点，在图上执行给定长度的随机游走。边方向（可能）被考虑，具体取决于 mode 参数。

参数： 

图:

输入图，它可以是有向图或无向图。尊重多重边，也尊重自环边。

weights:

一个非负边权重的向量。假设在每个顶点的外向边中至少找到一个严格正权重。此外，任何边权重都不能是 NaN。如果任何一种情况不成立，则返回错误。如果它是 NULL 指针，则所有边都被认为具有相等的权重。

edgewalk:

一个已初始化的向量；遍历的边的索引存储在此处。它将根据需要调整大小。

开始:

游走的起始顶点。

steps:

要采取的步数。如果随机游走被卡住，则 stuck 参数指定会发生什么。

模式:

如何在有向图中沿着边游走。IGRAPH_OUT 表示沿着边的方向，IGRAPH_IN 表示沿着边的相反方向，IGRAPH_ALL 表示忽略边的方向。此参数对于无向图将被忽略。

stuck:

如果随机游走被卡住，该怎么办。IGRAPH_RANDOM_WALK_STUCK_RETURN 表示该函数返回较短的游走；IGRAPH_RANDOM_WALK_STUCK_ERROR 表示报告一个 IGRAPH_ERWSTUCK 错误。在这两种情况下，edgewalk 都会被截断以包含实际中断的游走。

返回值： 

错误代码。

警告

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

← 第 14 章. 图循环 第 16 章. 团和独立顶点集 →