Построение направленного мультиграфа (Python)

Question

Допустим, я получил один список, который представляет веса для соседних узлов. Мультиграф имеет форму гиперкуба. Узлы будут названы их координатами в виде двоичной строки.

Пример для n=3

bin_string = ['000', '100', '010', '001', '110', '101', '011', '111']
weights = [[-5, -13, -2], [16, -9], [-15, 2], [13, -13], [18], [-9], [18]]

Я хочу построить словарь из обоих списков следующим образом: мы начинаем с 000 и иметь ребра для всех узлов с еще одним 1 в обратном лексикографическом порядке (как в bin_string). Второй узел будет 100 (еще один 1, самый большой первый), и этот узел может иметь ребра для всех узлов, опять же, еще один 1. Таким образом, словарь будет выглядеть так:

d = { '000':{'100':-5, '010':-13, '001':-2},
      '100':{'110':16, '101':-9},
      '010':{'110':-15, '011':2},
      '001':{'101':13, '011':-13},
      '110':{'111':18},
      '101':{'111':-9},
      '011':{'111':18}
     }

У меня есть гиперкубы со всеми видами измерений, и я уже могу генерировать bin_string в зависимости от размера. Но как мне жениться bin_string а также weights в один словарь?

Answer 1

Словари Python не имеют определенного порядка, поэтому вам нужно использовать collections.OrderedDict, Вот пример:

from collections import OrderedDict

def one_more_one(s):
    for i, digit in enumerate(s):
        if digit == '0':
            yield s[:i] + '1' + s[i+1:]

bin_string = ['000', '100', '010', '001', '110', '101', '011', '111']
weights = [[-5, -13, -2], [16, -9], [-15, 2], [13, -13], [18], [-9], [18]]

d = OrderedDict()
for node, weight in zip(bin_string, weights):
    d[node] = OrderedDict(zip(one_more_one(node), weight))

Вот, one_more_one является генератором, дающим соседей узла, у которых есть "еще один". Это дает их в обратном лексикографическом порядке.

Если порядок не важен, вы можете просто использовать обычные python dicts. Вы можете восстановить нормальный dict написав:

{k:dict(v) for k,v in d.iteritems()}

который дает

{'000': {'001': -2, '010': -13, '100': -5},
 '001': {'011': -13, '101': 13},
 '010': {'011': 2, '110': -15},
 '011': {'111': 18},
 '100': {'101': -9, '110': 16},
 '101': {'111': -9},
 '110': {'111': 18}}