construct graph from python set type.

Question

The short question, is there an off the self function to make a graph from a collection of python sets? The longer question: I have several python sets. They each overlap or some are sub sets of others. I would like to make a graph (as in nodes and edges) nodes are the elements in the sets. The edges are intersection of the sets with weighted by number of elements in the intersection of the sets. There are several graphing packages for python. (NetworkX, igraph,...) I am not familiar with the use of any of them. Will any of them make a graph directly from a list of sets ie, MakeGraphfromSets(alistofsets) If not do you know of an example of how to take the list of sets to define the edges. It actually looks like it might be straight forward but an example is always good to have.

Answer 1

It's not too hard to code yourself:

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

This function numbers each set with its index within sets. We do this because dict keys must be immutable, which is true of integers but not sets.

Here's an example of how to use this function, and it's output:

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

Answer 2

 

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

OUTPUT:

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