By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
449,309 Members | 2,035 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 449,309 IT Pros & Developers. It's quick & easy.

More user feedback on Sets.py

P: n/a
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?
Raymond Hettinger
Jul 18 '05 #1
Share this Question
Share on Google+
5 Replies


P: n/a
In article <1h****************@nwrdny03.gnilink.net>,
"Raymond Hettinger" <vz******@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?


I've certainly been doing some implementations of graph algorithms in
which the graph vertices represent sets of objects (but I've been
representing them as bitvectors since I am still running 2.2 and don't
have Sets.py yet). It would be awkward if I couldn't have sets of
vertices...but I don't see any reason for the sets in these applications
to ever be mutable, so automatic conversion to immutability doesn't seem
to be critical.

For something concrete (that I thought about doing recently but haven't
actually done): conversion of NFA to DFA and then state minimization of
the resulting DFA. The converted DFA's states are sets of states of the
NFA, and the state minimization involves sets of DFA states.

--
David Eppstein http://www.ics.uci.edu/~eppstein/
Univ. of California, Irvine, School of Information & Computer Science
Jul 18 '05 #2

P: n/a
[Raymond Hettinger]
If the need has arisen, is the current design sufficient?

[David Eppstein] I've certainly been doing some implementations of graph algorithms in
which the graph vertices represent sets of objects (but I've been
representing them as bitvectors since I am still running 2.2 and don't
have Sets.py yet).
I have added some backwards compatability code so that Sets.py will run
Python 2.2. Please give it a test drive:

http://cvs.sourceforge.net/viewcvs.p...n&rev=1.44.8.4

It would be awkward if I couldn't have sets of
vertices...but I don't see any reason for the sets in these applications
to ever be mutable, so automatic conversion to immutability doesn't seem
to be critical.
That was useful feedback.

For something concrete (that I thought about doing recently but haven't
actually done): conversion of NFA to DFA and then state minimization of
the resulting DFA. The converted DFA's states are sets of states of the
NFA, and the state minimization involves sets of DFA states.


That would be a perfect way to test drive the sets module.
Raymond
Jul 18 '05 #3

P: n/a
In article <Rx*****************@nwrdny02.gnilink.net>,
"Raymond Hettinger" <vz******@verizon.net> wrote:
I have added some backwards compatability code so that Sets.py will run
Python 2.2. Please give it a test drive:

http://cvs.sourceforge.net/viewcvs.p...ist/src/Lib/se
ts.py?content-type=text%2Fplain&rev=1.44.8.4


Thanks! Doesn't quite work out of the box, though...

Python 2.2 (#1, 07/14/02, 23:25:09)
[GCC Apple cpp-precomp 6.14] on darwin
Type "help", "copyright", "credits" or "license" for more information.
import sets Traceback (most recent call last):
File "<stdin>", line 1, in ?
File "/usr/lib/python2.2/site-packages/sets.py", line 79, in ?
class BaseSet(object):
File "/usr/lib/python2.2/site-packages/sets.py", line 109, in BaseSet
def _repr(self, sorted=False):
NameError: name 'False' is not defined


Here's a patch:

*** sets.py Sun Nov 9 09:48:47 2003
--- /usr/lib/python2.2/site-packages/sets.py Sun Nov 9 11:09:35 2003
***************
*** 74,79 ****
--- 74,83 ----
if not predicate(x):
yield x

+ if 'True' not in globals():
+ globals()['True'] = not None
+ globals()['False'] = not True
+
__all__ = ['BaseSet', 'Set', 'ImmutableSet']

class BaseSet(object):

--
David Eppstein http://www.ics.uci.edu/~eppstein/
Univ. of California, Irvine, School of Information & Computer Science
Jul 18 '05 #4

P: n/a
I had a natural example of sets of sets of sets of sets today... I
wanted to explore the trees having n labeled items at their leaves
<http://www.research.att.com/projects/OEIS?Anum=A000311>.

Each edge of such a tree forms a bipartition of the set of leaves, so I
represented the tree as the set of its bipartitions. Each bipartition
is itself a set {S, U-S} where U is the set of all leaves and S is some
subset of U. So, each tree is represented as a set of sets of sets. I
ran some algorithms that involved sets of trees, so these algorithms
constructed sets of sets of sets of sets...

This was all relatively easy using sets.py (23 new lines added to the
code I was already using for exploring other combinatorial objects) and
would have been much more cumbersome if I had to represent sets
explicitly as bit vectors or dictionaries.

So, thanks for sets, and thanks for making it work under python 2.2!

--
David Eppstein http://www.ics.uci.edu/~eppstein/
Univ. of California, Irvine, School of Information & Computer Science
Jul 18 '05 #5

P: n/a
[Raymond]
I have added some backwards compatability code so that Sets.py will run
Python 2.2. Please give it a test drive:

http://cvs.sourceforge.net/viewcvs.p...ist/src/Lib/se
ts.py?content-type=text%2Fplain&rev=1.44.8.4

[Dave Eppstein] Thanks! Doesn't quite work out of the box, though...

Python 2.2 (#1, 07/14/02, 23:25:09)
[GCC Apple cpp-precomp 6.14] on darwin
Type "help", "copyright", "credits" or "license" for more information. import sets

Traceback (most recent call last):
File "<stdin>", line 1, in ?
File "/usr/lib/python2.2/site-packages/sets.py", line 79, in ?
class BaseSet(object):
File "/usr/lib/python2.2/site-packages/sets.py", line 109, in BaseSet
def _repr(self, sorted=False):
NameError: name 'False' is not defined


Okay, I've added code to make this run with older versions of Py2.2.

Still, it's worth downloading the bugfix release 2.2.3 which has
True/False in it and a number of important fixups.
Raymond Hettinger
Jul 18 '05 #6

This discussion thread is closed

Replies have been disabled for this discussion.