python - 给定列表创建无向图

Question

我有一个列表:

entry=['A','B','C','null','B','A','D','null','E','F']

彼此相邻的字母(顶点)形成一条边。 'null' 是分隔符。

每条边的权重为 1。边 (A,B) 的权重为 2，因为它出现了两次。

为了形象化，上面的列表将是这个图表:

我想创建一个字典，类似于邻接表。

dict= {
'A':{'B':2,'D',1},
'B':{'A':2,'C':1},
'C':{'B':1},
'D':{'A':1},
'E':{'F':1},
'F':{'E':1}
}

第一个键是顶点，第二个键是相邻顶点及其权重值。

如何得出上图。如果有任何其他更好的方式来表示上图，我将不胜感激。

Answer 1

一个解决方案是 reduce您的 entry 列表作为 reduce(没有累加器)一次查看 2 个相邻元素:

from functools import reduce

graph = {}

def add_edge(u, v):
    if u != 'null' and v != 'null':
        if u in graph:
            graph[u][v] = graph[u].get(v, 0) + 1
        else:
            graph[u] = {v: 1}
        if v in graph:
            graph[v][u] = graph[v].get(u, 0) + 1
        else:
            graph[v] = {u: 1}
    return v

entry = ['A','B','C','null','B','A','D','null','E','F']
reduce(add_edge, entry)

print(graph)
# {'B': {'A': 2, 'C': 1}, 'E': {'F': 1}, 'F': {'E': 1}, 'C': {'B': 1}, 'A': {'B': 2, 'D': 1}, 'D': {'A': 1}}

编辑:

一种“更纯粹”的归约方式是将相邻元素压缩在一起，然后使用初始化器归约:

def add_edge(graph, edges):
    u, v = edges
    if u != 'null' and v != 'null':
        # ... same thing as before
    return graph

entry = ['A','B','C','null','B','A','D','null','E','F']
graph = reduce(add_edge, zip(entry[:-1], entry[1:]), {})