Home Original page

More user feedback on Sets.py

David Eppstein eppstein at ics.uci.edu
Sun Nov 9 18:02:39 EST 2003 
In article <1hSqb.1167$bQ3.696 at nwrdny03.gnilink.net>,
 "Raymond Hettinger" <vze4rx4y at verizon.net> wrote:

> For Py2.4, I'm working on a C implementation of Sets.py with the possibility 
> of
> having a set() type as a builtin.  There is a question as whether the current
> design for set of sets has been useful.
> 
> To support sets-of-sets, the current design includes an automatic conversion 
> to
> an immutable set class.  The original use case was for implementing graph
> algorithms.
> 
> Has anyone used sets-of-sets to solve any non-toy problems?
> Has anyone successfully applied sets-of-sets to graph algorithms?
> If the need has arisen, is the current design sufficient?

Now that I have sets working, here's a response to the original question.

I think, now that we have sets, the natural update to Guido's graph 
representation essay <http://www.python.org/doc/essays/graphs.html>
is to use the following representation of a graph:
Represent G as a dictionary, where the keys are vertices and the values 
are sets of the (outgoing) neighbors of each vertex.
This representation allows the following operations to be performed 
efficiently:

    - iterate through all vertices in G:
      for v in G: suite

    - iterate through all neighbors of a vertex v:
      for w in G[v]: suite

    - test whether a vertex belongs to G:
      if v in G: suite

    - test whether an edge belongs to G:
      if w in G[v]: suite

If one uses this representation, then any time one has sets as vertices, 
one will have sets of sets in the representation.  No automatic coercion 
from mutable to immutable seems to be necessary here, or in any graph 
algorithm using this representation -- if you are going to use sets as 
vertices, they have to already be immutable.

Here's a quick example involving sets of sets of sets:

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

-- 
David Eppstein                      http://www.ics.uci.edu/~eppstein/
Univ. of California, Irvine, School of Information & Computer Science
More information about the Python-list mailing list