拓扑排序

本示例演示如何在有向无环图 (DAG) 上获取拓扑排序。有向图的拓扑排序是基于有向边所隐含的优先级的一种线性排序。当且仅当图不包含任何环时，拓扑排序才存在。在 igraph 中，我们可以使用 igraph.GraphBase.topological_sorting() 来获取顶点的拓扑排序。

import igraph as ig
import matplotlib.pyplot as plt

首先，我们生成一个有向无环图 (DAG)

g = ig.Graph(
    edges=[(0, 1), (0, 2), (1, 3), (2, 4), (4, 3), (3, 5), (4, 5)],
    directed=True,
)

我们可以立即验证这确实是一个 DAG

assert g.is_dag

通过调用 igraph.GraphBase.topological_sorting()，可以很轻松地计算出拓扑排序，它返回一个顶点 ID 列表。如果给定的图不是 DAG，则会发生错误。

results = g.topological_sorting(mode='out')
print('Topological sort of g (out):', *results)

Topological sort of g (out): 0 1 2 4 3 5

实际上，igraph.GraphBase.topological_sorting() 有两种模式，'out' 和 'in'。'out' 是默认模式，从入度为 0 的节点开始。反之，'in' 从出度为 0 的节点开始。要调用另一种模式，我们只需使用

results = g.topological_sorting(mode='in')
print('Topological sort of g (in):', *results)

Topological sort of g (in): 5 3 1 4 2 0

我们可以使用 igraph.Vertex.indegree() 来查找节点的入度。

for i in range(g.vcount()):
    print('degree of {}: {}'.format(i, g.vs[i].indegree()))

# %
# Finally, we can plot the graph to make the situation a little clearer.
# Just to change things up a bit, we use the matplotlib visualization mode
# inspired by `xkcd <https://xkcd.com/>_:
with plt.xkcd():
    fig, ax = plt.subplots(figsize=(5, 5))
    ig.plot(
        g,
        target=ax,
        layout='kk',
        vertex_size=25,
        edge_width=4,
        vertex_label=range(g.vcount()),
        vertex_color="white",
    )

degree of 0: 0
degree of 1: 1
degree of 2: 1
degree of 3: 2
degree of 4: 1
degree of 5: 2