函数如何对节点进行排序？

Question

我有一个有向图。节点有一个字符串标签。我想为每个节点分配一个整数值。节点的编号从 1, ..., n 应该考虑到依赖性。示例：

给定节点n1、n2、n3和n4。依赖关系为 n1->n2、n1-> n3、n2 -> n3 和 n3 -> n4。前人应该假设一个更小的整数值。

n1 = 1

n2 = 2，因为 n3 有 n2 和 n1 作为前辈

n3 = 3，n3 不能为 2，因为 n2 是 n3 的另一个前身

n4=4

我尝试使用来自networkx的convert_node_labels_to_integers函数。我选择了排序=“已排序”。但是，我不明白它是如何排序的。您知道一种无需重新标记的编号方法吗？也许类似于为每个节点插入索引引用？

Answer 1

您所描述的称为拓扑排序。通过函数

nx.topological_sort

在 Networkx 中可用。 文档在这里。请注意，

topological_sort

返回一组有序的节点 ID；您必须自己重新标记节点。