Re: [sage-devel] Re: Scary things in Sage's Digraphs
On Sun, Jul 25, 2010 at 6:50 PM, Robert Miller r...@rlmiller.org wrote: On Sun, Jul 25, 2010 at 8:10 PM, Carl Witty carl.wi...@gmail.com wrote: You seem to want to make the vertex dictionary respect the equivalence relation defined by Sage equality. If so, you're going to be in trouble, since Sage equality actually is not an equivalence relation: It gets worse: sage: a = Set([1,2,3]) sage: b = Set([2,3,4]) sage: a b True sage: b a False sage: b a True sage: a b False Let's take a look at Sage's implementation of comparison: sage: a.__cmp__?? ... if isinstance(other, Set_object_enumerated): if self.set() == other.set(): return 0 return -1 else: return Set_object.__cmp__(self, other) Aduu! If it is not true that a == b, then a b. Not good. I would like to ask, since obviously nobody cares about doing comparisons with Sage sets at the moment... We obviously need to define what it means for a b and a b for Sage Sets. Does anyone mind if we do this so that instead of meaning subset, and getting a bad ordering with respect to sorting lists, can we make give a lexicographic ordering? I will gladly do all the work, including implementing an is_subset method. That way, if you like working with sets themselves and you want to mean subset, simply use Python sets. Or if you are Chris Godsil, e.g., and like to be able to consistently sort sets because you use them as vertices for graphs, use Sage Sets. I think this is the best solution we can get to this problem... -- Robert L. Miller http://www.rlmiller.org/ -- To post to this group, send an email to sage-devel@googlegroups.com To unsubscribe from this group, send an email to sage-devel+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/sage-devel URL: http://www.sagemath.org
Re: [sage-devel] Re: Scary things in Sage's Digraphs
On Tue, Aug 3, 2010 at 10:33 AM, Robert Miller r...@rlmiller.org wrote: On Sun, Jul 25, 2010 at 6:50 PM, Robert Miller r...@rlmiller.org wrote: On Sun, Jul 25, 2010 at 8:10 PM, Carl Witty carl.wi...@gmail.com wrote: You seem to want to make the vertex dictionary respect the equivalence relation defined by Sage equality. If so, you're going to be in trouble, since Sage equality actually is not an equivalence relation: It gets worse: sage: a = Set([1,2,3]) sage: b = Set([2,3,4]) sage: a b True sage: b a False sage: b a True sage: a b False Let's take a look at Sage's implementation of comparison: sage: a.__cmp__?? ... if isinstance(other, Set_object_enumerated): if self.set() == other.set(): return 0 return -1 else: return Set_object.__cmp__(self, other) Aduu! If it is not true that a == b, then a b. Not good. I would like to ask, since obviously nobody cares about doing comparisons with Sage sets at the moment... We obviously need to define what it means for a b and a b for Sage Sets. Does anyone mind if we do this so that instead of meaning subset, and getting a bad ordering with respect to sorting lists, can we make give a lexicographic ordering? I will gladly do all the work, including implementing an is_subset method. +1It makes no sense for to mean subset because should be a total order. If you want to check for subsets we should use a method like in python: sage: a = set([1,2,3]) sage: b = set([2,3,4]) sage: a.issubset(b) False sage: b.issubset(a) False sage: a.issubset(b.union(a)) True I don't like issubset as the method name, and would prefer is_subset, personally. That way, if you like working with sets themselves and you want to mean subset, simply use Python sets. Yep. Or if you are Chris Godsil, e.g., and like to be able to consistently sort sets because you use them as vertices for graphs, use Sage Sets. I think this is the best solution we can get to this problem... William -- To post to this group, send an email to sage-devel@googlegroups.com To unsubscribe from this group, send an email to sage-devel+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/sage-devel URL: http://www.sagemath.org
Re: [sage-devel] Re: Scary things in Sage's Digraphs
On Tue, Aug 3, 2010 at 2:29 PM, William Stein wst...@gmail.com wrote: +1 It makes no sense for to mean subset because should be a total order. If you want to check for subsets we should use a method like in python: sage: a = set([1,2,3]) sage: b = set([2,3,4]) sage: a.issubset(b) False sage: b.issubset(a) False sage: a.issubset(b.union(a)) True I don't like issubset as the method name, and would prefer is_subset, personally. http://trac.sagemath.org/sage_trac/ticket/9677 needs a review... -- Robert L. Miller http://www.rlmiller.org/ -- To post to this group, send an email to sage-devel@googlegroups.com To unsubscribe from this group, send an email to sage-devel+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/sage-devel URL: http://www.sagemath.org
Re: [sage-devel] Re: Scary things in Sage's Digraphs
See trac #9610 for a patch which fixes this issue. -- Robert L. Miller http://www.rlmiller.org/ -- To post to this group, send an email to sage-devel@googlegroups.com To unsubscribe from this group, send an email to sage-devel+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/sage-devel URL: http://www.sagemath.org
Re: [sage-devel] Re: Scary things in Sage's Digraphs
Nathann,
Using the following instead fixes the problem:
g.add_edges( (Mod(i,n),Mod(i+j,n)) for i in range(n) for j in range(1,k+1) )
This is more consistent, since we are actually using the same vertex
objects. However, that should just work, right? Why doesn't it?
This is coming from the code around line 1000 of c_graph, which goes
from vertex labels to ints and back. The IntegerMod case was not in
mind when this code was written. The real problem is that when the
Python int 0 gets passed to get_vertex, it does not add the entry to
the translation dictionary. The idea being that it would be more
efficient for the majority of graphs, which only use [0, 1, ..., n-1]
as labels, going through dictionaries a bunch would be a waste.
However, when the IntegerMod 0 gets passed in, it does not find an
equal object in the dict, and since it is not one of {int, long,
Integer}, it assigns a new int in the translation dictionary for it.
So that's what's happening, what do people think about what we should
do about this? Technically the input is a bit fuzzy, but this raises
the question of how many other objects are there which will pass the
test int(0) == IntegerMod(0, 20)... I am very reluctant to support
adding all the labels to the dicts, unless someone can show that there
really isn't any overhead there...
--
Robert L. Miller
http://www.rlmiller.org/
--
To post to this group, send an email to sage-devel@googlegroups.com
To unsubscribe from this group, send an email to
sage-devel+unsubscr...@googlegroups.com
For more options, visit this group at http://groups.google.com/group/sage-devel
URL: http://www.sagemath.org
Re: [sage-devel] Re: Scary things in Sage's Digraphs
Hello !!!
This is coming from the code around line 1000 of c_graph, which goes
from vertex labels to ints and back. The IntegerMod case was not in
mind when this code was written. The real problem is that when the
Python int 0 gets passed to get_vertex, it does not add the entry to
the translation dictionary. The idea being that it would be more
efficient for the majority of graphs, which only use [0, 1, ..., n-1]
as labels, going through dictionaries a bunch would be a waste.
However, when the IntegerMod 0 gets passed in, it does not find an
equal object in the dict, and since it is not one of {int, long,
Integer}, it assigns a new int in the translation dictionary for it.
So that's what's happening, what do people think about what we should
do about this? Technically the input is a bit fuzzy, but this raises
the question of how many other objects are there which will pass the
test int(0) == IntegerMod(0, 20)... I am very reluctant to support
adding all the labels to the dicts, unless someone can show that there
really isn't any overhead there...
H.. I would not want to see any loss of performance because of
such matters either, I think we quite agree on this point..
I understood from your explanation why Mod(1,n) is considered
different from 0, and it is to me the correct behaviour... But what
about this
g has 21 vertices
len(g.vertices) == 20 ?
Sorry if you answered already ! :-)
Nathann
--
To post to this group, send an email to sage-devel@googlegroups.com
To unsubscribe from this group, send an email to
sage-devel+unsubscr...@googlegroups.com
For more options, visit this group at http://groups.google.com/group/sage-devel
URL: http://www.sagemath.org
Re: [sage-devel] Re: Scary things in Sage's Digraphs
Nathann,
I understood from your explanation why Mod(1,n) is considered
different from 0, and it is to me the correct behaviour... But what
about this
g has 21 vertices
len(g.vertices) == 20 ?
Sorry if you answered already ! :-)
I think the information was there, but I was not very clear. It is
better if you just look at the code:
{{{
cdef int get_vertex(object u, dict vertex_ints, dict vertex_labels,
CGraph G) except ? -2:
if u in vertex_ints:
return vertex_ints[u]
if (not isinstance(u, (int, long, Integer)) or
u 0 or u = G.active_vertices.size or
u in vertex_labels):
return -1
return u
}}}
When int(0) is input, it returns 0. When Mod(0, 20) is input, however,
it returns -1, meaning that the object is not yet in the translation
dictionaries (since the second block only tests for three types of
integer). So when int(0) is input to check_vertex(), nothing gets
added to the dictionaries. However, when Mod(0, 20) is input, it does
add an entry to the dicts, and since 0 is already taken up (as defined
in a bitset of which ones are used), it gets a different int. This is
how we get two zeros in the vertex dicts.
It is not clear to me how to solve this problem. One could add
IntegerMod to the list of types to check, but that's a slippery
slope... One very silly option is to simply make the behavior of
adding Python ints and IntegerMods at the same time undefined, but
there *must* be a better fix...
--
Robert L. Miller
http://www.rlmiller.org/
--
To post to this group, send an email to sage-devel@googlegroups.com
To unsubscribe from this group, send an email to
sage-devel+unsubscr...@googlegroups.com
For more options, visit this group at http://groups.google.com/group/sage-devel
URL: http://www.sagemath.org
Re: [sage-devel] Re: Scary things in Sage's Digraphs
Nononon, I understood why there are two copies of what appears to
be a zero, and I think it's fine like that !
My question was about the number of vertices as remembered by the graph :
in one case, it says 21, but g.vertices() is only long of 20 elements.
Why aren't there two zeroes in g.vertices() ? I would expect to see
one 0, which is the integer, and one zero which is actually the member
of Z/20Z !
Sorry for this misunderstanding :-)
Nathann
On 25 July 2010 20:49, Robert Miller r...@rlmiller.org wrote:
Nathann,
I understood from your explanation why Mod(1,n) is considered
different from 0, and it is to me the correct behaviour... But what
about this
g has 21 vertices
len(g.vertices) == 20 ?
Sorry if you answered already ! :-)
I think the information was there, but I was not very clear. It is
better if you just look at the code:
{{{
cdef int get_vertex(object u, dict vertex_ints, dict vertex_labels,
CGraph G) except ? -2:
if u in vertex_ints:
return vertex_ints[u]
if (not isinstance(u, (int, long, Integer)) or
u 0 or u = G.active_vertices.size or
u in vertex_labels):
return -1
return u
}}}
When int(0) is input, it returns 0. When Mod(0, 20) is input, however,
it returns -1, meaning that the object is not yet in the translation
dictionaries (since the second block only tests for three types of
integer). So when int(0) is input to check_vertex(), nothing gets
added to the dictionaries. However, when Mod(0, 20) is input, it does
add an entry to the dicts, and since 0 is already taken up (as defined
in a bitset of which ones are used), it gets a different int. This is
how we get two zeros in the vertex dicts.
It is not clear to me how to solve this problem. One could add
IntegerMod to the list of types to check, but that's a slippery
slope... One very silly option is to simply make the behavior of
adding Python ints and IntegerMods at the same time undefined, but
there *must* be a better fix...
--
Robert L. Miller
http://www.rlmiller.org/
--
To post to this group, send an email to sage-devel@googlegroups.com
To unsubscribe from this group, send an email to
sage-devel+unsubscr...@googlegroups.com
For more options, visit this group at
http://groups.google.com/group/sage-devel
URL: http://www.sagemath.org
--
To post to this group, send an email to sage-devel@googlegroups.com
To unsubscribe from this group, send an email to
sage-devel+unsubscr...@googlegroups.com
For more options, visit this group at http://groups.google.com/group/sage-devel
URL: http://www.sagemath.org
Re: [sage-devel] Re: Scary things in Sage's Digraphs
On Sun, Jul 25, 2010 at 2:01 PM, Nathann Cohen nathann.co...@gmail.com wrote:
Nononon, I understood why there are two copies of what appears to
be a zero, and I think it's fine like that !
This is definitely *not* fine, since we have
sage: int(0) == Mod(0, 20)
True
As input, the underlying C graph ends up corrupted (see below for
details). Since they are equal, Sage's graphs should treat them as
equal and they do not. Bug.
To belabor the point for clarity:
When you call g.vertices(), it calls iterator_verts in c_graph.pyx:
{{{
cdef int i
cdef object v
if verts is None:
S = set(self.vertex_ints.iterkeys())
for i from 0 = i (CGraphself._cg).active_vertices.size:
if (i not in self.vertex_labels and
bitset_in((CGraphself._cg).active_vertices, i)):
S.add(i)
return iter(S)
}}}
At this point we have:
{{{
active_vertices == 1000
vertex_ints == {0: 20, 1: 1, 2: 2, 3: 3, 4: 4, 5: 5, 6: 6, 7: 7, 8: 8,
9: 9, 10: 10, 11: 11, 12: 12, 13: 13, 14: 14, 15: 15, 16: 16, 17: 17,
18: 18, 19: 19}
vertex_labels == {1: 1, 2: 2, 3: 3, 4: 4, 5: 5, 6: 6, 7: 7, 8: 8, 9:
9, 10: 10, 11: 11, 12: 12, 13: 13, 14: 14, 15: 15, 16: 16, 17: 17, 18:
18, 19: 19, 20: 0}
}}}
Note that there are 21 bits in active_vertices, so C int 0 and C int
20 are both vertices according to that. That first zero in vertex_ints
is an IntegerMod, and the 20 it points to is a C int. Vice versa for
the 20: 0 entry in vertex_labels.
At first, the line {{{ S = set(self.vertex_ints.iterkeys()) }}}
creates a set of size twenty, containing twenty IntegerMod's, the set
{0, ..., 19}.
When i == 0 in the loop {{{ for i from 0 = i
(CGraphself._cg).active_vertices.size }}}, the inner branch
discovers that 0 should be added to S, but since S is a set, and
Mod(0, 20) is already in there, adding int(0) to it does nothing.
So as I said before, the problem is created by line 1084 (in
sage-4.5/4.5.1) of c_graph.pyx, namely:
{{{ if (not isinstance(u, (int, long, Integer)) or }}}
In fact this should check for any Sage object X for which {{{
Integer(Y) == X }}} is true for any Y.
I hope this better illustrates the problem, and I hope I've convinced
you that int(0) and Mod(0, 20) should *not* be considered distinct by
Sage graphs.
Sorry for this misunderstanding :-)
Nathann
A: Stop apologizing!
B: I'm sorry!
--
Robert L. Miller
http://www.rlmiller.org/
--
To post to this group, send an email to sage-devel@googlegroups.com
To unsubscribe from this group, send an email to
sage-devel+unsubscr...@googlegroups.com
For more options, visit this group at http://groups.google.com/group/sage-devel
URL: http://www.sagemath.org
Re: [sage-devel] Re: Scary things in Sage's Digraphs
On Sun, Jul 25, 2010 at 10:27 AM, Robert Miller r...@rlmiller.org wrote:
On Sun, Jul 25, 2010 at 2:01 PM, Nathann Cohen nathann.co...@gmail.com
wrote:
Nononon, I understood why there are two copies of what appears to
be a zero, and I think it's fine like that !
This is definitely *not* fine, since we have
sage: int(0) == Mod(0, 20)
True
You seem to want to make the vertex dictionary respect the equivalence
relation defined by Sage equality. If so, you're going to be in
trouble, since Sage equality actually is not an equivalence relation:
sage: 3 == Mod(7, 4)
True
sage: 3 == Mod(8, 5)
True
sage: Mod(7, 4) == Mod(8, 5)
False
This means that mixing Sage objects of different parents as elements
of a single set or keys of a single dictionary is asking for trouble;
in general, it cannot work (or at least we haven't figured out a way
to make it work). (As long as you stick to a single parent you should
be fine.)
So as I said before, the problem is created by line 1084 (in
sage-4.5/4.5.1) of c_graph.pyx, namely:
{{{ if (not isinstance(u, (int, long, Integer)) or }}}
In fact this should check for any Sage object X for which {{{
Integer(Y) == X }}} is true for any Y.
Sounds like what you want is u in ZZ, which is equivalent to u ==
ZZ(u) except that it returns False if ZZ(u) fails.
Carl
--
To post to this group, send an email to sage-devel@googlegroups.com
To unsubscribe from this group, send an email to
sage-devel+unsubscr...@googlegroups.com
For more options, visit this group at http://groups.google.com/group/sage-devel
URL: http://www.sagemath.org
Re: [sage-devel] Re: Scary things in Sage's Digraphs
On Sun, Jul 25, 2010 at 8:10 PM, Carl Witty carl.wi...@gmail.com wrote: You seem to want to make the vertex dictionary respect the equivalence relation defined by Sage equality. If so, you're going to be in trouble, since Sage equality actually is not an equivalence relation: Is it really too much to ask? It sounds like the proper thing to do here, then, is to adjust the circulant graph constructor to use Mod(i) instead of i in the edge additions, and then profusely document this issue -- perhaps a whole chapter in the reference manual about graph gotchas... This is just really unsatisfying. I like the idea of having graphs be free enough that you can make anything you want a vertex. A mathematician would not usually say that the integer is equal to the coset. I can see why we might want sage: 3 == Mod(7, 4) True But this highlights yet another place where mathematics and computer science are less than perfect bedfellows. Just a day or two ago this sort of thing was discovered in another thread. In short, Python sets do not implement a total ordering (since means inclusion), and so are not sortable... What to do, what to do? Definition: Mod(n, m, parent=None) Docstring: Return the equivalence class of n modulo m as an element of ZZ/mZZ. According to this definition, I would expect sage: Integer(7) == Mod(7,12) False Following the Python set notation, which I think is equally silly but much harder to change, we would have sage: Integer(7) Mod(7,12) True .. -- Robert L. Miller http://www.rlmiller.org/ -- To post to this group, send an email to sage-devel@googlegroups.com To unsubscribe from this group, send an email to sage-devel+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/sage-devel URL: http://www.sagemath.org
