【图论】 Graph.jl 操作汇总

参考链接：
https://juliagraphs.org/Graphs.jl/stable/core_functions/operators/

图论的集合类操作

Base.getindex

方法

g[iter]

返回由 iter 诱导的子图。等价于 induced_subgraph(g, iter)[1]。

Base.intersect

方法， 边的交集

intersect(g, h)

返回一个仅包含同时存在于图 g和图 h 中的边的图。

实现说明：此函数可能生成度数为 0 的顶点。保留输入图的 eltype。

示例

using Graphs
g1 = SimpleDiGraph([0 1 0 0 0; 0 0 1 0 0; 1 0 0 1 0; 0 0 0 0 1; 0 0 0 1 0])
g2 = SimpleDiGraph([0 1 0; 0 0 1; 1 0 0])
foreach(println, edges(intersect(g1, g2)))

Base.join

方法

join(g, h)

返回一个组合图 g 和 h 的图（使用 blockdiag），然后添加 g中的顶点与 h 中的顶点之间的所有边。

实现说明：保留输入图的 eltype。如果生成的图的顶点数超出 eltype 的范围，则会报错。

示例

using Graphs
g = join(star_graph(3), path_graph(2))
println(g) # 输出: {5, 9} undirected simple Int64 graph
foreach(println, edges(g))

Base.reverse

函数 反向图

reverse(g)

返回一个有向图，其中所有边的方向都与原始有向图 g` 相反。

实现说明：保留输入图的 eltype。

示例

using Graphs
g = SimpleDiGraph([0 1 0 0 0; 0 0 1 0 0; 1 0 0 1 0; 0 0 0 0 1; 0 0 0 1 0])
foreach(println, edges(reverse(g)))

Base.reverse!

函数

reverse!(g)

有向图 g 的就地反转（修改原图）。非修改版本请参见 Base.reverse。

Base.size

方法 顶点数

size(g, i)

如果 i=1 或 i=2，则返回图 g` 的顶点数，否则返回 1。

示例

using Graphs
g = cycle_graph(4)
println(size(g, 1)) # 输出: 4
println(size(g, 2)) # 输出: 4
println(size(g, 3)) # 输出: 1

Base.sum

方法 顶点度

sum(g, i)

返回图的入度（i=1）或出度（i=2）值的向量。

示例

using Graphs
g = SimpleDiGraph([0 1 0 0 0; 0 0 1 0 0; 1 0 0 1 0; 0 0 0 0 1; 0 0 0 1 0])
println(sum(g, 2)) # 输出: [1, 1, 2, 1, 1]
println(sum(g, 1)) # 输出: [1, 1, 1, 2, 1]

Base.sum

方法 边数

sum(g)

返回图 g` 中的边数。

示例

using Graphs
g = SimpleGraph([0 1 0; 1 0 1; 0 1 0])
println(sum(g)) # 输出: 2

Base.union

方法 顶点的并，边的并

union(g, h)

通过取所有顶点和边的集合并集，返回一个组合图 g 和 h 的图。

实现说明：保留输入图的 eltype。如果生成的图的顶点数超出 eltype 的范围，则会报错。

示例

using Graphs
g = SimpleGraph(3); h = SimpleGraph(5)
add_edge!(g, 1, 2); add_edge!(g, 1, 3)
add_edge!(h, 3, 4); add_edge!(h, 3, 5); add_edge!(h, 4, 5)
f = union(g, h)
foreach(println, edges(f))

图生成与转换

Graphs.cartesian_product`

方法

cartesian_product(g, h)

返回 g 和 h 的笛卡尔积图。

实现说明：保留输入图的 eltype。如果生成的图的顶点数超出 eltype 的范围，则会报错。

示例

using Graphs
g = cartesian_product(star_graph(3), path_graph(3))
println(g) # 输出: {9, 12} undirected simple Int64 graph
foreach(println, edges(g))

Graphs.complement

方法

complement(g)

返回图 g` 的补图。

实现说明：保留输入图的 eltype。

示例

using Graphs
g = SimpleDiGraph([0 1 0 0 0; 0 0 1 0 0; 1 0 0 1 0; 0 0 0 0 1; 0 0 0 1 0])
foreach(println, edges(complement(g)))

Graphs.compute_shifts

方法

compute_shifts(n::Int, x::AbstractArray)

确定 x 中的所有元素中有多少个小于 i，i 从 1 到 n。

Graphs.crosspath

函数

crosspath(len::Integer, g::Graph)

返回一个将图 g 重复 len 次的图，并通过路径将每个顶点与其副本连接起来。

实现说明：保留输入图的 eltype。如果生成的图的顶点数超出 eltype 的范围，则会报错。

示例

using Graphs
g = crosspath(3, path_graph(3))
println(g) # 输出: {9, 12} undirected simple Int64 graph
foreach(println, edges(g))

Graphs.difference

方法

difference(g, h)

返回一个图，其边在图 g 中但不在图 h 中。

实现说明：此函数可能会生成具有 0 度顶点的图。保留输入图的 eltype。

示例

using Graphs
g1 = SimpleDiGraph([0 1 0 0 0; 0 0 1 0 0; 1 0 0 1 0; 0 0 0 0 1; 0 0 0 1 0])
g2 = SimpleDiGraph([0 1 0; 0 0 1; 1 0 0])
foreach(println, edges(difference(g1, g2)))

Graphs.egonet

方法

egonet(g, v, d, distmx=weights(g))

返回由距离顶点 v 为 d 的邻居诱导的子图，使用可选的权重 distmx（默认使用 weights(g)）。这等价于 induced_subgraph(g, neighborhood(g, v, d, dir=dir))[1]`。

可选参数

• dir=:out：如果 g 是有向图，此参数指定相对于 v 的边方向（即 :in 或 :out`）。

Graphs.induced_subgraph

方法

induced_subgraph(g, vlist)
induced_subgraph(g, elist)

返回由顶点列表 vlist 或边列表 elist 诱导的图 g 的子图，以及一个将新顶点映射回旧顶点的向量 vmap（子图中的顶点 i 对应于原始图中的顶点 vmap[i]）。

返回的图有 length(vlist) 个顶点，新顶点 i 对应于原始图中 vlist 的第 i 个顶点。

使用示例

using Graphs
g = complete_graph(10)
sg, vmap = induced_subgraph(g, 5:8)
println(nv(sg)) # 输出: 4
println(ne(sg)) # 输出: 6
println(vm[4])  # 输出: 8sg, vmap = induced_subgraph(g, [2,8,3,4])
println(sg == g[[2,8,3,4]]) # 输出: trueelist = [Edge(1,2), Edge(3,4), Edge(4,8)]
sg, vmap = induced_subgraph(g, elist)
println(sg == g[elist]) # 输出: true

Graphs.merge_vertices!

方法

merge_vertices!(g, vs)

将 vs 中指定的顶点合并为单个顶点，其索引将是 vs 中的最小值。所有连接到 vs` 中顶点的边都将连接到新的合并顶点。

返回一个向量，其中新顶点值由原始顶点索引索引。

实现说明：仅支持 SimpleGraph`。

示例

using Graphs
g = path_graph(5)
foreach(println, edges(g)) # 输出原始边
vmap = merge_vertices!(g, [2, 3])
println(vmap) # 输出新顶点映射
foreach(println, edges(g)) # 输出合并后的边

Graphs.merge_vertices

方法

merge_vertices(g::AbstractGraph, vs)

创建一个新图，其中 vs 中的所有顶点都被别名为同一个顶点 minimum(vs)。

示例

using Graphs
g = path_graph(5)
foreach(println, edges(g)) # 输出原始边
h = merge_vertices(g, [2, 3])
foreach(println, edges(h)) # 输出新图的边

Graphs.symmetric_difference

方法

symmetric_difference(g, h)

返回一个图，其边来自图 g 但不在图 h 中，或来自图 h 但不在图 g 中。

实现说明：此函数可能会生成包含 0 度顶点的图。保留输入图的 eltype。如果生成的图的顶点数超出 eltype 的范围，则会报错。

示例

using Graphs
g = SimpleGraph(3); h = SimpleGraph(3)
add_edge!(g, 1, 2)
add_edge!(h, 1, 3); add_edge!(h, 2, 3)
f = symmetric_difference(g, h)
foreach(println, edges(f))

Graphs.tensor_product

方法

tensor_product(g, h)

返回 g 和 h 的张量积图。

实现说明：保留输入图的 eltype。如果生成的图的顶点数超出 eltype 的范围，则会报错。

示例

using Graphs
g = tensor_product(star_graph(3), path_graph(3))
println(g) # 输出: {9, 8} undirected simple Int64 graph
foreach(println, edges(g))

其他函数

SparseArrays.blockdiag

方法

blockdiag(g, h)

返回一个具有 |V(g)| + |V(h)| 个顶点和 |E(g)| + |E(h)| 条边的图，其中图 h 的顶点和边附加到图 g。

实现说明：保留输入图的 eltype。如果生成的图的顶点数超出 eltype 的范围，则会报错。

示例

using Graphs
g1 = SimpleDiGraph([0 1 0 0 0; 0 0 1 0 0; 1 0 0 1 0; 0 0 0 0 1; 0 0 0 1 0])
g2 = SimpleDiGraph([0 1 0; 0 0 1; 1 0 0])
g = blockdiag(g1, g2)
println(g) # 输出: {8, 9} directed simple Int64 graph
foreach(println, edges(g))

SparseArrays.sparse

方法

sparse(g)

返回图 g` 的默认邻接矩阵。