重新索引网络（图形）边缘列表

Question

我这里的问题与语言无关，所以伪代码答案会更好。

假设我们有一个表示图形的边列表，并且这个边列表是经典的二维矩阵形式。我们还假设在这个边缘列表中，节点不是以连续的方式计算的：在生成的 adj 矩阵中，将有几个 raws 和充满零的列。这种情况的示例如下：

节点 1 节点 2
20 21
17 105
105 108
105 110
45 105
20 21

我们希望节点标签从 1 开始到 N=节点数结束。我们还想保留每个节点之间的顺序关系：在先前标记中具有索引 i 的节点

节点 1 节点 2
2 3
1 5
5 6
5 7
4 5
2 3

据我所知，这个任务可以通过两种方式实现：直接操作边缘列表或首先创建（稀疏）adj 矩阵，然后直接删除全为零的 raws/columns（的当然，后一种操作必须小心完成，因为直接删除完整的零行和列不会带来想要的结果：简单的例子简单的矩阵 [0 1 0 0] 将在图表中的删除过程后产生，只有一个自循环).

希望我把问题说清楚了。

干杯

Answer 1

我会获取所有标签，对它们进行排序并使用此排序列表将每个标签映射到一个 int

// Part 1 : Get all the labels and order them
S = Set<int>
for edge E in edge-list
    S.insert(E.begin) // This is just getting the node1 
    S.insert(E.end)   // and node2
L = List<int>
L.insert(S) // Just put everything that was in S in a list
sort(L)
// In your example, you would have L = [17,20,21,45,105,...]


// Part 2 : Create a renaming of the labels
M = map<int,int>
for(int i = 0; i<L.length(); ++i)
    M[L[i]] = i

// You have your renaming. Each label has now an integer mapped to it
// It has all the properties you asked

请注意，我的新标签是 0 索引的，如果您想要与您给出的示例相同的内容，只需执行 M[L[i]] = i+1

现在每次遇到标签，比如45，都可以调用M[45]获取新标签

Answer 2

如果您将图表作为 networkx 对象，您可以使用 networkx relabel nodes function

将图表的节点重新索引到 integer 标签

import networkx as nx
old_graph = nx.Graph()
reindexed_graph = nx.relabel.convert_node_labels_to_integers(old_graph, first_label=0, ordering='default') #first_label is the starting integer label, in this case zero

重新索引网络（图形）边缘列表

Re-indexing a network (graph) edge list

indexing

graph

pseudocode

networkx

graph-algorithm