построить граф из набора типов Python

Question

Короткий вопрос, есть ли функция self для создания графа из набора наборов питонов? Более длинный вопрос: у меня есть несколько наборов питонов. Каждый из них перекрывается, или некоторые являются подмножествами других. Я хотел бы сделать граф (как в узлах и ребрах) узлы являются элементами в наборах. Ребра являются пересечением множеств с взвешенным числом элементов в пересечении множеств. Есть несколько графических пакетов для Python. (NetworkX, igraph, ...) Я не знаком с использованием любого из них. Будет ли кто-нибудь из них составлять график непосредственно из списка наборов, т.е. MakeGraphfromSets (alistofsets) Если нет, то знаете ли вы пример того, как взять список множеств для определения ребер. На самом деле это выглядит так, будто это может быть просто, но пример всегда полезен.

Answer 1

def MakeGraphfromSets(sets):
    egs = []
    l = len(sets)
    for i in range(l):
        for j in range(i,l):
            w = sets[i].intersection(sets[j])
            egs.append((i,j,len(w)))
    return egs

# (source set index,destination set index,length of intersection)

sets = [set([1,2,3]), set([2,3,4]), set([4,2])]

edges = MakeGraphfromSets(sets)

for e in edges:
    print e

ВЫВОД:

(0, 0, 3)
(0, 1, 2)
(0, 2, 1)
(1, 1, 3)
(1, 2, 2)
(2, 2, 2)

Answer 2

Кодировать не сложно:

def intersection_graph(sets):
    adjacency_list = {}
    for i, s1 in enumerate(sets):
        for j, s2 in enumerate(sets):
            if j == i:
                continue
            try:
                lst = adjacency_list[i]
            except KeyError:
                adjacency_list[i] = lst = []
            weight = len(s1.intersection(s2))
            lst.append( (j, weight) )
    return adjacency_list

Эта функция нумерует каждый набор с индексом в пределах sets. Мы делаем это потому, что ключи dict должны быть неизменяемыми, что верно для целых чисел, но не для множеств.

Вот пример использования этой функции и ее вывод:

>>> sets = [set([1,2,3]), set([2,3,4]), set([4,2])]
>>> intersection_graph(sets)
{0: [(1, 2), (2, 1)], 1: [(0, 2), (2, 2)], 2: [(0, 1), (1, 2)]}