从Python集合类型构建图形

Question

简短的问题是：有没有现成的函数可以用来从一组Python集合中制作图形？

长一点的问题是：我有几个Python集合，它们之间有重叠，或者有些是其他集合的子集。我想制作一个图（也就是节点和边的结构），节点是集合中的元素，边则是集合之间的交集，边的权重是交集中元素的数量。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中的位置。我们这样做是因为字典的键必须是不可变的，整数是不可变的，但集合（sets）就不是。

下面是如何使用这个函数的一个例子，以及它的输出结果：

>>> 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)]}