igraph 参考手册

用于使用 igraph C 库

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

第 20 章 生成图绘制的布局

1. 2D 布局生成器
2. 树和无环图的布局
3. 3D 布局生成器
4. 合并布局

1. 2D 布局生成器

1.1. igraph_layout_random — 在平面上均匀随机地放置顶点。
1.2. igraph_layout_circle — 将顶点均匀地放置在一个圆上，顺序任意。
1.3. igraph_layout_star — 生成星状布局。
1.4. igraph_layout_grid — 将顶点放置在平面上的规则网格上。
1.5. igraph_layout_graphopt — 通过 graphopt 算法优化顶点布局。
1.6. igraph_layout_bipartite — 二分图的简单布局。
1.7. DrL 布局生成器
1.8. igraph_layout_fruchterman_reingold — 根据 Fruchterman-Reingold 算法将顶点放置在平面上。
1.9. igraph_layout_kamada_kawai — 根据 Kamada-Kawai 算法将顶点放置在平面上。
1.10. igraph_layout_gem — 根据 GEM 算法布局图。
1.11. igraph_layout_davidson_harel — Davidson-Harel 布局算法。
1.12. igraph_layout_mds — 使用多维缩放将顶点放置在平面上。
1.13. igraph_layout_lgl — 用于大型图的基于力的布局算法。

布局生成器函数（或至少它们中的大多数）尝试以视觉上令人愉悦的方式将图的顶点和边放置在 2D 平面上或 3D 空间中。

它们接受一个图对象和一些参数作为参数，并返回一个 igraph_matrix_t，其中每一行给出一个顶点的坐标。

1.1. igraph_layout_random — 在平面上均匀随机地放置顶点。

igraph_error_t igraph_layout_random(const igraph_t *graph, igraph_matrix_t *res);

参数： 

图:

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

res:

指向已初始化矩阵对象的指针。这将包含结果，并将根据需要调整大小。

返回值： 

错误代码。当前实现始终返回成功。

时间复杂度：O(|V|)，顶点的数量。

1.2. igraph_layout_circle — 将顶点均匀地放置在一个圆上，顺序任意。

igraph_error_t igraph_layout_circle(const igraph_t *graph, igraph_matrix_t *res,
                         igraph_vs_t order);

参数： 

图:

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

res:

指向已初始化矩阵对象的指针。这将包含结果，并将根据需要调整大小。

order:

顶点在圆上的顺序。此处未包含的顶点将放置在 (0,0) 处。在此处提供 igraph_vss_all() 以按顶点 ID 的顺序放置顶点。

返回值： 

错误代码。

时间复杂度：O(|V|)，顶点的数量。

1.3. igraph_layout_star — 生成星状布局。

igraph_error_t igraph_layout_star(const igraph_t *graph, igraph_matrix_t *res,
                       igraph_integer_t center, const igraph_vector_int_t *order);

参数： 

图:

输入图。此函数忽略其边。

res:

指向已初始化矩阵对象的指针。这将包含结果，并将根据需要调整大小。

center:

要放置在中心的顶点的 ID。对于输入图没有顶点的特殊情况，您可以将其设置为任何任意值；否则，它必须介于 0 和顶点数减 1 之间。

order:

一个数值向量，给出顶点的顺序（包括中心顶点！）。如果为空指针，则顶点按递增的顶点 ID 顺序放置。

返回值： 

错误代码。

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

另请参阅： 

igraph_layout_circle() 和其他布局生成器。

1.4. igraph_layout_grid — 将顶点放置在平面上的规则网格上。

igraph_error_t igraph_layout_grid(const igraph_t *graph, igraph_matrix_t *res, igraph_integer_t width);

参数： 

图:

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

res:

指向已初始化矩阵对象的指针。这将包含结果，并将根据需要调整大小。

width:

网格中单行的顶点数。当为零或负数时，网格的宽度将是顶点数的平方根，如果需要则向上取整。

返回值： 

错误代码。当前实现始终返回成功。

时间复杂度：O(|V|)，顶点的数量。

1.5. igraph_layout_graphopt — 通过 graphopt 算法优化顶点布局。

igraph_error_t igraph_layout_graphopt(const igraph_t *graph, igraph_matrix_t *res,
                           igraph_integer_t niter,
                           igraph_real_t node_charge, igraph_real_t node_mass,
                           igraph_real_t spring_length,
                           igraph_real_t spring_constant,
                           igraph_real_t max_sa_movement,
                           igraph_bool_t use_seed);

这是 Michael Schmuhl 的 graphopt 布局算法的端口。 graphopt 版本 0.4.1 用 C 重写，删除了对层的支持，并重新组织了代码以避免节点电荷（见下文）为零时的一些不必要的步骤。

Graphopt 使用物理类比来定义顶点之间的吸引力和排斥力，然后模拟物理系统直到达到平衡。（没有模拟退火或类似的东西，因此不能保证稳定的固定点。）

另请参见 https://web.archive.org/web/20220611030748/http://www.schmuhl.org/graphopt/ 和 https://sourceforge.net/projects/graphopt/ 以获取原始 graphopt。

参数： 

图:

输入图。

res:

指向已初始化矩阵的指针，结果将存储在此处，如果 use_seed 参数为真，则其初始内容将用作模拟的起点。请注意，在这种情况下，矩阵应该具有适当的大小，否则会发出警告，并且提供的价值观将被忽略。如果未给出起始位置（或它们无效），则使用随机起始位置。如果需要，矩阵将调整大小。

niter:

整数常量，要执行的迭代次数。通常应该有几百个。如果您有一个大型图，那么您可能只想进行少量迭代，然后检查结果。如果它不够好，您可以将其再次馈入 res 参数中。原始 graphopt 默认值为 500。

node_charge:

顶点的电荷，用于计算静电斥力。原始 graphopt 默认值为 0.001。

node_mass:

顶点的质量，用于弹簧力。原始 graphopt 默认为 30。

spring_length:

弹簧的长度。原始 graphopt 默认为零。

spring_constant:

弹簧常数，原始 graphopt 默认为 1。

max_sa_movement:

实数常量，它给出了沿单个轴的单个步骤中允许的最大移动量。原始 graphopt 默认值为 5。

use_seed:

布尔值，是否使用 res 中的位置作为起始配置。另请参见上面的 res。

返回值： 

错误代码。

时间复杂度：O(n (|V|^2+|E|) )，n 是迭代次数，|V| 是顶点数，|E| 是边数。如果 node_charge 为零，则仅为 O(n|E|)。

1.6. igraph_layout_bipartite — 二分图的简单布局。

igraph_error_t igraph_layout_bipartite(const igraph_t *graph,
                            const igraph_vector_bool_t *types,
                            igraph_matrix_t *res, igraph_real_t hgap,
                            igraph_real_t vgap, igraph_integer_t maxiter);

通过首先将顶点放置在两行中，根据它们的类型创建布局。然后，通过调用 igraph_layout_sugiyama()，优化行内的位置以最小化边的交叉。

参数： 

图:

输入图。

types:

一个布尔向量，包含 1 和 0，表示顶点类型。它的长度必须与图中的顶点数匹配。

res:

指向已初始化矩阵的指针，结果，x 和 y 坐标存储在此处。

hgap:

同一层中（即相同类型的顶点）顶点之间首选的最小水平间隙。

vgap:

图层之间的距离。

maxiter:

交叉最小化阶段的最大迭代次数。 100 是一个合理的默认值；如果您觉得边的交叉太多，请增加此值。

返回值： 

错误代码。

另请参阅： 

igraph_layout_sugiyama().

1.7. DrL 布局生成器

1.7.1. igraph_layout_drl_options_t — DrL 布局生成器的参数
1.7.2. igraph_layout_drl_default_t — DrL 布局生成器的预定义参数模板
1.7.3. igraph_layout_drl_options_init — 初始化 DrL 布局生成器的参数
1.7.4. igraph_layout_drl — DrL 布局生成器
1.7.5. igraph_layout_drl_3d — DrL 布局生成器，3d 版本。

DrL 是由 Shawn Martin 等人开发和实施的复杂的布局生成器。截至 2012 年 10 月，原始 DrL 主页不幸地不可用。您可以在以下技术报告中阅读有关此算法的更多信息：Martin, S., Brown, W.M., Klavans, R., Boyack, K.W., DrL: Distributed Recursive (Graph) Layout. SAND Reports, 2008. 2936: p. 1-10。

igraph 中仅包含 DrL 完整功能的一个子集，不支持并行运行和递归、多级布局。

布局的参数存储在 igraph_layout_drl_options_t 结构中，可以通过调用函数 igraph_layout_drl_options_init() 来初始化它。如果需要，然后可以手动调整此结构的字段。通过调用 igraph_layout_drl() 来计算布局。

1.7.1. igraph_layout_drl_options_t — DrL 布局生成器的参数

typedef struct igraph_layout_drl_options_t {
    igraph_real_t    edge_cut;
    igraph_integer_t init_iterations;
    igraph_real_t    init_temperature;
    igraph_real_t    init_attraction;
    igraph_real_t    init_damping_mult;
    igraph_integer_t liquid_iterations;
    igraph_real_t    liquid_temperature;
    igraph_real_t    liquid_attraction;
    igraph_real_t    liquid_damping_mult;
    igraph_integer_t expansion_iterations;
    igraph_real_t    expansion_temperature;
    igraph_real_t    expansion_attraction;
    igraph_real_t    expansion_damping_mult;
    igraph_integer_t cooldown_iterations;
    igraph_real_t    cooldown_temperature;
    igraph_real_t    cooldown_attraction;
    igraph_real_t    cooldown_damping_mult;
    igraph_integer_t crunch_iterations;
    igraph_real_t    crunch_temperature;
    igraph_real_t    crunch_attraction;
    igraph_real_t    crunch_damping_mult;
    igraph_integer_t simmer_iterations;
    igraph_real_t    simmer_temperature;
    igraph_real_t    simmer_attraction;
    igraph_real_t    simmer_damping_mult;
} igraph_layout_drl_options_t;

值： 

edge_cut:

边切割参数。边切割是在算法的后期阶段完成的，目的是实现较少的密集布局。如果边上的应力很大（目标函数和中的一个大值），则切割边。边切割参数是一个介于 0 和 1 之间的值，其中 0 表示不切割边，而 1 表示最大边切割。默认值为 32/40。

init_iterations:

迭代次数，初始阶段。

init_temperature:

起始温度，初始阶段。

init_attraction:

吸引力，初始阶段。

init_damping_mult:

阻尼因子，初始阶段。

liquid_iterations:

液体阶段的迭代次数。

liquid_temperature:

液体阶段的起始温度。

liquid_attraction:

液体阶段的吸引力。

liquid_damping_mult:

Multiplicatie 阻尼因子，液体阶段。

expansion_iterations:

扩展阶段的迭代次数。

expansion_temperature:

扩展阶段的起始温度。

expansion_attraction:

吸引力，扩展阶段。

expansion_damping_mult:

阻尼因子，扩展阶段。

cooldown_iterations:

冷却阶段的迭代次数。

cooldown_temperature:

冷却阶段的起始温度。

cooldown_attraction:

冷却阶段的吸引力。

cooldown_damping_mult:

冷却阶段的阻尼因子。

crunch_iterations:

压缩阶段的迭代次数。

crunch_temperature:

压缩阶段的起始温度。

crunch_attraction:

压缩阶段的吸引力。

crunch_damping_mult:

压缩阶段的阻尼因子。

simmer_iterations:

煨炖阶段的迭代次数。

simmer_temperature:

煨炖阶段的起始温度。

simmer_attraction:

煨炖阶段的吸引力。

simmer_damping_mult:

煨炖阶段的乘法阻尼因子。

1.7.2. igraph_layout_drl_default_t — DrL 布局生成器的预定义参数模板

typedef enum { IGRAPH_LAYOUT_DRL_DEFAULT = 0,
               IGRAPH_LAYOUT_DRL_COARSEN,
               IGRAPH_LAYOUT_DRL_COARSEST,
               IGRAPH_LAYOUT_DRL_REFINE,
               IGRAPH_LAYOUT_DRL_FINAL
             } igraph_layout_drl_default_t;

这些常量可用于初始化一组 DrL 参数。然后可以根据用户的需要修改这些参数。

值： 

IGRAPH_LAYOUT_DRL_DEFAULT:

默认参数。

IGRAPH_LAYOUT_DRL_COARSEN:

略微修改的参数以获得更粗糙的布局。

IGRAPH_LAYOUT_DRL_COARSEST:

更粗糙的布局。

IGRAPH_LAYOUT_DRL_REFINE:

优化已计算的布局。

IGRAPH_LAYOUT_DRL_FINAL:

完成已经优化的布局。

1.7.3. igraph_layout_drl_options_init — 初始化 DrL 布局生成器的参数

igraph_error_t igraph_layout_drl_options_init(igraph_layout_drl_options_t *options,
                                   igraph_layout_drl_default_t templ);

此函数可用于初始化保存 DrL 布局生成器参数的结构。有许多预定义的模板可用，最好从修改某些参数的模板之一开始。

参数： 

选项:

要初始化的结构。

templ:

要使用的模板。目前提供了以下模板：IGRAPH_LAYOUT_DRL_DEFAULT、IGRAPH_LAYOUT_DRL_COARSEN、IGRAPH_LAYOUT_DRL_COARSEST、IGRAPH_LAYOUT_DRL_REFINE 和 IGRAPH_LAYOUT_DRL_FINAL。

返回值： 

错误代码。

时间复杂度：O(1)。

1.7.4. igraph_layout_drl — DrL 布局生成器

igraph_error_t igraph_layout_drl(const igraph_t *graph, igraph_matrix_t *res,
                      igraph_bool_t use_seed,
                      const igraph_layout_drl_options_t *options,
                      const igraph_vector_t *weights);

此函数实现力导向 DrL 布局生成器。请在以下技术报告中查看更多信息：Martin, S., Brown, W.M., Klavans, R., Boyack, K.W., DrL: Distributed Recursive (Graph) Layout. SAND Reports, 2008. 2936: p. 1-10。

参数： 

图:

输入图。

use_seed:

布尔值，如果为真，则使用 res 参数中提供的坐标作为起点。

res:

指向矩阵的指针，结果布局存储在此处。将根据需要调整大小。

选项:

要传递给布局生成器的参数。

weights:

边权重，指向向量的指针。如果这是一个空指针，则每条边将具有相同的权重。

返回值： 

错误代码。

时间复杂度：???

1.7.5. igraph_layout_drl_3d — DrL 布局生成器，3d 版本。

igraph_error_t igraph_layout_drl_3d(const igraph_t *graph, igraph_matrix_t *res,
                         igraph_bool_t use_seed,
                         const igraph_layout_drl_options_t *options,
                         const igraph_vector_t *weights);

此函数实现力导向 DrL 布局生成器。请在技术报告中查看更多信息：Martin, S., Brown, W.M., Klavans, R., Boyack, K.W., DrL: Distributed Recursive (Graph) Layout. SAND Reports, 2008. 2936: p. 1-10。

此函数使用修改后的 DrL 生成器，该生成器在三个维度中进行布局。

参数： 

图:

输入图。

use_seed:

布尔值，如果为真，则使用 res 参数中提供的坐标作为起点。

res:

指向矩阵的指针，结果布局存储在此处。将根据需要调整大小。

选项:

要传递给布局生成器的参数。

weights:

边权重，指向向量的指针。如果这是一个空指针，则每条边将具有相同的权重。

返回值： 

错误代码。

时间复杂度：???

另请参阅： 

标准 2d 版本的 igraph_layout_drl()。

1.8. igraph_layout_fruchterman_reingold — 根据 Fruchterman-Reingold 算法将顶点放置在平面上。

igraph_error_t igraph_layout_fruchterman_reingold(const igraph_t *graph,
                                       igraph_matrix_t *res,
                                       igraph_bool_t use_seed,
                                       igraph_integer_t niter,
                                       igraph_real_t start_temp,
                                       igraph_layout_grid_t grid,
                                       const igraph_vector_t *weights,
                                       const igraph_vector_t *minx,
                                       const igraph_vector_t *maxx,
                                       const igraph_vector_t *miny,
                                       const igraph_vector_t *maxy);

这是一种力导向布局，它模拟连接的顶点对之间的吸引力 f_a 和所有顶点对之间的排斥力 f_r。力计算为两个顶点之间的距离 d 的函数，如下所示

f_a(d) = -w * d^2 和 f_r(d) = 1/d,

其中 w 表示边的权重。因此，两个连接顶点的平衡距离为 1/w^3，假设没有其他力作用于它们。

在断开连接的图中，igraph 有效地在所有顶点对之间插入一个权重为 n^(-3/2) 的弱连接，其中 n 是顶点计数。这确保了组件彼此靠近。

参考

Fruchterman, T.M.J. and Reingold, E.M.: Graph Drawing by Force-directed Placement. Software -- Practice and Experience, 21/11, 1129--1164, 1991. https://doi.org/10.1002/spe.4380211102

参数： 

图:

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

res:

指向已初始化矩阵对象的指针。这将包含结果，并将根据需要调整大小。

use_seed:

如果为真，则使用 res 参数中提供的值作为初始布局，如果为假，则使用随机初始布局。

niter:

要进行的迭代次数。一个合理的默认值为 500。

start_temp:

起始温度。这是对于一个顶点，在一个步骤中，沿一个轴允许的最大移动量。目前，它在迭代期间线性地减小到零。

grid:

是否使用算法的（快速但不太准确的）基于网格的版本。可能的值：IGRAPH_LAYOUT_GRID、IGRAPH_LAYOUT_NOGRID、IGRAPH_LAYOUT_AUTOGRID。最后一个仅对大型图使用基于网格的版本，目前是具有超过 1000 个顶点的图。

weights:

指向包含边权重的向量的指针。权重必须为正。如果 NULL，则假定所有边的权重为 1。沿边的吸引力将乘以权重，导致通过高权重边连接的顶点彼此更靠近。

minx:

指向向量的指针，或一个 NULL 指针。如果不为 NULL 指针，则该向量给出每个顶点的最小 “x” 坐标。

maxx:

与 minx 相同，但最大 “x” 坐标。

miny:

指向向量的指针，或一个 NULL 指针。如果不为 NULL 指针，则该向量给出每个顶点的最小 “y” 坐标。

maxy:

与 miny 相同，但最大 “y” 坐标。

返回值： 

错误代码。

时间复杂度：每次迭代 O(|V|^2)，|V| 是图中顶点的数量。

1.9. igraph_layout_kamada_kawai — 根据 Kamada-Kawai 算法将顶点放置在平面上。

igraph_error_t igraph_layout_kamada_kawai(const igraph_t *graph, igraph_matrix_t *res,
                               igraph_bool_t use_seed, igraph_integer_t maxiter,
                               igraph_real_t epsilon, igraph_real_t kkconst,
                               const igraph_vector_t *weights,
                               const igraph_vector_t *minx, const igraph_vector_t *maxx,
                               const igraph_vector_t *miny, const igraph_vector_t *maxy);

这是一种力导向布局。在所有顶点对之间插入一个弹簧，包括那些直接连接的和那些没有直接连接的。弹簧的未拉伸长度是根据相应顶点对之间的无向图距离选择的。因此，在加权图中，增加两个顶点之间的权重会使它们分开。弹簧的杨氏模量与图距离成反比，确保了远距离顶点之间的弹簧对布局的影响较小。

断开连接的图通过假设不同组件中顶点之间的图距离与图直径相同来处理。

此布局特别适用于局部连接的空间网络，例如网格。

此布局算法不适用于大型图。内存要求是 O(|V|^2) 的量级。

参考

Kamada, T. and Kawai, S.: An Algorithm for Drawing General Undirected Graphs. Information Processing Letters, 31/1, 7--15, 1989. https://doi.org/10.1016/0020-0190(89)90102-6

参数： 

图:

一个图对象。

res:

指向已初始化矩阵对象的指针。这将包含结果（第零列中的 x 位置和第一列中的 y 位置），并且将根据需要调整大小。

use_seed:

布尔值，是否使用 res 参数中提供的值作为初始配置。如果为零并且对 X 或 Y 坐标有任何限制，则使用随机初始配置。否则，顶点将放置在半径为 1 的圆上作为初始配置。

maxiter:

要执行的最大迭代次数。一个合理的默认值是顶点数量的至少十倍（或更多）。

epsilon:

如果算法的最大增量值小于 still，则停止迭代。可以安全地将其保留为零，然后执行 maxiter 迭代。

kkconst:

Kamada-Kawai 顶点吸引力常数。典型值：顶点数。

weights:

一个边权重向量。在 Kamada-Kawai 算法使用的最短路径计算中，权重被解释为边长度。因此，由高权重边连接的顶点将被放置得更远。传递 NULL 以假设所有边的单位权重。

minx:

指向向量的指针，或一个 NULL 指针。如果不为 NULL 指针，则该向量给出每个顶点的最小 “x” 坐标。

maxx:

与 minx 相同，但最大 “x” 坐标。

miny:

指向向量的指针，或一个 NULL 指针。如果不为 NULL 指针，则该向量给出每个顶点的最小 “y” 坐标。

maxy:

与 miny 相同，但最大 “y” 坐标。

返回值： 

错误代码。

时间复杂度：每次迭代 O(|V|)，在 O(|V|^2 log|V|) 初始化步骤之后。 |V| 是图中顶点的数量。

1.10. igraph_layout_gem — 根据 GEM 算法布局图。

igraph_error_t igraph_layout_gem(const igraph_t *graph, igraph_matrix_t *res,
                      igraph_bool_t use_seed, igraph_integer_t maxiter,
                      igraph_real_t temp_max, igraph_real_t temp_min,
                      igraph_real_t temp_init);

GEM 布局算法，如 Arne Frick, Andreas Ludwig, Heiko Mehldau: A Fast Adaptive Layout Algorithm for Undirected Graphs, Proc. Graph Drawing 1994, LNCS 894, pp. 388-403, 1995 中所述。

参数： 

图:

输入图。在有向图中，边方向被忽略。

res:

结果存储在此处。如果 use_seed 参数为真，则此矩阵也用作算法的起点。

use_seed:

布尔值，是否使用 res 中提供的坐标作为起点。如果为假（零），则使用均匀随机起点。

maxiter:

要执行的最大迭代次数。更新单个顶点算作一次迭代。一个合理的默认值是 40 * n * n，其中 n 是顶点数。原始论文建议 4 * n * n，但这通常只有在仔细设置其他参数时才有效。

temp_max:

允许的最大局部温度。一个合理的默认值是顶点数。

temp_min:

算法终止时的全局温度（甚至在达到 maxiter 迭代之前）。一个合理的默认值是 1/10。

temp_init:

所有顶点的初始局部温度。一个合理的默认值是顶点数的平方根。

返回值： 

错误代码。

时间复杂度：O(t * n * (n+e))，其中 n 是顶点数，e 是边数，t 是执行的时间步数。

1.11. igraph_layout_davidson_harel — Davidson-Harel 布局算法。

igraph_error_t igraph_layout_davidson_harel(const igraph_t *graph, igraph_matrix_t *res,
                                 igraph_bool_t use_seed, igraph_integer_t maxiter,
                                 igraph_integer_t fineiter, igraph_real_t cool_fact,
                                 igraph_real_t weight_node_dist, igraph_real_t weight_border,
                                 igraph_real_t weight_edge_lengths,
                                 igraph_real_t weight_edge_crossings,
                                 igraph_real_t weight_node_edge_dist);

此函数实现 Davidson 和 Harel 的算法，请参见 Ron Davidson, David Harel: Drawing Graphs Nicely Using Simulated Annealing. ACM Transactions on Graphics 15(4), pp. 301-331, 1996. https://doi.org/10.1145/234535.234538

该算法使用模拟退火和一个复杂的能量函数，不幸的是，该能量函数很难为不同的图设置参数。原始出版物没有披露任何参数值，下面的值是通过实验确定的。

该算法由两个阶段组成，一个退火阶段和一个微调阶段。第二阶段没有模拟退火。

我们的实现尝试尽可能地遵循原始出版物。唯一的主要区别是坐标被明确地保持在布局矩形的边界内。

参数： 

图:

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

res:

一个矩阵，结果存储在此处。它可以用于提供起始坐标，请参见 use_seed。

use_seed:

布尔值，是否使用提供的 res 作为起始坐标。

maxiter:

退火的最大迭代次数。对于较小的图，一个合理的值是 10。

fineiter:

微调迭代次数。一个合理的值是 max(10, log2(n))，其中 n 是顶点数。

cool_fact:

冷却因子。一个合理的值是 0.75。

weight_node_dist:

能量函数的节点-节点距离分量的权重。合理值：1.0。

weight_border:

能量函数的距离边框分量的权重。如果允许顶点位于边框上，则可以将其设置为零。

weight_edge_lengths:

能量函数的边长度分量的权重，一个合理的值是图的密度除以 10。

weight_edge_crossings:

能量函数的边交叉分量的权重，一个合理的默认值是 1 减去图密度的平方根。

weight_node_edge_dist:

能量函数的节点-边距离分量的权重。一个合理的值是 1 减去密度，除以 5。

返回值： 

错误代码。

时间复杂度：一个第一阶段迭代的时间复杂度为 O(n^2+m^2)，一个微调迭代的时间复杂度为 O(mn)。如果能量函数的一些分量的权重设置为零，则时间复杂度可能会更小。

1.12. igraph_layout_mds — 使用多维缩放将顶点放置在平面上。

igraph_error_t igraph_layout_mds(const igraph_t *graph, igraph_matrix_t *res,
                      const igraph_matrix_t *dist, igraph_integer_t dim);

此布局需要一个距离矩阵，其中行 i 和列 j 的交集指定顶点 i 和顶点 j 之间的期望距离。该算法将尝试将顶点放置在具有给定维度数的空间中，其方式是近似距离矩阵中规定的距离关系。 igraph 使用 Torgerson 的经典多维缩放；有关更多详细信息，请参见 Cox & Cox: Multidimensional Scaling (1994), Chapman and Hall, London。

如果输入图断开连接，igraph 将首先将其分解为子图，使用距离矩阵的相应子矩阵逐个布局子图，然后使用 igraph_layout_merge_dla 合并布局。由于 igraph_layout_merge_dla 仅适用于 2D 布局，因此您无法在断开连接的图上运行多于两个维度的 MDS 布局。

警告：如果图对于两个顶点的交换是对称的（就像连接到同一父节点的树的叶子一样），则经典多维缩放可能会为这些顶点分配相同的坐标。

参数： 

图:

一个图对象。

res:

指向已初始化矩阵对象的指针。这将包含结果，并将根据需要调整大小。

dist:

距离矩阵。它必须是对称的，并且此函数不检查矩阵是否确实对称。如果您在此处传递非对称矩阵，则结果未指定。您可以将此参数设置为 null；在这种情况下，顶点之间的无向最短路径长度将用作距离。

dim:

嵌入空间中的维度数。对于 2D 布局，请在此处提供 2。

返回值： 

错误代码。

在 0.6 版本中添加。

时间复杂度：通常约为 O(|V|^2 dim)。

1.13. igraph_layout_lgl — 用于大型图的基于力的布局算法。

igraph_error_t igraph_layout_lgl(const igraph_t *graph, igraph_matrix_t *res,
                      igraph_integer_t maxit, igraph_real_t maxdelta,
                      igraph_real_t area, igraph_real_t coolexp,
                      igraph_real_t repulserad, igraph_real_t cellsize,
                      igraph_integer_t proot);

这是一个类似于 Large Graph Layout 算法和程序的布局生成器 (http://lgl.sourceforge.net/)。但与 LGL 不同的是，此版本使用 Fruchterman-Reingold 风格的模拟退火算法来放置顶点。通过将顶点放置在网格上，并且仅计算距离小于限制的顶点之间的斥力，从而实现加速。

参数： 

图:

要放置的（已初始化）图对象。它必须是连通的；算法不处理非连通图。

res:

指向已初始化矩阵对象的指针，用于保存结果。如果需要，将调整大小。

maxit:

为每个布局步骤执行的最大冷却迭代次数。一个合理的默认值为 150。

maxdelta:

单次迭代中顶点允许移动的最大长度。一个合理的默认值是顶点数。

area:

此参数给出顶点将放置在其上的正方形的面积。一个合理的默认值是顶点数的平方。

coolexp:

冷却指数。一个合理的默认值为 1.5。

repulserad:

确定顶点-顶点斥力抵消相邻顶点吸引力的半径。一个合理的默认值是 area 乘以顶点数。

cellsize:

网格单元的大小，正方形的一条边。一个合理的默认值是 area 的四次方根（如果 area 也保留其默认值，则为顶点数的平方根）。

proot:

根顶点，这是第一个放置的顶点，其邻居在第一次迭代中放置，第二个邻居在第二次迭代中放置，等等。如果为负数，则选择一个随机顶点。

返回值： 

错误代码。

在 0.2 版本中添加。

时间复杂度：理想情况下为 O(dia*maxit*(|V|+|E|))，|V| 是顶点数，dia 是图的直径，最坏情况下的复杂度仍然是 O(dia*maxit*(|V|^2+|E|))，这种情况发生在所有顶点恰好都在同一个网格单元中。

2. 树和非循环图的布局

2.1. igraph_layout_reingold_tilford — 用于树图的 Reingold-Tilford 布局。
2.2. igraph_layout_reingold_tilford_circular — 用于树的圆形 Reingold-Tilford 布局。
2.3. igraph_roots_for_tree_layout — 适用于良好树布局的根。
2.4. igraph_layout_sugiyama — 用于分层有向无环图的 Sugiyama 布局算法。
2.5. igraph_layout_umap — 使用 Uniform Manifold Approximation and Projection (UMAP) 的布局。
2.6. igraph_layout_umap_compute_weights — 从距离开始计算 UMAP 布局的权重。

2.1. igraph_layout_reingold_tilford — 用于树图的 Reingold-Tilford 布局。

igraph_error_t igraph_layout_reingold_tilford(const igraph_t *graph,
                                   igraph_matrix_t *res,
                                   igraph_neimode_t mode,
                                   const igraph_vector_int_t *roots,
                                   const igraph_vector_int_t *rootlevel);

在树中排列节点，其中给定节点用作根。树向下定向，父节点位于其子节点的上方居中。有关确切的算法，请参见

Reingold, E and Tilford, J: Tidier drawing of trees. IEEE Trans. Softw. Eng., SE-7(2):223--228, 1981. https://doi.org/10.1109/TSE.1981.234519

如果给定的图不是树，则首先执行广度优先搜索以获得可能的生成树。

参数： 

图:

图对象。

res:

结果，矩阵中的坐标。该参数应指向一个已初始化的矩阵对象，并将调整大小。

模式:

指定构建树时要考虑哪些边。如果它是 IGRAPH_OUT，则仅考虑父节点的传出边，如果它是 IGRAPH_IN，则仅考虑传入边。如果它是 IGRAPH_ALL，则使用所有边（这是 igraph 0.5 及更早版本中的行为）。如果未给出根顶点，则此参数还会影响根顶点的计算方式。请参阅 roots 参数。

roots:

根顶点或根顶点的索引。应该指定根集，以便可以从它们访问图的所有顶点。简而言之，在无向情况下，应从每个连通分量中给出一个根。如果 roots 是 NULL 或指向空向量的指针，则将自动选择根。当前，自动根选择在顶点少于 500 的图中优先选择低偏心率顶点，而在更大的图中优先选择高次顶点（根据 mode）。根选择启发式方法可能会在不另行通知的情况下更改。为了确保一致的输出，请手动指定根。igraph_roots_for_tree_layout() 函数可以更好地控制自动根选择。

rootlevel:

绘制非树森林（即它们是不连通的并且具有树组件）时，此参数可能很有用。它指定森林中每棵树的根顶点的级别。仅当它不是空指针且还给出了 roots 参数（并且它不是空指针或空向量）时才会被考虑。

返回值： 

错误代码。

在 0.2 版本中添加。

另请参阅： 

igraph_layout_reingold_tilford_circular(), igraph_roots_for_tree_layout()

示例 20.1.  文件 examples/simple/igraph_layout_reingold_tilford.c

#include <igraph.h>
#include <math.h>

int main(void) {

    igraph_t g;
    FILE *f;
    igraph_matrix_t coords;
    /* igraph_integer_t i, n; */

    f = fopen("igraph_layout_reingold_tilford.in", "r");
    igraph_read_graph_edgelist(&g, f, 0, IGRAPH_DIRECTED);
    igraph_matrix_init(&coords, 0, 0);
    igraph_layout_reingold_tilford(&g, &coords, IGRAPH_IN, 0, 0);

    /*n=igraph_vcount(&g);
    for (i=0; i<n; i++) {
      printf("%6.3f %6.3f\n", MATRIX(coords, i, 0), MATRIX(coords, i, 1));
    }*/

    igraph_matrix_destroy(&coords);
    igraph_destroy(&g);
    return 0;
}


2.2. igraph_layout_reingold_tilford_circular — 用于树的圆形 Reingold-Tilford 布局。

igraph_error_t igraph_layout_reingold_tilford_circular(const igraph_t *graph,
        igraph_matrix_t *res,
        igraph_neimode_t mode,
        const igraph_vector_int_t *roots,
        const igraph_vector_int_t *rootlevel);

此布局与 igraph_layout_reingold_tilford() 几乎相同，但树以圆形方式绘制，根顶点位于中心。

参数： 

图:

图对象。

res:

结果，矩阵中的坐标。该参数应指向一个已初始化的矩阵对象，并将调整大小。

模式:

指定构建树时要考虑哪些边。如果它是 IGRAPH_OUT，则仅考虑父节点的传出边，如果它是 IGRAPH_IN，则仅考虑传入边。如果它是 IGRAPH_ALL，则使用所有边（这是 igraph 0.5 及更早版本中的行为）。如果未给出根顶点，则此参数还会影响根顶点的计算方式。请参阅 roots 参数。

roots:

根顶点或根顶点的索引。应该指定根集，以便可以从它们访问图的所有顶点。简而言之，在无向情况下，应从每个连通分量中给出一个根。如果 roots 是 NULL 或指向空向量的指针，则将自动选择根。当前，自动根选择在顶点少于 500 的图中优先选择低偏心率顶点，而在更大的图中优先选择高次顶点（根据 mode）。根选择启发式方法可能会在不另行通知的情况下更改。为了确保一致的输出，请手动指定根。

rootlevel:

绘制非树森林（即它们是不连通的并且具有树组件）时，此参数可能很有用。它指定森林中每棵树的根顶点的级别。仅当它不是空指针且还给出了 roots 参数（并且它不是空指针或空向量）时才会被考虑。

返回值： 

错误代码。

另请参阅： 

igraph_layout_reingold_tilford().

2.3. igraph_roots_for_tree_layout — 适用于良好树布局的根。

igraph_error_t igraph_roots_for_tree_layout(
        const igraph_t *graph,
        igraph_neimode_t mode,
        igraph_vector_int_t *roots,
        igraph_root_choice_t heuristic);

此函数选择一个根或一组根，适合于可视化树或类似树的图。它通常与 igraph_layout_reingold_tilford() 一起使用。原理是选择最小的根集，以便所有其他顶点都可以从它们访问。

在无向情况下，从每个连通分量中选择一个根。在有向情况下，从每个没有传入（或传出）边的强连通分量中选择一个根（取决于 'mode'）。当有多个根选择可能时，顶点会根据给定的 heuristic 进行优先级排序。

参数： 

图:

图，通常是树，但接受任何图。

模式:

是否将输入解释为无向图、有向外树或内树。

roots:

已初始化的整数向量，根将在此处返回。

heuristic:

当有多个根选择可能时，用于打破平局的启发式方法。

IGRAPH_ROOT_CHOICE_DEGREE

选择具有最高度数（有向模式下的出度或入度）的顶点。即使在大型图中，这种简单的启发式方法也很快。

IGRAPH_ROOT_CHOICE_ECCENTRICITY

选择具有最低偏心率的顶点。这通常会导致“宽而浅”的树布局。虽然这种启发式方法产生高质量的结果，但对于大型图来说速度很慢：计算偏心率在顶点数中具有二次复杂度。

返回值： 

错误代码。

时间复杂度：取决于启发式方法。

2.4. igraph_layout_sugiyama — 用于分层有向无环图的 Sugiyama 布局算法。

igraph_error_t igraph_layout_sugiyama(const igraph_t *graph, igraph_matrix_t *res,
                           igraph_t *extd_graph, igraph_vector_int_t *extd_to_orig_eids,
                           const igraph_vector_int_t* layers, igraph_real_t hgap, igraph_real_t vgap,
                           igraph_integer_t maxiter, const igraph_vector_t *weights);

此布局算法专为有向无环图设计，其中每个顶点都分配到一个层。层从零开始索引，同一层的顶点将放置在同一条水平线上。每个图层中顶点的 X 坐标由 Sugiyama 等人提出的启发式方法决定，以最大限度地减少边交叉。

您也可以尝试使用此算法来布局无向图、包含循环的图或没有先验分层分配的图。igraph 将尝试消除循环并将顶点分配到图层，但不保证在这些情况下的布局质量。

Sugiyama 布局可能会在边上引入“弯曲”，以获得视觉上更令人愉悦的布局。这是通过向跨越多个图层的边添加虚拟节点来实现的。生成的布局不仅将坐标分配给原始图的节点，还分配给虚拟节点。布局算法还将返回带有虚拟节点的扩展图。原始图中的边可以映射到扩展图中的单条边，也可以映射到以原始源顶点和目标顶点开始和结束并经过多个虚拟顶点的路径。在这种情况下，用户还可以请求将扩展图的边映射回原始图的边。

有关更多详细信息，请参见 K. Sugiyama, S. Tagawa and M. Toda, "Methods for Visual Understanding of Hierarchical Systems". IEEE Transactions on Systems, Man and Cybernetics 11(2):109-125, 1981.

参数： 

图:

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

res:

指向已初始化矩阵对象的指针。这将包含结果并将根据需要调整大小。布局的前 |V| 行将包含原始图的坐标，其余行包含虚拟节点的位置。因此，您可以将结果与 graph 或 extended_graph 一起使用。

extended_graph:

指向未初始化图对象或 NULL 的指针。带有添加的虚拟节点的扩展图将在此处返回。在此图中，每条边都指向下层，跨越一个图层，并且前 |V| 个顶点与原始图的顶点重合。

extd_to_orig_eids:

指向向量或 NULL 的指针。如果不是 NULL，则扩展图的边 ID 到原始图的边 ID 的映射将存储在此处。

layers:

每个顶点的图层索引，如果图层应由 igraph 自动确定，则为 NULL。

hgap:

同一图层中顶点之间首选的最小水平间隙。

vgap:

图层之间的距离。

maxiter:

交叉最小化阶段的最大迭代次数。 100 是一个合理的默认值；如果您觉得边的交叉太多，请增加此值。

weights:

边的权重。这些仅在图包含循环时使用；igraph 将倾向于在打破循环时反转具有较小权重的边。

2.5. igraph_layout_umap — 使用 Uniform Manifold Approximation and Projection (UMAP) 的布局。

igraph_error_t igraph_layout_umap(const igraph_t *graph,
                                  igraph_matrix_t *res,
                                  igraph_bool_t use_seed,
                                  const igraph_vector_t *distances,
                                  igraph_real_t min_dist,
                                  igraph_integer_t epochs,
                                  igraph_bool_t distances_are_weights);

警告

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

UMAP 主要用于将高维向量嵌入到低维空间（最常见的是 2D）中。该算法是概率性的并引入非线性，不像例如 PCA，并且类似于 T-distributed Stochastic Neighbor Embedding (t-SNE)。非线性有助于将非常相似的向量“聚类”在一起，而不会对嵌入空间施加全局几何形状（例如，PCA 中的刚性旋转 + 压缩）。UMAP 使用图作为中间数据结构，因此也可以用作图布局算法。

一般的 UMAP 工作流程是从向量开始，计算一个稀疏距离图，该图仅包含相似点之间的边（例如，k 最近邻图），然后将这些距离转换为 0 和 1 之间的指数衰减权重，对于距离图中最近邻的点，权重更大。如果使用没有任何与边关联的距离的图，则所有权重都将设置为 1。

如果您尝试使用此函数来嵌入高维向量，您应该首先计算向量之间的 k 最近邻图并计算关联的距离，然后在该图上调用此函数。如果您已经有一个距离图，或者您有一个没有距离的图，您可以直接调用此函数。如果您已经有一个与每条边关联的有意义权重的图，您也可以调用此函数，但将参数 distances_are_weights 设置为 true。要从距离计算权重而不计算布局，请参阅 igraph_layout_umap_compute_weights()。

参考

Leland McInnes, John Healy, and James Melville: UMAP: Uniform Manifold Approximation and Projection for Dimension Reduction (2020) https://arxiv.org/abs/1802.03426

参数： 

图:

指向要为其查找布局（即嵌入）的图的指针。这通常是一个稀疏图，仅存储最短距离的边，例如 k 最近邻图。

res:

指向将存储布局坐标的 n x 2 矩阵的指针。

use_seed:

如果 true，则 res 参数中提供的值用作初始布局，如果 false，则使用随机初始布局。

distances:

指向与图边关联的距离向量的指针。如果此参数是 NULL，则所有权重都将设置为 1。

min_dist:

一个 fudge 参数，用于决定两个未连接的顶点在嵌入中可以有多近才会感受到排斥力。它不能为负数。典型值介于 0 和 1 之间。

epochs:

交叉熵上的主随机梯度下降循环的迭代次数。典型值介于 30 和 500 之间。

distances_are_weights:

是否使用预先计算的权重。如果为 true，则 distances 向量包含预先计算的权重。如果 false（典型用例），此函数将从距离计算权重，然后使用它们来计算布局。

返回值： 

错误代码。

另请参阅： 

igraph_layout_umap_3d()

2.6. igraph_layout_umap_compute_weights — 从距离开始计算 UMAP 布局的权重。

igraph_error_t igraph_layout_umap_compute_weights(
        const igraph_t *graph,
        const igraph_vector_t *distances,
        igraph_vector_t *weights);

警告

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

UMAP 用于将高维向量嵌入到低维空间（最常见的是 2D）中。它使用距离图作为中间数据结构，使其也成为一种有用的图布局算法。有关更多信息，请参见 igraph_layout_umap()。

UMAP 的早期步骤是从距离图计算指数衰减“权重”。连通性也可以被视为量化两个顶点之间相似性的边权重。此函数从距离图计算权重。要从预先计算的权重计算布局，请调用 igraph_layout_umap()，并将 distances_are_weights 参数设置为 true。

虽然距离图可以是有向的（例如，在 k 最近邻中，很清楚您是谁的邻居），但权重通常是无向的。每当两个顶点在距离图中双重连接时，生成的权重 W 设置为

W = W1 + W2 - W1 * W2 因为 UMAP 权重被解释为概率，这只是任一边存在的概率，没有重复计算。在原始 UMAP 实现中，它被称为“模糊并集”，并且是默认值。也可以要求两条边都存在，即 W = W1 * W2：这将表示模糊交集，并且未在 igraph 中实现。作为这种对称化的结果，信息丢失，即需要比距离更少的权重。为了保持效率，这里我们将两条边之一的权重设置为如上，而将其反向边的权重设置为 0，以便稍后在 UMAP 梯度下降中跳过它。

技术说明：对于每个顶点，此函数计算其比例因子 (sigma)、其连通性校正 (rho) 以及最终权重本身。

参考

Leland McInnes, John Healy, and James Melville: UMAP: Uniform Manifold Approximation and Projection for Dimension Reduction (2020) https://arxiv.org/abs/1802.03426

参数： 

图:

指向距离图的指针。这可以是有向的（例如，将每个顶点连接到其在 k 最近邻中的邻居）或无向的，但必须没有循环或并行边。唯一的例外是：如果图是有向的，则接受具有相反方向的边对。

distances:

指向带有与每条边关联的顶点到顶点距离的向量的指针。此参数可以为 NULL，在这种情况下，假定所有边都具有相同的距离。

weights:

指向将在其中存储结果的已初始化向量的指针。如果输入图是有向的，则权重表示包含较少信息的对称化版本。因此，每当在输入图中存在相同顶点之间且方向相反的两条边时，仅设置其中一个权重，而将另一个权重固定为零。该格式被 igraph_layout_umap() 接受，它跳过布局优化中的所有零权重边。

返回值： 

错误代码。

另请参阅： 

igraph_layout_umap(), igraph_layout_umap_3d()

3. 3D 布局生成器

3.1. igraph_layout_random_3d — 将顶点均匀随机地放置在一个立方体中。
3.2. igraph_layout_sphere — 将顶点（或多或少）均匀地放置在一个球体上。
3.3. igraph_layout_grid_3d — 将顶点放置在 3D 空间中的规则网格上。
3.4. igraph_layout_fruchterman_reingold_3d — 3D Fruchterman-Reingold 算法。
3.5. igraph_layout_kamada_kawai_3d — Kamada-Kawai 布局生成器的 3D 版本。
3.6. igraph_layout_umap_3d — 使用 UMAP 的 3D 布局。

3.1. igraph_layout_random_3d — 将顶点均匀随机地放置在一个立方体中。

igraph_error_t igraph_layout_random_3d(const igraph_t *graph, igraph_matrix_t *res);

顶点坐标范围从 -1 到 1，并放置在矩阵的 3 列中，每行一个顶点。

参数： 

图:

要放置的图。

res:

指向已初始化矩阵对象的指针。它将被调整大小以保存结果。

返回值： 

错误代码。当前实现始终返回成功。

在 0.2 版本中添加。

时间复杂度：O(|V|)，顶点的数量。

3.2. igraph_layout_sphere — 将顶点（或多或少）均匀地放置在一个球体上。

igraph_error_t igraph_layout_sphere(const igraph_t *graph, igraph_matrix_t *res);

顶点以近似相等的间距放置在环绕球体的螺旋线上，按照其顶点 ID 的顺序排列。具有连续顶点 ID 的顶点彼此靠近放置。

该算法在以下论文中描述

Distributing many points on a sphere by E.B. Saff and A.B.J. Kuijlaars, Mathematical Intelligencer 19.1 (1997) 5--11. https://doi.org/10.1007/BF03024331

参数： 

图:

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

res:

指向已初始化矩阵对象的指针。这将包含结果，并将根据需要调整大小。

返回值： 

错误代码。当前实现始终返回成功。

在 0.2 版本中添加。

时间复杂度：O(|V|)，图中顶点的数量。

3.3. igraph_layout_grid_3d — 将顶点放置在 3D 空间中的规则网格上。

igraph_error_t igraph_layout_grid_3d(const igraph_t *graph, igraph_matrix_t *res,
                          igraph_integer_t width, igraph_integer_t height);

参数： 

图:

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

res:

指向已初始化矩阵对象的指针。这将包含结果，并将根据需要调整大小。

width:

网格单行中的顶点数。当为零或负数时，宽度会自动确定。

height:

网格单列中的顶点数。当为零或负数时，高度会自动确定。

返回值： 

错误代码。当前实现始终返回成功。

时间复杂度：O(|V|)，顶点的数量。

3.4. igraph_layout_fruchterman_reingold_3d — 3D Fruchterman-Reingold 算法。

igraph_error_t igraph_layout_fruchterman_reingold_3d(const igraph_t *graph,
        igraph_matrix_t *res,
        igraph_bool_t use_seed,
        igraph_integer_t niter,
        igraph_real_t start_temp,
        const igraph_vector_t *weights,
        const igraph_vector_t *minx,
        const igraph_vector_t *maxx,
        const igraph_vector_t *miny,
        const igraph_vector_t *maxy,
        const igraph_vector_t *minz,
        const igraph_vector_t *maxz);

这是基于力的 Fruchterman-Reingold 布局的 3D 版本。有关 2D 版本，请参见 igraph_layout_fruchterman_reingold()。

参数： 

图:

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

res:

指向已初始化矩阵对象的指针。这将包含结果，并将根据需要调整大小。

use_seed:

如果为真，则使用 res 参数中提供的值作为初始布局，如果为假，则使用随机初始布局。

niter:

要进行的迭代次数。一个合理的默认值为 500。

start_temp:

起始温度。这是对于一个顶点，在一步之内，允许沿一个轴移动的最大量。目前，在迭代期间，它线性减少到零。

weights:

指向包含边权重的向量的指针。权重必须为正。如果 NULL，则假定所有边的权重为 1。沿边的吸引力将乘以权重，导致通过高权重边连接的顶点彼此更靠近。

minx:

指向向量的指针，或一个 NULL 指针。如果不为 NULL 指针，则该向量给出每个顶点的最小 “x” 坐标。

maxx:

与 minx 相同，但最大 “x” 坐标。

miny:

指向向量的指针，或一个 NULL 指针。如果不为 NULL 指针，则该向量给出每个顶点的最小 “y” 坐标。

maxy:

与 miny 相同，但最大 “y” 坐标。

minz:

指向向量或 NULL 指针的指针。如果不是 NULL 指针，则向量给出每个顶点的最小“z”坐标。

maxz:

与 minz 相同，但是最大“z”坐标。

返回值： 

错误代码。

在 0.2 版本中添加。

时间复杂度：每次迭代 O(|V|^2)，|V| 是图中顶点的数量。

3.5. igraph_layout_kamada_kawai_3d — Kamada-Kawai 布局生成器的 3D 版本。

igraph_error_t igraph_layout_kamada_kawai_3d(const igraph_t *graph, igraph_matrix_t *res,
                                  igraph_bool_t use_seed, igraph_integer_t maxiter,
                                  igraph_real_t epsilon, igraph_real_t kkconst,
                                  const igraph_vector_t *weights,
                                  const igraph_vector_t *minx, const igraph_vector_t *maxx,
                                  const igraph_vector_t *miny, const igraph_vector_t *maxy,
                                  const igraph_vector_t *minz, const igraph_vector_t *maxz);

这是 igraph_layout_kamada_kawai() 的 3D 版本。有关更多信息，请参见该函数的文档。

此布局算法不适用于大型图。内存要求是 O(|V|^2) 的量级。

参数： 

图:

一个图对象。

res:

指向已初始化矩阵对象的指针。这将包含结果（x-、y- 和 z- 位置在第一到三列中），并且如果需要，将调整大小。

use_seed:

布尔值，是否使用 res 参数中提供的值作为初始配置。如果为零并且对 z、y 或 z 坐标有任何限制，则使用随机初始配置。否则，顶点将均匀地放置在半径为 1 的球体上作为初始配置。

maxiter:

要执行的最大迭代次数。一个合理的默认值是顶点数量的至少十倍（或更多）。

epsilon:

如果算法的最大增量值小于 still，则停止迭代。可以安全地将其保留为零，然后执行 maxiter 迭代。

kkconst:

Kamada-Kawai 顶点吸引力常数。典型值：顶点数。

weights:

一个边权重向量。在 Kamada-Kawai 算法使用的最短路径计算中，权重被解释为边长度。因此，由高权重边连接的顶点将被放置得更远。传递 NULL 以假设所有边的单位权重。

minx:

指向向量的指针，或一个 NULL 指针。如果不为 NULL 指针，则该向量给出每个顶点的最小 “x” 坐标。

maxx:

与 minx 相同，但最大 “x” 坐标。

miny:

指向向量的指针，或一个 NULL 指针。如果不为 NULL 指针，则该向量给出每个顶点的最小 “y” 坐标。

maxy:

与 miny 相同，但最大 “y” 坐标。

minz:

指向向量或 NULL 指针的指针。如果不是 NULL 指针，则向量给出每个顶点的最小“z”坐标。

maxz:

与 minz 相同，但是最大“z”坐标。

返回值： 

错误代码。

时间复杂度：每次迭代 O(|V|)，在 O(|V|^2 log|V|) 初始化步骤之后。 |V| 是图中顶点的数量。

3.6. igraph_layout_umap_3d — 使用 UMAP 的 3D 布局。

igraph_error_t igraph_layout_umap_3d(const igraph_t *graph,
                                     igraph_matrix_t *res,
                                     igraph_bool_t use_seed,
                                     const igraph_vector_t *distances,
                                     igraph_real_t min_dist,
                                     igraph_integer_t epochs,
                                     igraph_bool_t distances_are_weights);

警告

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

这是 UMAP 算法的 3D 版本（有关 2D 版本，请参见 igraph_layout_umap()）。

参数： 

图:

指向要为其查找布局（即嵌入）的图的指针。这通常是一个有向的稀疏图，仅存储最短距离的边，例如从每个焦点顶点到其邻居的边的 k 最近邻图。但是，它也可以是一个无向图。如果 distances_are_weights 是 true，则将其视为无向图。

res:

指向将存储布局坐标的 n x 3 矩阵的指针。

use_seed:

如果为真，则使用 res 参数中提供的值作为初始布局，如果为假，则使用随机初始布局。

distances:

指向与图边关联的距离向量的指针。如果此参数是 NULL，则假定所有边都具有相同的距离。

min_dist:

一个 fudge 参数，用于决定两个未连接的顶点在嵌入中可以有多近才会感受到排斥力。它不能为负数。典型值介于 0 和 1 之间。

epochs:

交叉熵上的主随机梯度下降循环的迭代次数。典型值介于 30 和 500 之间。

distances_are_weights:

是否使用预先计算的权重。如果 false（典型用例），此函数将从距离计算权重，然后使用它们来计算布局。如果 true，则 distances 向量包含预先计算的权重，包括可能与布局优化无关的某些等于零的权重。

返回值： 

错误代码。

另请参阅： 

igraph_layout_umap()

4. 合并布局

4.1. igraph_layout_merge_dla — 通过使用 DLA 算法合并多个布局。

4.1. igraph_layout_merge_dla — 通过使用 DLA 算法合并多个布局。

igraph_error_t igraph_layout_merge_dla(
    const igraph_vector_ptr_t *thegraphs, const igraph_matrix_list_t *coords,
    igraph_matrix_t *res
);

警告

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

首先，每个布局都被一个圆覆盖。然后，最大图的布局放置在原点。然后，其他布局通过 DLA 算法放置，较大的布局先放置，较小的布局最后放置。

参数： 

thegraphs:

包含图对象的指针向量，将合并这些图对象的布局。

coords:

带有 thegraphs 中图的 2D 布局的矩阵列表。

res:

指向已初始化矩阵对象的指针，结果将存储在此处。如果需要，将调整大小。

返回值： 

错误代码。

在 0.2 版本中添加。

时间复杂度：待定。

← 第 19. 章 图 motif、dyad census 和 triad census 第 21. 章 从文件读取图和将图写入文件 →