DjangoBB LoFi version

Полная версия: Создать словарь смежности.

Начало » Python для новичков » Создать словарь смежности.

kozlo22

Янв. 16, 2014 23:03:14

Задача такая: дана строка, необходимо создать словарь смежности и обойти каждый элемент графа, начиная с первого и заканчивая им.
Исходная строка:

'12,28,87,71,13,14,34,35,45,46,63,65'

Результат:

'1365417821'

или

'12871135641'

Пока что у меня не получается создать словарь смежности.
Вот что имеется:

def adjaс_dict(lst):
    '''Создает словарь смежности
    lst - список вершин ["12", "14", "65"]'''
    d = {}
    for i in lst:
        if i[0] not in d:
            d.update({i[0]: i[1]})
        elif i[0] in d:
            d.update({i[0]: (list(d[i[0]]) + [i[1]])})
    return d
def nodes(lst):
    '''Создает список всех узлов графа'''
    tmp = []
    for i in lst:
        for j in i:
            if j not in tmp:
                tmp.append(j)
    tmp.sort()
    return tmp
def check_nodes(lst, vertex_lst, d_ad):
    '''Добавляет в словарь смежности недостающих узлов
    lst - список всех узлов графа; vertex_lst - список вершин;
    d - словарь смежности'''
    for i in lst:
        if i not in d_ad:
            for j in vertex_lst:
                if i in j:
                    d_ad.update({j[1]:j[0]})
    return d_ad
s = '12,28,87,71,13,14,34,35,45,46,63,65'
v_lst = s.split(',')
d = adjaс_dict(v_lst)
tmp = nodes(v_lst)
d = check_nodes(tmp, v_lst, d)

В результате получится словарь вида:

['1', '2', '3', '4', '5', '6', '7', '8']
{'1': ['2', '3', '4'], '3': ['4', '5'], '2': '8', '5': '6', '4': ['5', '6'], '7': '1', '6': ['3', '5'], '8': '7'}

Проблема в том, что значение элемента

d['5']

должно быть

['6', '4', '3']

, а не просто ‘6’.

bismigalis

Янв. 17, 2014 19:36:46

lst = [(1,2),(2,8),(8,7),(7,1),(1,3),(1,4),(3,4),(3,5),(4,5),(4,6),(6,3),(6,5)]
#
def fn1(a, item):
    a.setdefault(item[0], []).append(item[1])
    a.setdefault(item[1], []).append(item[0])
    return a
#
print reduce(fn1, lst, {})

kozlo22

Янв. 17, 2014 22:33:39

bismigalis
не то. Смотрите, мне надо просто дополнить словарь недостающими узлами.
Сначала мы добавляем узлы по правилу: первый элемент - ключ, второй - значение, если значений для данного ключа больше одного, то добавляем элементы в список.
После того как первичный словарь создан, то проверяем его на отсутствие узлов. В данном случаем в первичном словаре будет отсутствовать узел ‘5’. Значит это надо восполнить следующим образом, теперь тех элементов, которых нет в словаре добавляем по правилу: второй элемент - ключ, первый значение, если их больше одного, то добавляем в список.

bismigalis

Янв. 17, 2014 23:50:56

ага вижу, ну теперь понятней

тогда так

lst = [(1,2),(2,8),(8,7),(7,1),(1,3),(1,4),(3,4),(3,5),(4,5),(4,6),(6,3),(6,5)]
#
def fn1(acc, item):
    m, s = acc
    k, v = item
    m.setdefault(k, []).append(v)
    s.add(v)
    return acc
#
def fn2(acc, item):
    m, diff = acc
    k, v = reversed(item)
    if k in diff:
        m.setdefault(k, []).append(v)
    return acc
#
m, s = reduce(fn1, lst, ({}, set()))
diff = s - set(m)
res, _ = reduce(fn2, lst, (m, diff))
print res