python - 从有向图创建无向图

Question

我太困惑了，想不出正确的方法:

我有这个有向图:

并且有两个字典，显示传出和传入的分数

graph_to = {'a':{'b':2,'c':3},'b':{'a':1,'d':4}}
graph_from = {'a':{'b':1},'b':{'a':2},'c':{'a':3},'d':{'b':4}}

例如，在 graph_to 中，节点 a 以得分 2 转到节点 b 并转到节点 c得分 3；在 graph_from 中，节点 a 从节点 b 接收分数 1。

我想创建无向图，以便将两个节点之间的分数相加。它应该变成这个字典:

graph = {
    'a':{'b':3,'c':3},
    'b':{'a':3,'d':4},
    'c':{'a':3},
    'd':{'b':4}
}

Answer 1

你可以试着做一个 collections.defaultdict()的 collections.Counter()对象，并在迭代两个图形字典时求和边数:

from collections import defaultdict
from collections import Counter
from pprint import pprint

graph_to = {'a':{'b':2,'c':3},'b':{'a':1,'d':4}}
graph_from = {'a':{'b':1},'b':{'a':2},'c':{'a':3},'d':{'b':4}}

undirected_graph = defaultdict(Counter)

def sum_edges(graph, result):
    for node, edges in graph.items():
        for edge in edges:
            result[node][edge] += edges[edge]

sum_edges(graph_to, undirected_graph)
sum_edges(graph_from, undirected_graph)

pprint(undirected_graph)

给出:

defaultdict(<class 'collections.Counter'>,
            {'a': Counter({'b': 3, 'c': 3}),
             'b': Counter({'d': 4, 'a': 3}),
             'c': Counter({'a': 3}),
             'd': Counter({'b': 4})})

注意 Counter 和defaultdict 是dict 的子类，因此您可以将它们视为正常字典。

如果你真的想要在最终的无向图中使用普通字典，你可以使用以下任一字典理解:

dict((k, dict(v)) for k, v in undirected_graph.items())
# {'a': {'b': 3, 'c': 3}, 'b': {'a': 3, 'd': 4}, 'c': {'a': 3}, 'd': {'b': 4}}

{k: dict(v) for k, v in undirected_graph.items()}
# {'a': {'b': 3, 'c': 3}, 'b': {'a': 3, 'd': 4}, 'c': {'a': 3}, 'd': {'b': 4}}

此外，您还可以使用dict.update()这里重构sum_edges():

def sum_edges(graph, result):
    for node, edges in graph.items():
        result[node].update(edges)