[Python-checkins] python/nondist/sandbox/setobj cube.py,NONE,1.1

[rhettinger at users.sourceforge.net]

Update of /cvsroot/python/python/nondist/sandbox/setobj
In directory sc8-pr-cvs1:/tmp/cvs-serv25907

Added Files:
	cube.py 
Log Message:
Demo application of sets of sets by David Eppstein.

Included in the sandbox to demonstrate the effectiveness of setobject.c
for implementing graph algorithms.



--- NEW FILE: cube.py ---
try:
    from set import frozenset as ImmutableSet
except ImportError:
    from sets import ImmutableSet

def powerset(U):
    """Generates all subsets of a set or sequence U."""
    U = iter(U)
    try:
        x = ImmutableSet([U.next()])
        for S in powerset(U):
            yield S
            yield S | x
    except StopIteration:
        yield ImmutableSet()

def cube(n):
    """Graph of n-dimensional hypercube."""
    singletons = [ImmutableSet([x]) for x in range(n)]
    return dict([(x, ImmutableSet([x^s for s in singletons]))
                 for x in powerset(range(n))])

def linegraph(G):
    """Graph, the vertices of which are edges of G,
    with two vertices being adjacent iff the corresponding
    edges share a vertex."""
    L = {}
    for x in G:
        for y in G[x]:
            nx = [ImmutableSet([x,z]) for z in G[x] if z != y]
            ny = [ImmutableSet([y,z]) for z in G[y] if z != x]
            L[ImmutableSet([x,y])] = ImmutableSet(nx+ny)
    return L

cuboctahedron = linegraph(cube(3))
print cuboctahedron