# Graph
具备无向边的图
函数库: TyMath
# 说明
Graph 对象表示无向图，无向图具有连接相应节点的无向边。创建 Graph 对象后，您可以通过使用对象函数针对对象执行查询，了解有关图的详细信息。例如，您可以添加或删除节点或边、确定两个节点之间的最短路径，或定位特定的节点或边。
G = Graph([1,1], [2,3])
e = G.Edges
addedge!(G,2,3)
addnode!(G,4)
# 语法
G = Graph()
G = Graph(A)
G = Graph(A,nodenames)
G = Graph(A,nodenames,nodeprops)
G = Graph(A, ___; type="")
G = Graph(A, ___; omitselfloops=false)
G = Graph(s,t)
G = Graph(s,t,weights)
G = Graph(s,t,weights,nodenames)
G = Graph(s,t,weights,nodenames,nodeprops)
G = Graph(s,t,weights,nodenames,nodeprops,edgeprops)
G = Graph(s,t,weights,num)
G = Graph(s,t,___;omitselfloops=false)
# 说明
G = Graph 创建空无向图对象 G，该对象没有节点或边。示例
G = Graph(A) 使用对称邻接方阵 A 创建一个无向图。示例
对于逻辑邻接矩阵，图没有边权重。
对于非逻辑邻接矩阵，图有边权重。A 中的每个非零项的位置指定图的一条边，边的权重等于该项的值。例如，如果 A[2,1] = 10，则 G 包含一条从节点 2 到节点 1 的边，该边的权重为 10。
G = Graph(A,nodenames) 还指定节点名称。nodenames 中的元素数量必须等于 size(A,1)。 示例
G = Graph(A,nodenames,nodeprops) 使用 nodenames 指定节点名称并使用 nodeprops 指定节点属性。
G = Graph(A,___;type = "") 指定在构造图时要使用的邻接矩阵的一个三角矩阵。必须指定 A，而 nodenames 和 nodeProps 是可选的。要仅使用 A 的上或下三角矩阵构造图，type 可以是 "upper" 或 "lower"。示例
G = Graph(A,___;omitselfloops = true) 忽略 A 的对角线元素，并返回没有任何自环的图。您可以使用上述语法中的任何输入参数组合。示例
G = Graph(s,t) 以节点对组形式指定图边 (s,t)。s 和 t 可以指定节点索引或节点名称。Graph 首先按源节点、然后按目标节点对 G 中的边进行排序。示例
G = Graph(s,t,weights) 还使用数组 weights 指定边的权重。示例
G = Graph(s,t,weights,nodenames) 还使用字符串数组 nodenames 指定节点名称。s 和 t 不能包含 nodenames 中没有的节点名称。示例
G = Graph(s,t,weights,nodenames,nodeprops) 使用 nodenames 指定节点名称并使用 nodeprops 指定节点属性。
G = Graph(s,t,weights,nodenames,nodeprops,edgeprops) 使用 edgeprops 指定边属性。edgeprops 长度必须与边数相同，每个元素对应 s 和 t 中的每一对元素。若不想输入前几项参数可输入指定类型的空数组。
G = Graph(s,t,weights,num) 使用数值标量 num 指定图中的节点数。示例
G = Graph(s,t,___;omitselfloops = true) 不会将任何自环添加到图。即，将忽略满足 s(k) == t(k) 的任何 k。您可以使用上述语法中的任何输入参数组合。
# 输入参数
A - 邻接矩阵矩阵
邻接矩阵，指定为矩阵。A 中每个非零项的位置指定两个节点之间的边。该元素的值提供边的权重。逻辑邻接矩阵会生成未加权图。
A 的主对角线上的非零项指定自环，即通过一条边连接到自身的节点。使用 omitselfloops=true 输入选项可忽略对角线元素。
A 必须是对称的，除非指定了 type 输入。使用 issymmetric 确认矩阵对称性。对于三角邻接矩阵，指定 type 以仅使用上或下三角矩阵。
示例： A = [0 1 0; 0 0 0; 5 0 0] 描述具有三个节点和两条边的图。从节点 1 到节点 2 的边具有权重 1，从节点 3 到节点 1 的边具有权重 5。
nodenames - 节点名称字符串数组 | 字符串
节点名称，指定为字符串数组|字符串。nodenames 的长度必须等于 numnodes(G)，从而将图形中每个节点的非空唯一名称包含在该数组中。
示例： G = Graph(A,["n1","n2","n3"]) 指定一个 3×3 邻接矩阵 A 的三个节点名称。
type - 邻接矩阵的类型"upper" | "lower"
邻接矩阵的类型，指定为 "upper" 或 "lower"。
示例： G = Graph(A,"upper") 仅使用 A 的上三角矩阵来构造图 G。
s,t - 节点对组（以单独参数指定）节点索引 | 节点名称
节点对组，指定为节点索引或节点名称。Graph 在 s 和 t 中的对应节点之间创建边，这些节点必须都是数值，或都是字符串、字符串数组或分类数组。在所有情况下，s 和 t 都必须具有相同的元素数。
如果 s 和 t 都是数值，则它们对应于图节点的索引。数值节点索引必须为大于或等于 1 的正整数。
如果 s 和 t 是字符串或字符串数组，则它们指定节点的名称。
如果 s 和 t 是分类数组，则 s 和 t 中的类别将用作图中的节点名称。这可以包括不是 s 或 t 中元素的类别。
如果 s 和 t 指定相同两个节点之间的多条边，则结果为多重图。
下表显示通过数值节点索引或节点名称引用一个或多个节点的不同方法。
| 形式 | 单一节点 | 多个节点 |
|---|---|---|
| 节点索引 | 标量 示例： | 向量 示例： |
| 节点名称 | ||
字符串标量 示例： | 字符串数组 示例： | |
带有分类的数组 示例： | 带有分类的数组 示例： |
示例： G = Graph([1,2,3],[2,4,5]) 创建一个具有五个节点和三条边的图。
示例： G = Graph(["Boston","New York","Washington D.C."],["New York","New Jersey","Pittsburgh"]) 创建一个具有五个命名节点和三条边的图。
weights - 边权重浮点标量 | 浮点向量
边权重，指定为标量、向量、矩阵或多维数组。weights 必须是标量或者是元素数与 s 和 t 相同的数组。
Graph 将边权重存储为 G.Edges.weights。要在创建图后添加或更改权重，您可以直接修改，例如 G.Edges.weights = [25,50,75]。
如果将 weights 指定为空数组 Float64[]，它将被忽略。
示例： G = Graph([1,2],[2,3],[100,200]) 创建具有三个节点和两条边的图。两条边的权重分别为 100 和 200。
nodeprops - 节点属性标量 | 向量
图节点属性，指定为标量或向量。
可指定为Bool型、整形、浮点型、字符串等，赋予节点指定的属性。
若要指定多种属性，需将每点的所有属性拼接后再传入。多属性时 addnode 等增加节点的方法必须指定节点属性才能添加。
可指定为空 [] 声明无节点属性的图。
示例： G = Graph([1,2],[2,3],1,["a","b","c"],[true,false,true]) 创建具有三个带属性节点的图。
edgeprops - 边属性标量 | 向量
边节点属性，指定为标量或向量。
可指定为Bool型、整形、浮点型、字符串等，赋予边指定的属性。
若要指定多种属性，需将每点的所有属性拼接后再传入。多属性时 addedge 等增加边的方法必须指定边属性才能添加。
示例： G = Graph([1,2],[2,3],1,["a","b","c"],[true,false,true],[1,2]) 创建具有三个带属性节点，两个带属性边的图。
num - 图节点数正整数标量
图节点数，指定为正整数标量。num 必须大于或等于 s 和 t 中的最大元素。
示例： G = Graph([1,2],[2,3],[],5) 创建具有三个相连接的节点和两个孤立节点的图。
# 属性
Edges - 图的边边结构体
图的边，以边结构体形式返回。G.Edges.endnodes 中的边列表首先按源节点、然后按目标节点排序。
- 要在图中添加或删除边，请使用 addedge 或 rmedge 对象函数。
示例： G.Edges 返回结构体，其中列出图中的边。
示例： G.Edges.weights 返回边权重的数值向量。
示例： G.Edges.weights = [10,20,30,55] 指定图的新边权重。
Nodes - 图的节点节点结构体
图的节点，以节点结构体形式返回。
- 要在图中添加或删除节点，请使用 addnode 或 rmnode 对象函数。
示例： G.Nodes 返回结构体，其中列出图的节点属性。
示例： G.Nodes.nodeNames = ["Montana", "New York", "Washington", "California"] 将节点名称添加到图。
示例： G.Nodes.props = [true,false,false,true,true] 将节点属性添加到 Nodes 。此例中用户指定属性含义为某些机场是否有 WIFI 覆盖。
# 示例
创建和修改图对象
创建具有三个节点和两条边的 Graph 对象。一条边位于节点 1 和节点 2之间，另一条位于节点 1 和节点 3之间。
using TyMath
G = Graph([1,1],[2,3])
G =
Graph with properties:
Edges:2×1
Nodes:3×0
查看图的边表。
G.Edges
ans =
2×1
EndNodes
1 2
1 3
向图中添加节点名称，然后查看新节点和边。
G.Nodes.nodeNames = ["A","B","C"];
G.Nodes
ans =
3×1
Name
A
B
C
G.Edges
ans =
3×1
EndNodes
1 2
1 3
您可以在 Nodes 和 Edges 中修改其他变量，以描述图节点或边的属性。但是，您无法通过修改这些结构体直接更改图中节点或边的数量。此时，应使用 addedge、rmedge、addnode 或 rmnode 函数修改图中节点或边的数量。
例如，向图中的节点 2 和 3 之间添加一条边并查看新边列表。
G = addedge(G,2,3)
G =
Graph with properties:
Edges:3×1
Nodes:3×1
G.Edges
ans =
4×1
EndNodes
1 2
1 3
2 3
构造邻接矩阵图
创建一个对称邻接矩阵 A，该矩阵用于创建 4 阶完整图。使用逻辑邻接矩阵创建不带权重的图。
using TyMath
A = ones(Int, 4, 4) - diagm([1, 1, 1, 1])
A = 4×4 Matrix{Int64}:
0 1 1 1
1 0 1 1
1 1 0 1
1 1 1 0
G = Graph(A .!= 0)
G =
Graph with properties:
Edges:6×1
Nodes:4×0
查看图的边列表。
G.Edges
ans =
6×1
EndNodes
1 2
1 3
1 4
2 3
2 4
3 4
使用节点名称构造邻接矩阵图
创建一个上三角邻接矩阵。
using TyMath
A = triu(magic(4))
A = 4×4 Matrix{Int64}:
16 2 3 13
0 11 10 8
0 0 6 12
0 0 0 1
使用邻接矩阵创建具有命名节点的图。指定 omitselfloops=true 以忽略 A 对角线上的元素，并将 type 指定为 "upper" 以指示 A 为上三角矩阵。
names = ["alpha", "beta", "gamma", "delta"];
G = Graph(A, names; type="upper",omitselfloops=true)
G =
Graph with properties:
Edges:6×2
Nodes:4×1
查看边和节点信息。
G.Edges
ans =
6×2
EndNodes Weights
1 2 2
1 3 3
1 4 13
2 3 10
2 4 8
3 4 12
G.Nodes
ans =
4×1
Name
alpha
beta
gamma
delta
构造边列表图
使用每条边的端节点列表创建一个立方体图。
using TyMath
s = [1, 1, 1, 2, 2, 3, 3, 4, 5, 5, 6, 7];
t = [2, 4, 8, 3, 7, 4, 6, 5, 6, 8, 7, 8];
G = Graph(s, t)
G =
Graph with properties:
Edges:12×1
Nodes:8×0
使用节点名称和边权重构造边列表图
使用每条边的端节点列表创建并绘制一个立方体图。将节点名称和边权重指定为单独的输入。
using TyMath
s = [1, 1, 1, 2, 2, 3, 3, 4, 5, 5, 6, 7];
t = [2, 4, 8, 3, 7, 4, 6, 5, 6, 8, 7, 8];
weights = [10, 10, 1, 10, 1, 10, 1, 1, 12, 12, 12, 12];
names = ["A", "B", "C", "D", "E", "F", "G", "H"];
G = Graph(s, t, weights, names)
G =
Graph with properties:
Edges:12×2
Nodes:8×1
具有额外节点的边列表构造
使用每条边的端节点的列表创建加权图。指定图应包含共 10 个节点。
using TyMath
s = [1, 1, 1, 1, 1];
t = [2, 3, 4, 5, 6];
weights = [5, 5, 5, 6, 9];
G = Graph(s, t, weights, 10)
G =
Graph with properties:
Edges:5×2
Nodes:10×0
将节点和边添加到空图
创建一个空图对象 G。
using TyMath
G = Graph();
将三个节点和三条边添加到该图。s 和 t 中的相应项定义各条边的源节点和目标节点。addedge 自动将适当的节点添加到图（如果这些节点尚不存在）。
s = [1, 2, 1];
t = [2, 3, 3];
G = addedge(G, s, t)
G =
Graph with properties:
Edges:3×1
Nodes:3×0
查看边列表。每行描述图中的一条边。
G.Edges
ans =
3×1
EndNodes
1 2
1 3
2 3
要获得最佳性能，请通过调用一次 Graph 来一次性构造多个图。对于大图来说，以循环方式添加节点或边会比较慢。