【图论】Graph.jl 核心函数

核心函数

AbstractPathState

提供最短路径计算信息的抽象类型。

顶点操作函数

add_vertices!(g, n)

向图 g 中添加 n 个新顶点。返回成功添加的顶点数。

示例:

using Graphs
g = SimpleGraph()
println(g)
add_vertices!(g, 2)
println(g)

邻居查询函数

all_neighbors(g, v)

返回图 g 中顶点 v 的所有入站和出站邻居的列表。对于无向图，这等同于 outneighbors 和 inneighbors`。

实现说明: 返回当前图内部结构的引用，而非副本。请勿修改结果。

示例:

using Graphs
g = DiGraph(3)
add_edge!(g, 2, 3)
add_edge!(g, 3, 1);
println(all_neighbors(g, 1))
println(all_neighbors(g, 2))
println(all_neighbors(g, 3))

common_neighbors(g, u, v)

返回图 g 中顶点 u 和 v 的共同邻居。

实现说明: 返回当前图内部结构的引用，而非副本。请勿修改结果。

示例:

using Graphs
g = SimpleGraph(4);
add_edge!(g, 1, 2);
add_edge!(g, 2, 3);
add_edge!(g, 3, 4);
add_edge!(g, 4, 1);
add_edge!(g, 1, 3);
println(common_neighbors(g, 1, 3))
println(common_neighbors(g, 1, 4))

neighbors(g, v)

返回从图 g 中顶点 v 可到达的所有邻居的列表。对于有向图，默认值等于 outneighbors`。

实现说明: 返回当前图内部结构的引用，而非副本。请勿修改结果。

示例:

using Graphs
g = DiGraph(3);
add_edge!(g, 2, 3);
add_edge!(g, 3, 1);
println(neighbors(g, 1))
println(neighbors(g, 2))
println(neighbors(g, 3))

度计算函数

degree(g[, v])

返回一个包含图 g 中每个顶点度数的向量。对于有向图，顶点的度数等于其入度与出度之和。

• 如果 v 指定且为单个顶点，则仅返回 v 的度数
• 如果 v 指定且为顶点向量，则仅返回 v 中顶点的度数

示例:

using Graphs
g = DiGraph(3)
add_edge!(g, 2, 3)
add_edge!(g, 3, 1);
println(degree(g))
println(degree(g,[1,3]))
println(degree(g,3))

indegree(g[, v])

返回一个包含图 g 中每个顶点入度的向量。

• 如果 v 指定且为单个顶点，则仅返回 v 的入度
• 如果 v 指定且为顶点向量，则仅返回 v 中顶点的入度

示例:

using Graphs
g = DiGraph(3);
add_edge!(g, 2, 3);
add_edge!(g, 3, 1);
println(indegree(g))
println(indegree(g,[2,3]))
println(indegree(g,2))

outdegree(g[, v])

返回一个包含图 g 中每个顶点出度的向量。

• 如果 v 指定且为单个顶点，则仅返回 v 的出度
• 如果 v 指定且为顶点向量，则仅返回 v 中顶点的出度

示例:

using Graphs
g = DiGraph(3);
add_edge!(g, 2, 3);
add_edge!(g, 3, 1);
println(outdegree(g))
println(outdegree(g,[1,2]))
println(outdegree(g,2))

degree_histogram(g, degfn=degree)

返回一个 Dict，表示具有由键表示的度数的顶点的数量。可以通过覆盖 degfn 来指定度函数（例如，indegree 或 outdegree`）。

degree_histogram(g, degfn=degree)

返回一个 Dict，表示具有由键表示的度数的顶点的数量。可以通过覆盖 degfn 来指定度函数（例如，indegree 或 outdegree`）。

图特征计算函数

density(g)

返回图 g 的密度。密度定义为实际边数与可能边数之比。

has_self_loops(g)

如果图 g 存在任何自循环，则返回 true`。

示例:

using Graphs
g = SimpleGraph(2)
add_edge!(g, 1, 2)
println(has_self_loops(g))
add_edge!(g, 1, 1)
println(has_self_loops(g))

num_self_loops(g)

返回图 g 中的自循环数。

示例:

using Graphs
g = SimpleGraph(2);
add_edge!(g, 1, 2);
println(num_self_loops(g))
add_edge!(g, 1, 1);
println(num_self_loops(g))

is_ordered(e)

如果边 e 的源顶点小于或等于目标顶点，则返回 true`。

示例:

using Graphs
g = DiGraph(2);
add_edge!(g, 2, 1);
println( is_ordered(first(edges(g))))

weights(g)

以矩阵形式返回图 g 边的权重。默认为 Graphs.DefaultDistance`。

实现说明: 一般来说，引用不存在边的权重是未定义的行为。不要依赖 weights 矩阵来替代图的 adjacency_matrix`。

极值函数

noallocextreme(f, comparison, initial, g)

计算极值 [f(g,i) for i=i:nv(g)] 而不收集所有值。

Δ(g)

返回图 g 中顶点的最大度 (degree)。

Δin(g)

返回图 g 中顶点的最大入度 (indegree)。

Δout(g)

返回图 g 中顶点的最大出度 (outdegree)。

δ(g)

返回图 g 中顶点的最小度 (degree)。

δin(g)

返回图 g 中顶点的最小入度 (indegree)。

δout(g)

返回图 g 中顶点的最小出度 (outdegree)。

squash(g)

返回具有可容纳所有顶点的最小实用 eltype 的图的副本。如果 eltype 没有改变，也可能返回原始图表。