Networkx
使用 NetworkX，您可以以标准和非标准数据格式加载和存储网络，生成多种类型的随机和经典网络，分析网络结构，构建网络模型，设计新的网络算法，绘制网络等等。
import networkx as nx-
关联矩阵
表示了每个节点和每条边之间的关系
-
邻接矩阵
邻接矩阵表示了两个节点之间的关系
-
距离矩阵
该矩阵的i行j列为节点i和j之间的距离 -
导出矩阵
nx.to_numpy_matrix(G) # 导出为numpy矩阵 nx.to_scipy_sparse_matrix(G) # 导出为稀疏矩阵
-
无向图
G = nx.Graph() G = nx.Graph(A) # 使用邻接矩阵A创建图G
-
有向图
D = nx.DiGraph() D = nx.DiGraph(A) # 使用邻接矩阵A创建图D D = nx.DiGraph({0: [3], 1: [2], 2: [3], 3: [0, 1]}) # 同时指定方向
-
可重复边的的无向图
M = nx.MultiGraph()
-
可重复边的有向图
M = MultiDigraph()
-
创建完全图
nx.complete_graph(n, create_using=None)
n: 如果n为一个数，节点为0~(n-1)，或者使用元祖指定节点
create_using: 图的类型，例如无向图和有向图 -
添加边
G.add_edge('Alice', 'Bob')
-
通过字典或列表，添加多条边
drive_times = {('Albany', 'Boston'): 3, ('Albany', 'NYC'): 4, ('Boston', 'NYC'): 4, ('NYC', 'Philly'): 2} G.add_edges_from(drive_times)
-
添加有权边
G.add_weighted_edges_from(ebunch_to_add, weight='weight', **attr)
- 传入元祖构成的列表，例如[(0, 1, 3.0), (1, 2, 7.5)]
-
添加节点
G.add_node('Alice')
-
通过字典或列表，添加多个节点
positions = dict(Albang = (-74, 43), Boston = (-71, 42), NYC = (-74, 41), Philly = (-75, 40)) G = nx.Graph() G.add_nodes_from(positions)
-
图的节点
list(G.nodes())
-
图的边
list(G.edges())
-
边的权值
nx.get_edge_attributes(G, name)
name: 边属性的名字，例如'weight'权重，'color'颜色
-
节点度数
nx.degree(G, nbunch=None, weight=None)
返回{节点:度数}字典
-
图中的所有节点
nx.nodes(G)
使用方法: list(nx.nodes(G))
-
节点数量
nx.number_of_nodes(G)
-
相邻节点
nx.neighbors(G, n)
使用方法: list(nx.neighbors(G, 2)) 或 [n for n in G.neighbors(node)]
-
不相邻节点
nx.non_neighbors(graph, node)
-
两个节点相同的节点
nx.common_neighbors(G, u, v)
返回 list(nx.common_neighbors(G, 1, 3))
-
节点度数频度视图
nx.degree_histogram(G)
返回从0开始到最大度数列表
-
边的视图
nx.edges(G, nbunch=None)
返回对应的边的列表，用两个节点表示一条边 [(node_i, node_j)]
-
边的数量
nx.number_of_edges(G)
-
图的密度
nx.density(G)
这里是官网绘图文档
-
基础绘图
nx.draw(G, pos=None, ax=None, **kwds)
- pos: key为node,value为元祖坐标的字典 或 预定的布局
- ax: 可在某个轴上绘制该图(matplotlib) 还可以使用with_labels等参数
-
绘制边和节点的标签
def draw_with_labels(G, pos=nx.random_layout(G)): nx.draw(G,pos) nx.draw(G, pos, with_labels=True) labels = nx.get_edge_attributes(G,'weight') nx.draw_networkx_edge_labels(G,pos,edge_labels=labels) plt.show()
-
详细绘图
nx.draw_networkx(G, pos=None, arrows=True, with_labels=True, **kwds)
arrows: 对于有向图是否画箭头 arrowstyle: 箭头样式，默认’-|>’.详见matplotlib.patches.ArrowStyle
arrowsize: 箭头大小，默认10.
with_labels: 是否显示节点标签
ax: 在matplotlib的某个axes对象上绘图
nodelist: 只画出指定的几个节点
edgelist: 只画出指定的几条边
node_size: 节点大小，默认300
node_color: 节点颜色，默认’#1f78b4’
node_shape: 节点形状，默认'o'，可选'so^>v<dph8’
alpha: 节点透明度
cmap: Matplotlib colormap, optional (default=None)
edge_color: 边的颜色
style: 边的样式，默认’solid’,可选(solid|dashed|dotted,dashdot)
font_size: 标签字体大小
font_color: 字体颜色
font_weight: 字体宽度
font_family: 字体样式
label: 图例标签 -
只绘制节点
nx.draw_networkx_nodes(G, pos, nodelist=None, node_size=300, node_color='#1f78b4', node_shape='o', alpha=None, cmap=None, vmin=None, vmax=None, ax=None, linewidths=None, edgecolors=None, label=None)
返回值：matplotlib.collections.PathCollection类型的节点
-
只绘制边
draw_networkx_edges(G, pos, edgelist=None, width=1.0, edge_color='k', style='solid', alpha=None, arrowstyle='-|>', arrowsize=10, edge_cmap=None, edge_vmin=None, edge_vmax=None, ax=None, arrows=True, label=None, node_size=300, nodelist=None, node_shape='o', connectionstyle=None, min_source_margin=0, min_target_margin=0)
返回值：matplotlib.collection.LineCollection类型的边
-
绘制节点标签
draw_networkx_labels(G, pos, labels=None, font_size=12, font_color='k', font_family='sans-serif', font_weight='normal', alpha=None, bbox=None, horizontalalignment='center', verticalalignment='center', ax=None)
返回字典类型
-
绘制边标签
draw_networkx_edge_labels(G, pos, edge_labels=None, label_pos=0.5, font_size=10, font_color='k', font_family='sans-serif', font_weight='normal', alpha=None, bbox=None, horizontalalignment='center', verticalalignment='center', ax=None, rotate=True)
- edge_labels: 可以使其等于nx.get_edge_attributes(G, 'weight')将边权重作为标签信息绘制 或者可以使用字典 返回字典类型
-
下面几种绘图方式是直接使用某种类型绘图
# 节点在圆环均匀分布绘图 nx.draw_circular(G, node_color='b', node_size=2000, with_labels=True) # Draw the graph G with a Kamada-Kawai force-directed layout. draw_kamada_kawai(G, **kwargs) # Draw a planar networkx graph with planar layout. draw_planar(G, **kwargs) # Draw the graph G with a random layout. draw_random(G, **kwargs) # Draw the graph G with a spectral 2D layout. draw_spectral(G, **kwargs) # Draw the graph G with a spring layout. draw_spring(G, **kwargs) # Draw networkx graph with shell layout. draw_shell(G, **kwargs)
-
绘图布局
绘图函数有pos参数，可以使用字典自行规定每个节点的坐标，或者使用预制的layout- circular_layout: 顶点在圆环上均匀分布
- random_layout: 顶点随机分布
- shell_layout: 顶点在同心圆上分布
- spring_layout: 用Fruchterman-Reingold算法排列顶点
- spectral_layout: 根据图的Laplace特征向量排列顶点
-
随机图
当图的节点联通率为p > p*=(ln n)/n时，图很有可能为连通的，在p*位置，图的连通率会发生突变 -
构造完全图(每两个节点之间相互相连)
def all_pairs(nodes): for i, u in enumerate(nodes): for j, v in enumerate(nodes): if i>j: yield u,v def make_complete_graph(n): G = nx.Graph() nodes = range(n) G.add_nodes_from(nodes) G.add_edges_from(all_pairs(nodes)) return G
-
连通图(每两个节点都有路径相连)
该函数接受一个图和一个起始节点start，从起始节点开始，返回可以到达的节点集def reachable_nodes(G, start): seen = set() stack = [start] while stack: node = stack.pop() if node not in seen: seen.add(node) stack.extend(G.neighbors(node)) return seen
该函数判断图G是否连通
def is_connected(G): start = next(iter(G)) reachable = reachable_nodes(G, start) return len(reachable) == len(G)
-
将图以dot格式写入文件
nx.write_dot(G, path)
nx.write_dot(G,'a.dot')
!neato -T png a.dot > a.png
ER图有两个特点，n为节点数目，p为两个节点间存在一条边的概率
-
下面的生成器枚举了所有的边，并选择哪些便应该添加到图中
def flip(p): return np.random.random() < p; # 返回0-1随机分布数字 def random_pairs(nodes, p): for edge in all_pairs(nodes): if flip(p): yield edge
-
生成并返回ER图
def make_random_graph(n, p): G = nx.Graph() nodes = range(n) G.add_nodes_from(nodes) G.add_edges_from(random_pairs(nodes, p)) return G
-
多次跌代计算图的连通率
def prob_connected(n, p, iters=100): tf = [is_connected(make_random_graph(n, p)) for i in range(iters)] return np.mean(tf)
dijkstra算法用于求一个节点到其余节点的最短路径，且边权要为正数
- 初始化：初始节点距离为0，其余为正无穷，标记起始节点
- 选择最短路径节点：选择距离出发节点最近的节点，标记，收录到最优路径中(第一次为开始节点)
- 更新最短路：添加相邻节点，根据目前点的最短路，加上相邻节点的边的权重，若得到的距离小于目前该节点的距离，则更新该节点的距离，并标记其后面节点为当前节点 不断重复后面两步，直到要求的节点被收录到最优路径里为止
贝尔曼-福特算法与迪科斯彻算法类似，都以松弛操作为基础，即估计的最短路径值渐渐地被更加准确的值替代，直至得到最优解。
- 求两个节点之间的最短路径
nx.shortest_path(G, source=None, target=None, weight=None, method='dijkstra')- weight: (weight/distance/cost)
- method: 采用算法(‘dijkstra’, ‘bellman-ford’)
返回值：最短路径节点组成的列表或字典
- 如果只传入source开始节点，返回由目标节点为key的最短路径集合(只传入target目标节点同理)
- 如果两个节点都没传入，则返回一个嵌套字典{开始节点:{结束节点:[路径]}}
- 求两个节点之间的全部最短路径
nx.all_shortest_paths(G, source, target, weight=None, method='dijkstra')返回值：返回一个含有所有最短路径的生成器
- 使用方法: print( p for p in nx.all_shortest_paths(G, source, target, weight=None, method='dijkstra') )
- 计算最短路径长度
nx.shortest_path_length(G, source=None, target=None, weight=None, method='dijkstra')返回值：
- 若只指定了source和target中的一个，则返回字典类型(同上)
- 若两个值都未指定，则返回一个迭代器(source, dictionary)
- 使用方法: p = dict( nx.shortest_path_length(G, source=None, target=None, weight='weight', method='dijkstra') )
- 平均最短路径长度
nx.average_shortest_path_length(G, weight=None, method=None)
- 判断两节点之间是否存在通路
nx.has_path(G, source, target)返回布尔值
-
最短路应用范例(设备更新)
年份 1 2 3 4 当年购买价格/万元 25 26 28 31 使用年份费用/万元 10 14 18 26 当年末出售价格/万元 20 16 13 11 计算后得到以下表: 从i年初到j年末费用
i \ j 1 2 3 4 5 1 0 15 33 54 82 2 0 0 16 34 55 3 0 0 0 18 36 4 0 0 0 0 21 5 0 0 0 0 0 我们可以构造以下有向图
import numpy as np M = np.zeros((5,5)) buy = np.array([25, 26, 28, 31]) repail = np.array([10, 14, 18, 26]) sell = np.array([20, 16, 13, 11]) spent_year = list() def years(repail, sell): for i in range(len(repail)): spent_year.append(np.sum(repail[:i+1]) - sell[i]) return spent_year spent_year = years(repail, sell) for i in range(len(buy)): for j in range(len(buy) + 1): if i < j: M[i, j] = buy[i] + spent_year[j-i-1] path = nx.shortest_path(D, source=0, target=4, weight='weight', method='dijkstra') print('Least fee year:', [i+1 for i in list(path)]) fee = nx.shortest_path_length(D, 0, 4, weight='weight') print('最小费用:', fee)
import matplotlib.pyplot as plt %matplotlib inline import networkx as nx D = nx.DiGraph(M) def draw_with_labels(D, pos=nx.shell_layout(D)): nx.draw(D,pos) nx.draw(D, pos, with_labels=True) labels = nx.get_edge_attributes(D,'weight') nx.draw_networkx_edge_labels(D,pos,edge_labels=labels) plt.show() draw_with_labels(D)
最小生成树可以用来解决最短路程类问题，给定地点，要求每个点间可达，求最短路程
- kruskal算法
该算法就是将节点间的距离排序，依次选取最短的边，并且保证不构成回路，否则不选择该点，最后得到n-1条边后就的到了最小生成数
nx.minimum_spanning_tree(G, weight='weight', algorithm='kruskal', ignore_nan=False)
实例代码
G = nx.Graph()
pos= dict(v1 = (10, 20),
v2 = (10, 10),
v3 = (90, 10),
v5 = (90, 20),
v4 = (130, 10))
G.add_nodes_from(pos)
G.add_weighted_edges_from([('v1', 'v2', 8),
('v1', 'v5', 2),
('v1', 'v3', 4),
('v5', 'v3', 1),
('v2', 'v3', 4),
('v5', 'v4', 5),
('v3', 'v4', 2)])
nx.draw(G, pos, with_labels=True)
weight = nx.get_edge_attributes(G, 'weight')
nx.draw_networkx_edge_labels(G, pos, edge_labels=weight)
plt.show()
# 最小生成树
T = nx.minimum_spanning_tree(G)
nx.draw(T, pos = pos, with_labels=True)
weight2 = nx.get_edge_attributes(T, 'weight')
nx.draw_networkx_edge_labels(T, pos, edge_labels=weight2)
plt.show()
| 概念 | 解释 |
|---|---|
| 欧拉通路 | 通过图中每条边且只通过一次，并且经过每一顶点的通路 |
| 欧拉环游 | 图的环游是指经过图的每条边至少一次的闭途径 |
| 欧拉回路 | 通过图中每条边且只通过一次，并且经过每一顶点的回路 |
| 半欧拉图 | 具有欧拉通路但不具有欧拉回路的无向图称为半欧拉图，有且仅有两个度数为奇数的结点 |
| 欧拉图 | 具有欧拉回路的图 |
-
欧拉定理
一个非空连通图是欧拉图当且仅当它的每个顶点的度数都是偶数 (简单说欧拉通路就是首尾不相接，而欧拉回路要求首尾相接，欧拉回路就是一笔画，有欧拉回路的图就是欧拉图) -
推论
- 无向连通图 G 是欧拉图，当且仅当 G 不含奇数度结点
- 无向连通图 G 含有欧拉通路，当且仅当 G 有零个或两个奇数度的结点
- 有向连通图 D 是欧拉图，当且仅当该图 D 中每个结点的入度=出度
-
判断是否为欧拉图
nx.is_eulerian(G)
-
欧拉回路
nx.eulerian_circuit(G, source=None, keys=False)
返回一个构成欧拉回路的边边组成的迭代器 list(nx.eulerian_circuit(G))
-
欧拉化
将一个无向图转化为欧拉图(就是通过复制产生重复边，使其奇度定点全部为偶度顶点，此外还要使添加的重复边尽量少)nx.eulerize(G)
返回一个可重复边类型的图MultiGraph
简而言之，就是顶点集V可分割为两个互不相交的子集，并且图中每条边依附的两个顶点都分属于这两个互不相交的子集，两个子集内的顶点不相邻。
from networkx.algorithms import bipartite-
创建二部图
B = nx.Graph() # 使用属性 "bipartite" 建立二部图 B.add_nodes_from([1, 2, 3, 4], bipartite=0) B.add_nodes_from(["a", "b", "c"], bipartite=1) # 边只能在两个不同集合之间 B.add_edges_from([(1, "a"), (1, "b"), (2, "b"), (2, "c"), (3, "c"), (4, "a")])
-
访问二部图节点集合
bottom_nodes, top_nodes = bipartite.sets(B)
-
判断是否为二部图
nx.is_bipartite(G)
-
二部图的最大(基数)匹配
nx.maximum_matching(G, top_nodes=None)
匹配指这个图之中，任意两条边都没有公共的顶点
-
最大基数匹配：指求出图中的一个matching，使得matching包含的边数最多。
-
最大权重匹配
# 这个函数是近似算法 nx.max_weight_matching(G, maxcardinality=False, weight='weight')
若要求最小权重匹配，将权值取负，然后求最大匹配就可以了
-
完美匹配：如果一个图的某个匹配中，所有的顶点都是匹配点，那么它就是一个完美匹配。
匈牙利算法用于解决最小化指派问题： 将i个人分配j个工作，每个人由于技能的不同，完成工作的时间不同，求最好的分配方式。
这里使用效率矩阵C(i,j)表示i人做工作j的时间(所有元素都要大于等于0)
可以转化为规划问题:
min = C(i,j)x(i,j)
sum(x(i,j), j) = 1
sum(x(i,j), i) = 1
x(i,j) = 0 / 1
- 第一步: 得到效率矩阵C，将矩阵每一行或列减去该行最小的数，将其变化成了每行都含0的矩阵C1
- 第二步： 用圈零法求新矩阵C1中独立零元素
- 进行行检验： 如果该行只有一个0元素，将该元素圈起来，并将该元素同一列的元素删掉(打叉) 重复行检验，直到每一行都没有未标记过的0元素，或小于等于两个为标记的0元素为止
- 进行列检验： 类似以上步骤
现在有三种情况：
- 独立0元素数量等于矩阵阶，此时每个人都可以直接分配工作
- 存在未标记的0元素，例如存在两个，那么表明有两种情况，随便选取一个代表一种情况
- 不存在未标记的0元素，但是圈0的数量 < 矩阵的阶
- 第三步： 进行试指派
若为前两种情况，则可以进行指派
若为第三种情况，则进行下一步 - 第四步： 做最小直线覆盖当前所有0元素
- 将矩阵中所有不含圈0元素的行打勾
- 对打勾的行中的所有0元素的列打勾
- 对于所有打勾列中圈0元素所在列打勾
- 重复2~3直到不能进一步打勾为止
- 对没有打勾的行画横线，对已经打勾的列画一条竖线 在未被直线覆盖的元素中挑出最小的元素，将打勾行的每个元素减去这个最小元素，对打勾列的每个元素加上这个最小元素，这样就将0元素数量增加了。然后再重复前面过程即可。
若要求最大指派问题，可以转化矩阵b(i,j) = M - c(i,j)，其中M为矩阵c中最大元素，任何求b矩阵的最小化问题
竞赛图是通过在无向完整图中为每个边缘分配方向而获得的有向图。
- 判断是否为竞赛图
nx.is_tournament(G)
哈密顿图是一个无向图，由指定的起点前往指定的终点，途中经过所有其他节点且只经过一次。在图论中是指含有哈密顿回路的图，闭合的哈密顿路径称作哈密顿回路（Hamiltonian cycle），含有图中所有顶点的路径称作哈密顿路径.
- 返回竞赛图的哈密顿图
nx.hamiltonian_path(G)
旅行商问题是这样一个问题：给定一系列城市和每对城市之间的距离，求解访问每一座城市一次并回到起始城市的最短回路。
- 克里斯托菲德斯算法
克里斯托菲德斯算法 (Christofides algorithm) 是旅行商问题在度量空间（即距离对称且满足三角不等式）上的一个近似算法。
该算法可以保证相对最优哈密尔顿回路长度有3/2的近似比。截至2017年，这一算法仍然是一般性旅行商问题的算法中近似比最好的结果。 算法步骤:
- 构造图上的最小的生成树T(图为完全图且满足三角不等式)
- 令O为原图顶点集中在T上度数为奇数的顶点集。根据握手定理O中有偶数个顶点
- 构造点集O在原完全图上的最小完美匹配M
- 将 M 和 T 的边集取并，构造重图 H ，满足其每个顶点都是偶数度的
- H 可以形成一个欧拉回路
- 将前一步得到的图改造为一个哈密尔顿回路：只需要跳过前一步欧拉回路中重复的顶点即可
下面使用google or-tools解决该问题
"""Simple traveling salesman problem between cities."""
from ortools.constraint_solver import routing_enums_pb2
from ortools.constraint_solver import pywrapcp
def create_data_model():
"""为该问题创建数据"""
data = {}
data['distance_matrix'] = [
[0, 7, 4, 5, 8, 6, 12, 13, 11, 18],
[7, 0, 3, 10, 9, 14, 5, 14, 17, 17],
[4, 3, 0, 5, 9, 10, 21, 8, 27, 12],
[5, 10, 5, 0, 14, 9, 10, 9, 23, 16],
[8, 9, 9, 14, 0, 7, 8, 7, 20, 19],
[6, 14, 10, 9, 7, 0, 13, 5, 25, 13],
[12, 5, 21, 10, 8, 13, 0, 23, 21, 18],
[13, 14, 8, 9, 7, 5, 23, 0, 18, 12],
[11, 17, 27, 23, 20, 25, 21, 18, 0, 16],
[18, 17, 12, 16, 19, 13, 18, 12, 16, 0]
] # 距离矩阵
data['num_vehicles'] = 1 # 汽车(销售员)数量
data['depot'] = 0 # 开始结束节点
return data
""" 打印结果 """
def print_solution(manager, routing, solution):
"""Prints solution on console."""
print('Objective: {} miles'.format(solution.ObjectiveValue()))
index = routing.Start(0)
plan_output = 'Route for vehicle 0:\n'
route_distance = 0
while not routing.IsEnd(index):
plan_output += ' {} ->'.format(manager.IndexToNode(index))
previous_index = index
index = solution.Value(routing.NextVar(index))
route_distance += routing.GetArcCostForVehicle(previous_index, index, 0)
plan_output += ' {}\n'.format(manager.IndexToNode(index))
print(plan_output)
plan_output += 'Route distance: {}miles\n'.format(route_distance)
def main():
"""Entry point of the program."""
# Instantiate the data problem.
data = create_data_model()
# Create the routing index manager.
manager = pywrapcp.RoutingIndexManager(len(data['distance_matrix']),
data['num_vehicles'], data['depot'])
# Create Routing Model.
routing = pywrapcp.RoutingModel(manager)
def distance_callback(from_index, to_index):
"""Returns the distance between the two nodes."""
# Convert from routing variable Index to distance matrix NodeIndex.
from_node = manager.IndexToNode(from_index)
to_node = manager.IndexToNode(to_index)
return data['distance_matrix'][from_node][to_node]
transit_callback_index = routing.RegisterTransitCallback(distance_callback)
# Define cost of each arc.
routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index)
# Setting first solution heuristic.
search_parameters = pywrapcp.DefaultRoutingSearchParameters()
search_parameters.first_solution_strategy = (
routing_enums_pb2.FirstSolutionStrategy.CHRISTOFIDES)
# Solve the problem.
solution = routing.SolveWithParameters(search_parameters)
# Print solution on console.
if solution:
print_solution(manager, routing, solution)
if __name__ == '__main__':
main()若要采用其他算法，可以修改FirstSolutionStrategy
扩展:
- Vehicle Routing Problem (汽车路程问题): 多个汽车到多个节点的最短路问题，当只有一个汽车时
- Capacity Constraints (容量限制): 汽车需要在每个节点运载货物，但最大运载量有限
- Vehicle Routing Problem with Time Windows (带时间窗口的汽车路径问题): 每个节点有限制的访问时间
- 若图中有欧拉回路，因为欧拉回路通过所有的边，因此任何一个欧拉回路即为此问题的解。
- 若图中不存在欧拉回路，其中必存在有奇数个边的端点，且这类的端点一定大于等于2个。此时将图欧拉化，然后再求欧拉回路。 若为有权图，则每两个节点之间权为两个节点间的最短路径。