Networkx Graph 获取每个节点的序列号

Question

我正在使用 networkx 生成有向图，如下所示。我如何对节点进行编号，以便它遵循从最低到最大的序列，并且当节点拆分为多个节点时，所有以下节点都获得相同的序列号。反过来，它也可以将多个节点合并为一个节点

当前图表

未来图

Answer 1

你想做的是"rank nodes in directed acyclic graph".

Networkx 没有内置函数（据我所知），但可以通过简单的算法完成：

如果节点没有前任，则其排名设置为 1。
如果节点有前任，其等级设置为“最大前任等级”加 1

以下是 Networkx 图的示例：

import networkx as nx

# Create graph
G = nx.DiGraph()
G.add_edges_from([
    ('a', 'b'),
    ('b', 'c'),
    ('d', 'e'),
    ('e', 'f'),
    ('f', 'g'),
    ('g', 'h'),
    ('c', 'h'),
    ('i', 'f'),
    ('h', 'j'),
    ('j', 'k'),
])

让我们把它画成你的第一张图（我建议你使用 Graphviz 布局）：

nx.draw(
    G,
    pos=nx.nx_agraph.graphviz_layout(G, prog='dot'),
    node_color='#FF0000'
)

然后我们使用topological sorting进行适当的DAG迭代并使用上层算法：

for node in nx.topological_sort(G):
    if not len(list(G.predecessors(node))):
        G.nodes[node]['level'] = 1
    else:
        G.nodes[node]['level'] = max(
            G.nodes[n]['level']
            for n in G.predecessors(node)
        ) + 1

然后我们将在"level"变量

中得到我们的排名数字

>>> G.nodes.data('level')

NodeDataView({'i': 1, 'a': 1, 'g': 4, 'b': 2, 'd': 1, 'j': 6, 'k': 7, 'c': 3, 'e': 2, 'h': 5, 'f': 3}, data='level')

最后我们使用节点等级作为标签绘制图形：

nx.draw(
    G,
    pos=nx.nx_agraph.graphviz_layout(G, prog='dot'),
    node_color='#FF0000',
    labels={n: G.nodes[n]['level'] for n in G.nodes}
)

这是想要的结果：

Networkx Graph 获取每个节点的序列号

Networkx Graph get sequence number for each node

python

networkx