Graph | NetworkX |1 NetworkX 介绍

澄心

为者常成，行者常至

NetworkX 的结构可以从其源代码的组织中看出。该包提供了 图对象的类、创建标准图的生成器、读取现有数据集的 IO 例程、分析结果网络的算法和一些基本的绘图工具 。

大多数 NetworkX API 是由将图对象作为参数的函数提供的。图对象的方法仅限于基本操作和报告。这提供了代码和文档的模块化。它还使新人更容易分阶段了解该软件包。每个模块的源代码都旨在易于阅读，阅读此 Python 代码实际上是了解更多网络算法的好方法，但我们付出了很多努力使文档充分和友好。如果您有任何建议或问题，请加入 NetworkX Google 群组与我们联系。

类使用 CamelCase （每个单词开头的大写字母）命名。函数、方法和变量名是 lower_case_underscore （小写，下划线表示单词之间的空格）。

NetworkX 基础知识

导入包

import networkx as nx

为了避免重复，在文档中我们假设 NetworkX 已经以这种方式导入。

如果导入 networkx 失败，则意味着 Python 找不到已安装的模块。检查您的安装和 PYTHONPATH。

以下基本图形类型作为 Python 类提供：

Graph 这个类实现了一个无向图。它忽略了两个节点之间的多条边。它确实允许节点与其自身之间的自循环边。

DiGraph 有向图，即具有有向边的图。提供有向图（Graph 的子类）通用的操作。

MultiGraph 一个灵活的图类，允许节点对之间有多个无向边。额外的灵活性会导致性能下降，但通常并不显着。

MultiDiGraph MultiGraph 的有向版本。

创建空的类似图的对象

G = nx.Graph()
G = nx.DiGraph()
G = nx.MultiGraph()
G = nx.MultiDiGraph()

所有图类都允许任何 可散列 （ hashable ）对象作为节点。可散列对象包括字符串、元组、整数等。任意边的属性（例如权重和标签）可以与边相关联。

图内部数据结构基于邻接表表示，并使用 Python 字典数据结构实现。图邻接结构被实现为字典的 Python 字典；外部字典由节点键控到值，这些值本身就是由相邻节点键控到与该边缘关联的边的属性的字典。这种“dict-of-dicts”结构允许在大图中快速添加、删除和查找节点和邻居。底层数据结构由类定义中的方法（编程接口“API”）直接访问。另一方面，所有函数都仅通过这些 API 方法操作类似图形的对象，而不是直接作用于数据结构。这种设计允许用实现相同方法的替代数据结构替换基于“dicts-of-dicts”的数据结构。

图（Graphs）

使用 NetworkX 时首先要选择的是使用哪种类型的 图对象 。

图（网络）是节点的集合以及作为节点对的边的集合。属性通常与节点和/或边相关联。 NetworkX 图形对象有不同的风格，具体取决于网络的两个主要属性：

有向的（Directed）：边是否有向？边对的顺序重要吗？有向图由类名中的“Di”前缀指定，例如 DiGraph() 。我们之所以做出这种区分，是因为许多经典图属性对有向图的定义不同。
多边（Multi-edges）：每对节点之间是否允许多条边？正如您可能想象的那样，多个边需要不同的数据结构，尽管聪明的用户可以设计边的数据属性来支持此功能。我们使用前缀“Multi”为此类图提供标准数据结构和接口，例如 MultiGraph() 。

基本的图的结构是: Graph , DiGraph , MultiGraph , 和 MultiDiGraph 。

节点和边

指定图形时必须做出的 下一个 选择是使用什么样的 节点和边 。

如果您只关心网络的拓扑结构，那么使用整数或字符串作为节点是有意义的，您不必担心边数据。如果您已经有一个数据结构来描述节点，您可以简单地使用该结构作为您的节点，只要它是可散列的。如果它不可散列，您可以使用唯一标识符来表示节点并将数据分配为节点属性。

边通常具有与之关联的数据。任意数据可以作为边的属性与边相关联。如果数据是数字并且意图是表示加权图，则使用 weight 关键字作为属性。一些图算法，比如 Dijkstra 的最短路径算法，默认使用这个属性名称来获取每条边的权重。

在添加边时，可以使用关键字/值对将属性分配给边。您可以使用任何关键字来命名您的属性，然后可以使用该属性关键字查询边缘数据。

一旦你决定了如何编码节点和边，以及你是否有一个有或没有多重边的无向/有向图，你就可以构建你的网络了。

图表创建

NetworkX 图形对象可以通过以下三种方式之一创建：

图生成器——创建网络拓扑的标准算法。
从预先存在的（通常是文件）源导入数据。
显式添加边和节点。

节点/边的显式添加和删除是最容易描述的。每个图形对象都提供操作图形的方法。例如，

import networkx as nx
G = nx.Graph()
G.add_edge(1, 2)  # default edge data=1
G.add_edge(2, 3, weight=0.9)  # specify edge data

边的属性可以是任何东西：

import math
G.add_edge('y', 'x', function=math.cos)
G.add_node(math.cos)  # any hashable can be a node

您可以一次添加许多边：

elist = [(1, 2), (2, 3), (1, 4), (4, 2)]
G.add_edges_from(elist)
elist = [('a', 'b', 5.0), ('b', 'c', 3.0), ('a', 'c', 1.0), ('c', 'd', 7.3)]
G.add_weighted_edges_from(elist)

有关更多示例，请参阅教程。

运算符模块文档中描述了一些基本的图形操作，例如并集和交集。

图生成器子包中提供了图生成器，例如 binomial_graph() 和 erdos_renyi_graph() 。

要从 GML、GraphML、边列表文本文件等格式导入网络数据，请参读入和写出图子包。

图报告

类视图提供节点、邻居、边和度数的基本报告。这些视图提供对 属性的迭代 以及 成员关系 查询和 数据属性 查找。视图（views）指的是图形数据结构，因此对图形的更改会反映在视图中。这类似于 Python 3 中的字典视图。如果您想在迭代时更改图形，则需要使用例如 for e in list(G.edges): 。视图提供类似集合的操作，例如并集和交集，以及类似字典对数据属性进行查找和迭代，通过 G.edges[u, v]['color'] 和 for e, datadict in G.edges.items() : 。方法 G.edges.items() 和 G.edges.values() 是 python dicts 中很常见的方法。此外 G.edges.data() 提供特定的属性迭代，例如 for e, e_color in G.edges.data('color'): 。

一条边的基本图关系可以通过两种方式获得。可以 节点的邻居 查找，也可以边查找。我们开玩笑地将关注节点/邻节点称为以节点为中心，将关注边称为以边为中心。 NetworkX 的设计者倾向于 以节点为中心 ，并将边视为节点之间的关系。您可以通过我们选择的查找符号来看到这一点，例如 G[u] 提供邻居（邻接），而边查找是 G.edges[u, v] 。大多数稀疏图的数据结构本质上是邻接表，因此符合这个观点。最后，当然，以哪种方式检查图表并不重要。 G.edges 删除了无向边的重复表示，而跨所有节点的邻居报告自然会报告两个方向。

任何比边、邻居和度更复杂的属性都由函数提供。例如 nx.triangles(G, n) 给出包含节点 n 作为顶点的三角形的数量。这些函数在术语算法下的代码和文档中分组组织。

Algorithms

NetworkX 提供了许多图形算法。这些包括最短路径、广度优先搜索（参见遍历）、聚类和同构算法等。还有很多我们还没有开发。如果您实现的图算法可能对其他人有用，请通过 NetworkX Google 小组或 Github 开发者专区告诉我们。

作为示例，这里是使用 Dijkstra 算法找到最短加权路径的代码：

>>> G = nx.Graph()
>>> e = [('a', 'b', 0.3), ('b', 'c', 0.9), ('a', 'c', 0.5), ('c', 'd', 1.2)]
>>> G.add_weighted_edges_from(e)
>>> print(nx.dijkstra_path(G, 'a', 'd'))
['a', 'c', 'd']

绘图

虽然 NetworkX 不是作为网络绘图工具设计的，但我们提供了一个简单的绘图包接口和一些简单的布局算法。我们使用（建议的）pygraphviz 包或 pydot 接口与优秀的 Graphviz 布局工具（如 dot 和neato）进行交互。绘图可以使用外部程序或 Matplotlib Python 包完成。交互式 GUI 界面是可能的，尽管未实现。绘图工具在模块 drawing 中提供。

基本绘图函数本质上是使用您通过字典提供的位置将节点放置在散点图上，或者使用布局函数计算位置。边是这些点之间的线。

import matplotlib.pyplot as plt
G = nx.cubical_graph()
subax1 = plt.subplot(121)
nx.draw(G)   # default spring_layout
subax2 = plt.subplot(122)
nx.draw(G, pos=nx.circular_layout(G), node_color='r', edge_color='b')

数据结构

NetworkX 使用“字典中的字典”作为基本的网络数据结构。这允许对大型稀疏网络进行合理存储的快速查找。键是节点，因此 G[u] 返回一个由邻居键控的邻接字典到边属性字典。邻接数据结构的视图由 dict-like 对象 G.adj 提供，例如对于节点， G.adj.items() : 中的 nbrsdict。表达式 G[u][v] 返回边缘属性字典本身。列表字典也是可能的，但不允许快速边缘检测，也不方便存储边缘数据。

dict-of-dicts-of-dicts 数据结构的优点：

使用两个字典查找查找边缘和删除边。
更喜欢“列表”，因为稀疏存储可以快速查找。
更喜欢“集合”，因为数据可以附加到边。
G[u][v] 返回边的属性字典。
n in G 测试节点 n 是否在图 G 中。
for n in G : 遍历图。
for nbr in G[n] ：遍历邻节点。

作为一个例子，这里是一个无向图的表示，其边为(A,B)和(B,C) 。

>>> G = nx.Graph()
>>> G.add_edge('A', 'B')
>>> G.add_edge('B', 'C')
>>> print(G.adj)
{'A': {'B': {}}, 'B': {'A': {}, 'C': {}}, 'C': {'B': {}}}

对于每个基本图类，数据结构都会略有变化。

对于有向图，提供了两种 dict-of-dicts-of-dicts 结构，一种用于后继（ G.succ ），一种用于前驱（ G.pred ）。对于 MultiGraph/MultiDiGraph，我们使用 dict-of-dicts-of-dicts-of-dicts [1]，其中第三个字典由边缘键标识符键控到第四个字典，其中包含两个节点之间该边缘的边缘属性 .

图为边数据属性提供了两个接口：邻接和边。所以 G[u][v]['width'] 与 G.edges[u, v]['width'] 相同。

>>> G = nx.Graph()