求无向图的度数

Question

我正在尝试找出一个无向图的度分布。我试过以下代码：

graph = { "a" : ["c"],
          "b" : ["c", "e"],
          "c" : ["a", "b", "d", "e"],
          "d" : ["c"],
          "e" : ["c", "b"],
          "f" : []
        }

def generate_edges(graph):
    edges = []
    for node in graph:
        for neighbour in graph[node]:
            edges.append((node, neighbour))

    return edges

print(generate_edges(graph))

我的输出结果是这样的：

[('c', 'a'), ('c', 'b'), ('c', 'd'), ('c', 'e'), ('b', 'c'), ('b', 'e'), ('a', 'c'), ('e', 'c'), ('e', 'b'), ('d', 'c')]

我想找出每个节点的度数，但我没有成功。我希望我的输出是 [1,2,2,0,1]，这是一个列表，列表的索引值从 0 到图中最大度数（在上面的图中，"c" 的最大度数是 4）。索引值表示具有相应度数的节点数量。（在上面的图中，有 1 个节点的度数是 0，有 2 个节点的度数是 1，还有 2 个节点的度数是 2，没有节点的度数是 3，最后有 1 个节点的度数是 4）。所以我需要的结果是 [1,2,2,0,1]。有没有人能帮我解决这个问题，不使用 NetworkX 呢？

Answer 1

你可以通过简单地查看每个元素的列表长度来找到每个节点的度数。

all_degrees = map(len, graph.values())

在你的情况下，这样做会得到每个节点的度数，但顺序可能和元素的顺序不一样。

[1, 4, 2, 2, 1, 0]

接下来就是在列表中进行频率统计。

from collections import defaultdict
freq = defaultdict(int)
for i in all_degrees:
    freq[i] += 1
print freq
Out: defaultdict(<type 'int'>, {0: 1, 1: 2, 2: 2, 4: 1})

正如预期的那样，freq现在会给出每个值的计数，你可以选择打印出来、添加到列表中等等。你可以直接打印字典freq的值，像这样：

print freq.values()

这样会返回你想要的列表[1, 2, 2, 0, 1]。或者你可以创建一个空列表，然后把值添加进去，像这样：

out = list()
for i in range(max(all_degrees)+1):
   out.append(freq[i])

同样会返回out = [1,2,2,0,1] - 这是你需要的输出。

Answer 2

还有一种使用 Counter 的解决方案：

from collections import Counter
a = Counter(map(len, graph.values())) # map with degree as key and number of nodes as value
out = [a[i] for i in range(max(a)+1)] # transform the map to a list

Answer 3

graph = { "a" : ["c"],
          "b" : ["c", "e"],
          "c" : ["a", "b", "d", "e"],
          "d" : ["c"],
          "e" : ["c", "b"],
          "f" : [] }

def max_length(x):
    return len(graph[x])

# Determine what index has the longest value
index = max(graph, key=max_length)
m = len(graph[index])

# Fill the list with `m` zeroes
out = [0 for x in range(m+1)]

for k in graph:
    l = len(graph[k])
    out[l]+=1

print(out)

输出结果是 [1, 2, 2, 0, 1]